There will be many objects in actual project development. How to manage the objects efficiently and easily has become an important link that affects program performance and maintenance. Java provides a collection framework to solve such problems. Linear tables, linked lists, hash tables, etc. are commonly used data structures. During the development of Java, JDK has provided us with a series of corresponding classes to achieve basic data structures. All classes are in the Java.util package, and list 1 describes the relationship between the collection class.
Listing 1. The relationship between the collection class
Collection
├List
│├LinkedList
│lAarrayList
│orvector
│ kStack
└Set
Map
BHashtable
Phashmap
Sweakhashmap
Collection interface
Collection interface
Collection is the most basic collection interface. A collection represents an Object, that is, the elements of Collection. Some Collections allow the same elements and support the sorting elements, while others are not working. JDK does not provide classes directly inherited from the Collection. The classes provided by JDK are sub -interfaces inherited from Collection, such as list and set. All classes that implement the Collection interface must provide two standard constructors. The constructor without parameters is used to create an empty collection. There is a constructor with a collection parameter to create a new collection. The collection in the entry has the same elements, and the latter constructor allows users to copy a collection.
How to iterate through each element in the Collection?
Regardless of the actual type of Collection, it supports an Iterator () method. This method returns an iterative child and uses the iterative child to access each element in the collection one by one. Typical usage is as follows:
Iterator it = collection.Iterator (); // Get an iterative child while (it.hasnext ()) {object obj = it.next (); // Get the next element}The two interfaces of the Collection interface are list and set.
The main method provided by the Collection interface:
1. Boolean add (Object O) Add object to collection;
2. Boolean Remove (Object O) delete the specified object;
3. int size () Returns the number of elements in the current collection;
4. Boolean contains (Object O) Find whether there are specified objects in the set;
5. Boolean Isempty () determine whether the set is empty;
6. Iterator iterator () return a iterator;
7. Boolean ContainSall (Collection C) Find whether there are elements in the set C in the set;
8. Boolean Addall (Collection C) adds all the elements in the collection C to the collection;
9. Void Clear () delete all elements in the set;
10. Void Removeall (Collection C) Delete the elements in the set C -collection from the collection;
11. Void RetainAll (Collection C) Delete the element that does not include in the collection C from the collection.
List interface
List is an orderly collection that can accurately control the position of each element insertion with this interface. Users can use indexes (the position of elements in List, similar to the array bidding) to access the elements in List, which is similar to the Java array. Unlike the SET to be mentioned below, List allows the same elements.
In addition to the ITERATOR () method that is necessary for the Collection interface, List also provides a listiterator () method to return a Listotrator interface. Compared with the standard Iterator interface, Listotrator has some methods such as ADD (), allowing functions such as adding, deleting, setting elements, forward or backward traversal. Commonly used classes to implement List interfaces include LinkedList, ArrayList, Vector and Stack.
The main method provided by the list interface:
1. Void ADD (int index, object element) adds an object at the specified location;
2. Boolean addall (int interns, Collection C) adds the element of the set C to the specified position;
3. Object get (int index) Returns the element specified in the designated position in List;
4. INDEXOF (Object O) returns the position of the first element O;
5. Object Removeint (int index) delete the element of the specified position;
6. Object Set (int indexex, object element) replace the elements on the position index of the element Element to return the replaceable element.
MAP interface
MAP did not inherit the Colleg interface. MAP provides a mapping from key to value. A MAP cannot contain the same key, and each key can only map one value. The MAP interface provides 3 sets of views. MAP content can be regarded as a set of key sets, a group of values, or a set of key-value mapping.
The main method provided by MAP:
1. Boolean equals (Object O) comparison object;
2. Boolean Remove (Object O) delete an object;
3. Put (Object Key, Object Value) add Key and Value.
Randomaccess interface
The RandoMaccess interface is a logo interface, which does not provide any method itself. The task can be considered as an object that supports fast and random access by calling the RandomaCcess interface. The main purpose of this interface is to identify the List implementation that can support fast and random access. Any array-based List implementation implements the RaodomAccess interface, while linked list-based implementations do not. Because only the array can perform rapid random access, the random access to the linked list needs to be traversed by the linked list. Therefore, the advantage of this interface is that in the application, you can know whether the List object that is being processed can perform fast and random access, so as to perform different operations for different List to improve the performance of the program.
Introduction
LinkedList class
LinkedList implements the List interface and allows NULL elements. In addition, LinkedList provides additional GET, Remove, Insert and other methods to operate data at the first or tail of LinkedList. These operations make LinkedList can be used as stacks, queue (queue) or two -way queues. Please note that LinkedList does not have a synchronization method. It is not a thread synchronization, that is, if multiple threads access a list at the same time, you must realize your own access synchronization. One solution is to construct a synchronous list when creating list.
List list = collections.synchronizedlist (new LinkedList (…));
ArrayList class
ArrayList implements a variable -size array. It allows all elements, including NULL. SIZE, ISEMPTY, GET, SET and other methods are running time, but the ADD method overhead is the constant of the sharing. Add N elements of n elements requires O (n) time, and other methods are linear.
Each ArrayList instance has a capacity (CaPacity) to store the size of the array of storage elements. This capacity can automatically increase as it continuously adds new elements. When a large amount of elements need to be inserted, you can call the EnsureCapAcity method before inserting to increase the capacity of ArrayList to improve the insertion efficiency. Like LinkedList, ArrayList is also a thread -not -synchronized (UNSYNCHRONIZED).
The main method provided by ArrayList:
1. Boolean add (Object O) adds the specified element to the end of the list;
2. Boolean add (int indexex, object element) to specify the position to add the specified element in the list;
3. Boolean Addall (Collection C) adds the specified set to the end of the list;
4. Boolean addall (int interleg, collection C) Add a specified collection in the specified location in the list;
5. Boolean Clear () delete all elements in the list;
6. Boolean clone () Return to a copy of the list of the list;
7. Boolean contains (Object O) determine whether it contains elements in the list;
8. Boolean EnsureCapAcity (int M) increases the capacity of the list. If necessary, this list can accommodate M elements;
9. Object get (int index) Return the element specified in the list in the list;
10. INDEXOF (Object ELEM) in the list finds the bidding of the specified element;
11. Int size () returns the number of elements of the current list.
Vector class
Vector is very similar to ArrayList, the difference is that vector is synchronized by threads. The Iterator created by Vector, although the ITERATOR created by ArrayList is the same port, because Vector is synchronized, when one Iterator was created and used, the other thread changed the status of Vector (for example, adding or deleting some of some of the state Elements), when the ITERATOR method is called, the ConcurrentModificationException will be thrown out, so the exception must be captured.
Stack class
Stack inherited from Vector and realized a stack that was subsequently advanced. Stack provides 5 extra methods for Vector to be used as stacks. In addition to the basic Push and POP methods, there is also the PEEK method to get the element of the top of the stack. The EMPTY method tests whether the stack is empty, and the Search method to detect the position of an element in the stack. Note that after Stack was just created, it was an empty stack.
SET class
Set is a collection without repeated elements, that is, any two element E1 and E2 have E1.equals (E2) = false. There is a NULL element at most set. Obviously, the constructor of the SET has a constraint condition, and the input of the collection parameters cannot include duplicate elements. Please note that you must carefully operate the variable objects. If the variable elements in a set change the state, this may cause some problems.
Hashtable class
Hashtable inherits the MAP interface and implements a hash table based on Key-Value mapping. Any Non-NULL object can be used as key or value. Add data to use PUT (key, value), and take out the data to use GET (key). The time over time of these two basic operations is the constant.
Hashtable adjusts the performance through the two parameters of the initial capacity and load factor. The default Load Factor 0.75 better achieves the balance of time and space. Increasing Load Factor can save space but the corresponding search time will increase, which will affect operations like Get and PUT. Use the simple example of Hashtable to put the three numbers of 1, 2, and 3 in the Hashtable. Their key is "One", "TWO", and "Three", which are shown in the list 2.
List 2. Hashtable Example
Hashtable numbers = new Hashtable();numbers.put(“one”, new Integer(1));numbers.put(“two”, new Integer(2));numbers.put(“three”, new Integer(3 );
If we need to take out a number, such as 2, we can use the corresponding key to take it out, and the code is shown in List 3.
List 3. Read data from hastable
Integer n = (integer) numbers.get ("two"); System.out.println ("two ="+ n);Since the object of the key will be determined by calculating its distribution function to determine the position of the corresponding value, any object as a key must implement the HashCode and Equals methods. HashCode and Equals methods inherit the root Object. If you use a custom class as Key, you must be very careful. According to the definition of the latter function, if the two objects are the same, that is, obj1.equals (obj2) = True, then Their hashcode must be the same, but if the two objects are different, their hashcode is not necessarily different. If the hashcode of the two different objects is the same, this phenomenon is called a conflict. So try to define the HashCode () method that can speed up the operation of hash tables.
If the same object has different Hashcode, there will be unexpected results for the operation of the hash table (looking forward to returning NULL). To avoid this problem, it is best to write the Equals method and the HashCode method at the same time, instead of just writing One of them.
HashMap Class
Hashmap is similar to Hashtable. The difference is that HashMap is non -synchronized thread and allows NULL, namely Null Value and Null Key. However, when the HashMap is regarded as the collection (the Values () method can be returned), it is proportional to the iterative sub -operating time overhead and the capacity of HashMap. Therefore, if the performance of iteration operation is very important, do not set the initialization capacity of HashMap too high, or set too low in the Load Factor parameter.
Weakhashmap class
Weakhashmap is a improved HashMap that "weak reference" for Key. If a key is no longer cited by the outside, the key can be recycled by GC.
Collection class practice
ArrayList, Vector, and LinkedList are all implemented from AbstractList, and AbstractList directly implements the List interface and is extended from AbstarctCollection. ArrayList and Vector use arrays to implement. ArrayList does not provide a thread synchronization for any method, so it is not thread security. Most of the methods in Vector have done thread synchronization, which is a thread security realization. LinkedList uses a circular two -way linked data structure, which is connected by a series of table items. A table item always contains 3 parts, element content, front drive tables, and rear drive tables.
When ArrayList's demand for capacity exceeds the size of the current array, it needs to be expanded. During the capacity expansion process, a large number of array replication operations will be performed, and when the array is replicated, the System.arrayCopy () method will be finally called. Since the linkedlist uses the structure of the linked list, it does not need to maintain the size of the capacity. However The influence, the new object is still occupied by a certain resource. Because of the continuity of the array, when the element is always increased at the end, the array expansion and array replication can only be generated when the space is insufficient.
ArrayList is based on array, and the array is a continuous memory space. If the element is inserted in any location of the array, all elements after that position will need to be re -arranged. Therefore Tail. LinkedList does not decrease performance due to inserting data.
Each effective element of ArrayList must be reorganized after deleting operations, and the higher the positioning of the deleted element position, the greater the overhead during the reorganization of the array. LinkedList needs to remove the intermediate data for half a list.
List 4. ArrayList and linkedList use code
Import Java.util.arrayList; Import Java.util.linkedList; Public Class ArrayListandLINDList {Public Static Void Main (String [] ARGS) {Long Start = Sy. STEM.CURRENTTTIMEMILLIS (); ArrayList list = New ArrayList (); Object Obj = New Object (); for (int i = 0; I <5000000; i ++) {list.add (obj);} long end = system.currenttimemillis (); System.out.println (End-Start); m. Currenttimemillis (); LinkedList list1 = new LinkedList (); Object obj1 = new object (); for (int i = 0; I <5000000; I ++) {list1.add (obj1);} END System.currenttimemillis (); System.out.println (End-Start); Start = System.CurrenTtiMillis (); Object Obj2 = New Object (); for (Int I = 0; I <1000; I ++) {List.add (0, Obj2 ); } END = System.currentttiMemillis (); System.out.println (End-Start); Start = System.Currenttimemillis (); Object obj3 = new object (); for (int i =0;i<1000;i++){ list1.add (obj1);} End = System.CurrenTtTimemillis (); System.out.println (End-Start); Start = System.CurrenTtimemillis (); List.remove (0); EN d = System.currentttimemillis (); System.out.println (End-Start); Start = System.Currenttimemillis (); List1.remove (250000); End = System.CurrenTtimemillis (); System.out.println (End-Start);}}List 5. Run output
639129669690015
HashMap is to make the key algorithm, and then map the hash value to the memory address to directly obtain the data corresponding to the key. In HashMap, the underlying data structure uses an array, the so -called memory address is the label index of the array. HashMap's high performance requires the following points:
1. The Hash algorithm must be efficient;
2. The algorithm of the hash value to the memory address (array index) is fast;
3. According to the memory address (array index), you can directly obtain the corresponding value.
HashMap is actually an array of a linked list. As mentioned earlier, the implementation mechanism based on the linked list method based on the hashmap, as long as the HashCode () and Hash () methods are achieved enough to reduce the occurrence of conflict as much as possible, then the operation of HashMap is almost equivalent to random access to the array of arrays. Operation has good performance. However, if the HashCode () or Hash () method is poorly achieved, in the case of a large number of conflicts, the HashMap is actually degraded into several linked lists, which is equivalent to the linked list for the operation of HashMap. At this time, the performance is very poor.
A functional disadvantage of HashMap is its disorder, which is stored in the elements in HashMap. When traversing HashMap, its output is disorderly. If you want to keep the input order, you can use LinkedhashMap instead.
LinkedhashMap inherits from HashMap and has high efficiency. At the same time, on the basis of HashMap, a linked list is added inside to store the order of elements.
HashMap can operate Put () and GET () as fast as the Hash algorithm. TREEMAP provides a completely different MAP implementation. In terms of function, TreeMap has a more powerful feature than HashMap. It implements the SortedMap interface, which means that it can sort the elements. TREEMAP's performance is slightly lower than HashMap. If you need to sort the elements in development, you cannot implement this function with HashMap. The iteration output of TreeMap will be performed in the order of elements. LinkedhashMap is based on the order of element entering the collection or sequential order of being accessed. TreeMap is based on the inherent sequence of elements (determined by Comparator or Comparable).
LinkedhashMap is sorted according to the order of element increase or access, while TreeMap is sorted according to the key of the element.
Listing 6 shows that the code demonstrates the order of business logic using TreeMap.
Listing 6. TreeMap implements sorting
Import java.util.iterator; Import Java.util.map; Import Java.util.Treemap; Public Class StudentS Comparable <student> {Public Stration; Public int Score; Public Student (String name, int score) {this. name = name; this.Score = score;} @ouverride // Tell Treemap how to sort the Public Int Compareto (Student O) {// TODO-GENERATED METHOD (O.Score <THIS.SC OR) {Return 1;} Else if (O.SCORE> this.Score) {Return -1;} Return 0;} @OverridePublic String Tostring () {StringBuffer sb = New Stringbuffer (); sb.append ("name:") ; sb.append (name ); sb.append (""); sb.append ("score:"); sb.append (score); Return sb.tostring ();} Public Static void Main (string [] args) {treemap map = new TreeMap();Student s1 = new Student("1",100);Student s2 = new Student("2",99);Student s3 = new Student("3",97);Student s4 = new Student(" 4 ", 91); Map.put (s1, New StudentDetailinfo (s1)); Map.put (s2, new studentdetailinfo (s2)); Map.put (s3, new studentdetailinfo (s3)); S4 , New StudentDetailinfo (S4)); // Print the scores Map Map1 = (Treemap) .submap (s4, s2); for (Iterator itctor = MAP1.KEYSET (). Iterator (). );;) {Student key = (Student) Iterator.next (); System.out.println (key+"->"+map.get (key));} System.out.println ("" Submap end "); // Map1 = ((timeMap) map). Headmap (s1); for (iterator iterator = map1.keyset (). Iterator.hasnext ();) {Student key = (student) Iterator.next (); system.out.println (key+"->"+map.get (key));} System.out.println ("submap end"); // print score Map1 = ((Treemap) .tailmap (s1); for (Iterator Iterator = MAP1.KEYSET (). Iterator.hasnext ();) {Student Key = (Student) itrator. Next (); System.out.println (key+"->"+map.get (key));} System.out.println ("Submap End"); LIC StudentDetailinfo (Student S ) {this.s = s;}@ounridepublic string tostring () {Return s.Name + "'s Detail information";}}List 7. Run output
name: 4 Score: 91-> 4's Detail InformationName: 3 Score: 97-> 3's Detail InformationSubmap Endname: 4 Score: 91-> 4's Detail InformationName: 3 Score: 97-> 3 'S Detail InformationName: 2 Score: 99-> 2's Detail InformationSubmap Endname: 1 Score: 100-> 1's Detail InformationSubmap End
Weakhashmap is characterized by itself that if there is no other cither in this key except for its citations, then this MAP will automatically discard the value. As shown in Listing 8, the code shows two MAP objects, one is HashMap, and the other is WeakhashMap. At the same time, put it in two objects to two MAPs. When HashMap is deleted a, and A and B are pointing to NULL, they point to NULL. A in WeakhashMap will be automatically recycled. The reason for this situation is that for Object A, when HashMap is deleted and A to NULL, in addition to Weakhashmap, there is no pointer to A except A Although pointing to NULL, there is a pointer pointed to B in HashMap, so Weakhashmap will retain the B object.
List 8.weakhashmap example code
Import java.util.hashmap; Import Java.util.itrator; Import java.util.map; Import Java.util.weakhashmap; Public Class WeakhashmapTest {Pub LIC Static Void Main (String [] ARGS) Throws Exception {String A = New String ("A"); String B = New String ("B"); Map Weakmap = New Weakhashmap (); Map Map = New HashMap (); Map.put (A, "AAA"); Map.put (B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, "bbb"); weakmap.put (a, "aaa"); weakmap.put (b, "bbb"); map.remove (a); a = null; b = null; system.gc (); Iterator I = map.entrySet (). Iterator (); about (i.hasnext ()) {map.entry en = (map.entry) izext (); system.out.println ("map:"+en.getkey ()+":"+en.getvalue ());} Iterator j = Weakmap.entryset (). Iterator (); While (j.hasnext ()) {map.entry en = (map.entry) j.next (); System.out.println ("Weakmap:"+EN.Getkey ()+":"+EN.GetValue ());Listing 9. Run output
MAP: B: BBBWEAKMAP: B: BBB
Weakhashmap mainly achieves the purpose of removing the internal unused entries through ExpungestAleEntries, thereby achieving the purpose of automatically release memory. Basically, as long as the content of Weakhashmap is accessed, this function will be called to achieve the internal entry that is no longer referenced. But if you have become a weakhashmap, and before the GC, you have never visited the weakhashmap, isn't it unlimited to release memory?
List 10. Weakhashmaptest1
Import java.util.arrayList; Import Java.util.List; Import Java.util.weakhashmap; Public Class Weakhashmapst1 {Public Static Void Main (String [] ARGS) Throws Exception {list <weakhashmap <byte [] [], byte [ ] [] >> Maps = New ArrayList <weakhashmap <byte [] [], byte [] [] >> (); for (int i = 0; i <1000; i ++) {weakhashmap <byte [], byte [] []> d = New Weakhashmap <byte [] [], byte [] []> (); d.Put (new byte [1000] [1000], new byte [1000] [1000]); maps .add (d); system.gc (); System.err.println (i);}}}Do not change any JVM parameter running list 10 shown in the operation list. Since the default memory of the Java is 64M, the memory overflows the error.
List 11. Run output
241242243Excetion in Thread "Main" Java.lang.outoFMemoryerror: Java Heap Spaceat Weakhashmaptest1.Main (weakhashmapst1.java:10)
Sure enough, weakhashmap did not automatically release unnecessary memory at this time. The code shown in Listing 12 will not have a memory overflow.
List 12. WeakhashmapTest2
Import Java.util.arrayList; Import Java.util.List; Import Java.util.weakhashmap; Public Class Weakhashmapst2 {Public Static Void Main (String [] ARGS) Throws Exception {list <weakhashmap <byte [] [], byte [ ] [] >> Maps = New ArrayList <weakhashmap <byte [] [], byte [] [] >> (); for (int i = 0; i <1000; i ++) {weakhashmap <byte [], byte [] []> d = New Weakhashmap <byte [] [], byte [] []> (); d.Put (new byte [1000] [1000], new byte [1000] [1000]); maps .add (d); system.gc (); system.err.println (i); for (int j = 0; j <i; j ++) {system.err.println (j + "size" + maps.Get (j) .size ());}}}}The results of the operation found that the test output was normal, and the problem of memory overflow was no longer occurred.
In general, weakhashmap is not an object that is not used inside if you do anything, but release the internal unused object when you access it.
WeakHashMap implements weak references because its Entry<K,V> is inherited from WeakReference<K>.
In the class definition and constructor of the Weakhashmap $ Entry <k, V>, it is shown in the list 13.
List 13. Weakhashmap class definition
Private Static Class Entry <k, V> Extends Weakreference <k> Implements Map.entry <k, V> ENTRY (K Key, V Value, ReferenceQueue <k> Queue, Int Hash, ENTRY <k, v> next) {super (key, queue); this.Value = value; this.hash = hash; this.next = next;}Please note that it constructs a father -class statement: "Super (key, queue);"; Key is introduced, so key is for weak reference. Value is directly referenced in this.value. In System.gc (), the BYTE array in the key is recycled, and Value remains (Value is strongly associated to Entry, Entry is associated in MAP, and MAP is associated in ArrayList).
Every time I have a new Weakhashmap every time, after the PUT operation, although the GC recycles the Byte array in Weakreference Key, and notify the event to ReferenceQueue, there is no corresponding action to trigger Weakhashmap to handle Referenceq ueue Therefore, the weakreference packaging Key still exists in Weakhashmap, and its corresponding value also exists.
When is the value be cleared? Analyze the two sample programs of List 10 and List 11, which can be seen that the maps.get (j) .size () of the list 11 triggered the recycling of value. How can it be triggered? Check the weakhashmap source code. You can see that the SIZE method calls the ExpungestaleEntries method. This method traverses the Entry (QUENE) to be recovered by the JVM, and the Value of the Entry is empty to recover the memory. Therefore, the effect is that Key was cleared when GC, and Value visited Weakhashmap after the key was cleared.
The WEAKHASHMAP class is non -synchronized. You can use the collections.synChronizedMap method to construct a synchronized Weakhashmap. Each key object is indirectly stored as a weak reference indicator object. Therefore, whether it is within the mapping or outside the mapping, the key is automatically removed only after the garbage recyler removes the weak reference to a certain key. It should be noted that the value object in the weakhashmap is kept by the general attraction. Therefore, you should be careful to ensure that the value object will not directly or indirectly reference its own keys, because this will prevent the tension from discarding. Note that the value object can indirectly quote the corresponding key through the WeakhashMap itself, which means that a certain value object may be strongly referenced by other key objects, and the value object associated with the key object turns to the first one to reference the first one. The key of the value object.
One way to deal with this problem is to pack the value itself in Weakreferentes before inserting, such as: M.Put (Key, New Weakreference (VALUE)), and then use Get to dissection. All the "Collection view views The method of "the backing device is rapidly failed. After the iterative device is created, if the mapping is modified from the structure, unless the iterator's own Remove or ADD method, the iterators will be modified at any time and any way, and the iterator will be Throw the ConcurrentModificationException. Therefore, in the face of concurrency modification, the iterator quickly failed completely, rather than risk at arbitrary uncertain behavior at any time in the future.
Note that we cannot ensure that the iterator fails. Generally speaking, when there is a non -synchronized concurrency modification, it is impossible to make any completely determined guarantee.
To sum up the introduction and instance code in the previous comprehensive, we can know that if it involves stacks, queues, etc., we should consider using List. For operations such as fast insertion and deleting elements, LinkedList should be used. If you need to access elements quickly, you should use ArrayList. If the program is performed in a single -threaded environment or access only in one thread, considering non -synchronized classes, it is efficient. If multiple threads may operate a class at the same time, the synchronous class should be used. Pay special attention to the operation of the hash table, and the object of the Equals and HashCode as a key is to correctly write the Equals and HashCode methods. Try to return the interface instead of actual types, such as returning list instead of ArrayList, so that if ArrayList needs to be replaced with linkedList in the future, the client code does not need to change. This is to perform programming ideas for abstract.
This article is only for the sharing of the application level. I hope it will be helpful to optimize the operation of the Java collection class.