The architecture of the Java collections framework is described in detail
- 2020-04-01 01:09:36
- OfStack
In a recent J2EE book, I saw a great description of the collection framework, which is filtered and Shared. The collection framework provides interfaces and classes for managing collections of objects. It contains interfaces, classes, and algorithms.
The Collection interface
Collection is the most basic Collection interface. A Collection represents a group of objects, namely Elements of the Collection. Some collections allow the same elements and others do not. Some sort and some don't. The Java SDK does not provide classes that are directly inherited from the Collection. The classes provided by the Java SDK are "sub-interfaces" that are inherited from the Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: a constructor with no arguments to create an empty Collection, and a constructor with a Collection argument to create a new Collection that has the same elements as the incoming Collection. The latter constructor allows the user to copy a Collection.
How do I iterate through each element in the Collection? Regardless of the actual type of the Collection, it supports an iterator() method that returns an iterator that accesses each element of the Collection one by one. Typical usage:
The two interfaces derived from the Collection interface are List and Set.
The List interface
A List is an ordered Collection, and this interface allows you to precisely control where each element is inserted. The user can access the elements in a List using an index (the position of the elements in a List, similar to an array index), which is similar to an array in Java.
Unlike the sets mentioned below, a List is allowed to have the same elements.
In addition to the mandatory iterator() method with the Collection interface, the List also provides a listIterator() method that returns a listIterator interface. Compared with the standard iterator interface, listIterator has a few more methods like add(), allows you to add, delete, set elements, and iterate back and forth.
Common classes that implement the List interface are LinkedList, ArrayList, Vector, and Stack.
LinkedList class
LinkedList implements the List interface, allowing null elements. Additionally LinkedList provides additional get, remove, and insert methods at the beginning or end of a LinkedList. These actions enable LinkedList to be used as a stack, queue, or two-way queue.
Note that there is no synchronized method on LinkedList. If multiple threads access a List at the same time, you must implement the access synchronization yourself. One solution is to construct a synchronized List when creating a List:
List the List = Collections. SynchronizedList (new LinkedList (...). );
ArrayList class
ArrayList implements arrays of variable size. It allows all elements, including null. The ArrayList is not synchronized.
Size, isEmpty, get, set methods run at constant time. But the add method costs a amortized constant, and it takes O(n) to add n elements. Other methods run linearly.
Each ArrayList instance has a Capacity, the size of the array used to store the elements. This capacity increases automatically as new elements are added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called before insertion to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is unsynchronized.
The Vector class
A Vector is very similar to an ArrayList, but a Vector is synchronous. Founded by the Vector of the Iterator, although and ArrayList Iterator is created by the same interface, however, because of the Vector are synchronous, when an Iterator is created and is being used, another thread changed the state Vector (add or delete some of the elements, for example), then call Iterator methods will throw ConcurrentModificationException, so you must catch the exception.
The Stack class
Stack inherits from Vector and implements a last in, first out Stack. Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and pop methods, as well as the peek method, get the top element on the stack, the empty method tests if the stack is empty, and the search method detects the position of an element on the stack. The Stack is empty after it is created.
The Set interface
Set is a Collection that does not contain duplicate elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.
Obviously, the Set constructor has a constraint that the incoming Collection parameter cannot contain duplicate elements.
Please note: must be careful operation variable Object (Mutable Object). This can cause problems if a mutable element in a Set changes its state and causes object.equals (Object)=true.
The Map interface
Note that the Map does not inherit the Collection interface and that the Map provides a key to value mapping. A Map cannot contain the same key, and each key can only Map one value. The Map interface provides a view of three collections. The contents of a Map can be treated as a set of key collections, a set of value collections, or a set of key-value mappings.
Hashtable class
Hashtable inherits the Map interface and implements a Hashtable for key-value mapping. Any non-null object can be used as a key or value.
Put (key, value) is used to add data, and get(key) is used to fetch data. The time cost of these two basic operations is constant.
Hashtable adjusts performance with two parameters, initial capacity and load factor. The default load factor 0.75 is generally a good time and space balance. Increasing the load factor saves space but increases the search time accordingly, which can affect operations like get and put.
A simple example of using Hashtable is to put 1, 2, and 3 into the Hashtable with keys "one", "two", and "three" :
To extract a number, such as 2, use the corresponding key:
Integer n = (Integer) Numbers. Get (" two ");
System.out.println(" two = "+ n);
Since the object as key will determine the location of its corresponding value by calculating its hash function, any object as key must implement the hashCode and equals methods. The equals and hashCode methods inherited from the root class Object, if you use a custom class as the key, be very careful, as defined by the hash function, if two objects are the same, namely obj1) equals (obj2) = true, they must be the same hashCode, but if two objects are different, the hashCode they may not different, if two different objects of the same hashCode, this phenomenon is called conflict, conflict can lead to hash operation time cost increase, So the hashCode() method, as defined as possible, will speed up the operation of the hash table.
If the same object has a different hashCode, the operation on the hash table can yield unexpected results (the expected get method returns null). To avoid this problem, just remember to copy both equals and hashCode methods, not just one.
Hashtable is synchronous.
A HashMap class
A HashMap is similar to a Hashtable, except that a HashMap is asynchronous and allows for null, that is, null value and null key. , but the (values() method returns a Collection when a HashMap is treated as a Collection, and its iterator operation time is proportional to the capacity of the HashMap. Therefore, do not set the initialization capacity of the HashMap too high or the load factor too low if the performance of the iteration operation is important.
WeakHashMap class
WeakHashMap is an improved HashMap that implements a "weak reference" to a key. If a key is no longer externally referenced, it can be recovered by the GC.
conclusion
List should be considered if you are involved in stack, queue, etc. LinkedList should be used if you need to insert and delete elements quickly, and ArrayList should be used if you need to access elements randomly and quickly.
It is more efficient to consider asynchronous classes if the program is in a single-threaded environment, or if access is limited to one thread, and to use synchronized classes if multiple threads may operate on a class at the same time.
Pay special attention to the operation of the hash table, the object as the key should correctly copy the equals and hashCode methods.
Try to return the interface instead of the actual type, such as a List instead of an ArrayList, so that the client code doesn't change if you later need to replace the ArrayList with a LinkedList. This is programming against the abstract.
The Collection interface
Collection is the most basic Collection interface. A Collection represents a group of objects, namely Elements of the Collection. Some collections allow the same elements and others do not. Some sort and some don't. The Java SDK does not provide classes that are directly inherited from the Collection. The classes provided by the Java SDK are "sub-interfaces" that are inherited from the Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: a constructor with no arguments to create an empty Collection, and a constructor with a Collection argument to create a new Collection that has the same elements as the incoming Collection. The latter constructor allows the user to copy a Collection.
How do I iterate through each element in the Collection? Regardless of the actual type of the Collection, it supports an iterator() method that returns an iterator that accesses each element of the Collection one by one. Typical usage:
Iterator it = collection.iterator(); //Get an iterator
while(it.hasNext()) {
Object obj = it.next(); //I get the next element
}
The two interfaces derived from the Collection interface are List and Set.
The List interface
A List is an ordered Collection, and this interface allows you to precisely control where each element is inserted. The user can access the elements in a List using an index (the position of the elements in a List, similar to an array index), which is similar to an array in Java.
Unlike the sets mentioned below, a List is allowed to have the same elements.
In addition to the mandatory iterator() method with the Collection interface, the List also provides a listIterator() method that returns a listIterator interface. Compared with the standard iterator interface, listIterator has a few more methods like add(), allows you to add, delete, set elements, and iterate back and forth.
Common classes that implement the List interface are LinkedList, ArrayList, Vector, and Stack.
LinkedList class
LinkedList implements the List interface, allowing null elements. Additionally LinkedList provides additional get, remove, and insert methods at the beginning or end of a LinkedList. These actions enable LinkedList to be used as a stack, queue, or two-way queue.
Note that there is no synchronized method on LinkedList. If multiple threads access a List at the same time, you must implement the access synchronization yourself. One solution is to construct a synchronized List when creating a List:
List the List = Collections. SynchronizedList (new LinkedList (...). );
ArrayList class
ArrayList implements arrays of variable size. It allows all elements, including null. The ArrayList is not synchronized.
Size, isEmpty, get, set methods run at constant time. But the add method costs a amortized constant, and it takes O(n) to add n elements. Other methods run linearly.
Each ArrayList instance has a Capacity, the size of the array used to store the elements. This capacity increases automatically as new elements are added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called before insertion to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is unsynchronized.
The Vector class
A Vector is very similar to an ArrayList, but a Vector is synchronous. Founded by the Vector of the Iterator, although and ArrayList Iterator is created by the same interface, however, because of the Vector are synchronous, when an Iterator is created and is being used, another thread changed the state Vector (add or delete some of the elements, for example), then call Iterator methods will throw ConcurrentModificationException, so you must catch the exception.
The Stack class
Stack inherits from Vector and implements a last in, first out Stack. Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and pop methods, as well as the peek method, get the top element on the stack, the empty method tests if the stack is empty, and the search method detects the position of an element on the stack. The Stack is empty after it is created.
The Set interface
Set is a Collection that does not contain duplicate elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.
Obviously, the Set constructor has a constraint that the incoming Collection parameter cannot contain duplicate elements.
Please note: must be careful operation variable Object (Mutable Object). This can cause problems if a mutable element in a Set changes its state and causes object.equals (Object)=true.
The Map interface
Note that the Map does not inherit the Collection interface and that the Map provides a key to value mapping. A Map cannot contain the same key, and each key can only Map one value. The Map interface provides a view of three collections. The contents of a Map can be treated as a set of key collections, a set of value collections, or a set of key-value mappings.
Hashtable class
Hashtable inherits the Map interface and implements a Hashtable for key-value mapping. Any non-null object can be used as a key or value.
Put (key, value) is used to add data, and get(key) is used to fetch data. The time cost of these two basic operations is constant.
Hashtable adjusts performance with two parameters, initial capacity and load factor. The default load factor 0.75 is generally a good time and space balance. Increasing the load factor saves space but increases the search time accordingly, which can affect operations like get and put.
A simple example of using Hashtable is to put 1, 2, and 3 into the Hashtable with keys "one", "two", and "three" :
Hashtable numbers = new Hashtable();
numbers.put( " one " , new Integer(1));
numbers.put( " two " , new Integer(2));
numbers.put( " three " , new Integer(3));
To extract a number, such as 2, use the corresponding key:
Integer n = (Integer) Numbers. Get (" two ");
System.out.println(" two = "+ n);
Since the object as key will determine the location of its corresponding value by calculating its hash function, any object as key must implement the hashCode and equals methods. The equals and hashCode methods inherited from the root class Object, if you use a custom class as the key, be very careful, as defined by the hash function, if two objects are the same, namely obj1) equals (obj2) = true, they must be the same hashCode, but if two objects are different, the hashCode they may not different, if two different objects of the same hashCode, this phenomenon is called conflict, conflict can lead to hash operation time cost increase, So the hashCode() method, as defined as possible, will speed up the operation of the hash table.
If the same object has a different hashCode, the operation on the hash table can yield unexpected results (the expected get method returns null). To avoid this problem, just remember to copy both equals and hashCode methods, not just one.
Hashtable is synchronous.
A HashMap class
A HashMap is similar to a Hashtable, except that a HashMap is asynchronous and allows for null, that is, null value and null key. , but the (values() method returns a Collection when a HashMap is treated as a Collection, and its iterator operation time is proportional to the capacity of the HashMap. Therefore, do not set the initialization capacity of the HashMap too high or the load factor too low if the performance of the iteration operation is important.
WeakHashMap class
WeakHashMap is an improved HashMap that implements a "weak reference" to a key. If a key is no longer externally referenced, it can be recovered by the GC.
conclusion
List should be considered if you are involved in stack, queue, etc. LinkedList should be used if you need to insert and delete elements quickly, and ArrayList should be used if you need to access elements randomly and quickly.
It is more efficient to consider asynchronous classes if the program is in a single-threaded environment, or if access is limited to one thread, and to use synchronized classes if multiple threads may operate on a class at the same time.
Pay special attention to the operation of the hash table, the object as the key should correctly copy the equals and hashCode methods.
Try to return the interface instead of the actual type, such as a List instead of an ArrayList, so that the client code doesn't change if you later need to replace the ArrayList with a LinkedList. This is programming against the abstract.