1. Interface inheritance and implementation
The collection classes are stored in the java.util package, and there are three main types: set, list, and Map.
- Collection: Collection is the basic interface to the Collection List, Set, and Queue.
- Iterator: an Iterator that iterates through the data in a collection
- Map: is the basic interface of a mapping table
2. Set the List
Java’s List is a very common data type. A List is an ordered Collection. There are three Java List implementation classes: ArrayList, Vector, and LinkedList.
2.1. ArrayList
ArrayList, the most commonly used List implementation class, is internally implemented through arrays, allowing fast random access to elements. The disadvantage of arrays is that there can be no space between each element. When the size of arrays is insufficient and the storage capacity needs to be increased, the data that already has arrays must be copied to the new storage space. When inserting or deleting elements from the middle of an ArrayList, the array needs to be copied, moved, and expensive. Therefore, it is suitable for random lookup and traversal, not insertion and deletion.
2.2. Vector (Array implementation, thread synchronization)
Vector, like ArrayList, is implemented using arrays. The difference is that it supports thread synchronization, which means that only one thread can write a Vector at a time. This avoids the inconsistencies caused by multiple threads writing simultaneously, but synchronization is expensive and therefore slower to access than ArrayList.
2.3. LinkList
LinkedList is a LinkedList structure to store data, which is suitable for dynamic insertion and deletion of data. Random access and traversal are slow. In addition, it provides methods not defined in the List interface that are specifically used to manipulate table header and table tail elements, and can be used as stacks, queues, and two-way queues.
3. Set the Set
Set focuses on unique properties. It is a collection of systems used to store elements that are unordered (stored and retrieved in different order) and cannot be repeated. Object equality is essentially determined by the Object’s hashCode value (Java calculates this number based on the Object’s memory address). If you want two different objects to be considered equal, you must override Object’s hashCode and equals methods.
3.1 HashSet (Hash Table)
The edge of a hash table holds hash values. A HashSet stores elements not in the order in which they were stored (unlike a List, of course) but in the hash value. The hash of an element is obtained using the element’s HashCode method. The HashSet first evaluates the hash values of two elements. If the hash values are the same, the HashSet is then compared to equals if the equls result is true. If equals is false, it is not the same element.
How do you store elements that have the same hash value equals false, which is the continuation of the same hash value (you can think of elements with the same hash value in a hash bucket). So it’s going to be hashed in a column. Figure 1 shows the case where hashCode values are different; Figure 2 shows the case where hashCode is the same but equals is different.
3.2 TreeSet (Binary Tree)
- TreeSet() sorts newly added objects in ascending and descending order using the principle of binary tree. Each new object is sorted and inserted into the specified position in the binary tree.
- The default TreeSet ordering is available for both Integer and String objects. Objects of custom classes are not. Self-defined classes must implement the Comparable interface and override the corresponding compareTo() function to be usable.
- When you overwrite compare(), you need to return the corresponding value to make TreeSet sort according to certain rules
- Compares the order of this object with the specified object. If the object is less than, equal to, or greater than the specified object, a negative integer, zero, or positive integer is returned, respectively.
3.3 LinkHashSet (HashSet+LinkedHashMap)
For LinkedHashSet, it inherits from HashSet and is based on LinkedHashMap. The underlying LinkedHashSet uses LinkedHashMap to store all elements. It inherits from HashSet, and all its methods are the same as HashSet. Therefore, the implementation of LinkedHashSet is very simple, providing only four constructors. And by passing an identity parameter, call the constructor of the parent class, the underlying structure of a LinkedHashMap to achieve, in related operations with the parent class HashSet operation is the same, directly call the method of the parent class HashSet.
4. Map mapping
4.1 HashMap (Array + Linked List + Red-black Tree)
A HashMap stores data based on the hashCode value of a key, and in most cases its value can be located directly, thus providing fast access, but the traversal order is uncertain. A HashMap allows at most one record to have a null key and multiple records to have a NULL value. A HashMap is not thread-safe, meaning that more than one thread can write a HashMap at any one time, which can lead to data inconsistencies. If thread-safe is desired, the Collections synchronizedMap method can be used to make HashMap thread-safe, or ConcurrentHashMap can be used. Let’s use the following diagram to illustrate the structure of a HashMap.
4.4.1 Java 7 implementation
- Capacity: Indicates the current array capacity. The capacity is always 2^n and can be expanded. After the array capacity is expanded, the array size is twice that of the current one.
- LoadFactor: loadFactor. The default value is 0.75.
- Threshold: capacity expansion threshold, equal to capacity x loadFactor
4.1.2 JAVA8 implementation
Java8 makes some changes to HashMap, but the big difference is that it leverages red-black trees, so it consists of arrays, linked lists, and red-black trees.
Java7 HashMap can quickly locate the index of the array based on the hash value, but then we need to go down the list to find the index. The time complexity depends on the length of the list, O(n). To reduce this overhead, in Java8, when the list has more than eight elements, the list is converted to a red-black tree, reducing the time complexity of lookups at these locations to O(logN).
4.2 ConcurrentHashMap
2. The Segment period
ConcurrentHashMap has the same idea as HashMap, but is more complex because it supports concurrent operations. The entire ConcurrentHashMap consists of segments that stand for “part” or “Segment”, and are often described as segmented locks. Notice how many places I used “slots” to represent a segment.
4.2.2. Thread Safety (Segment inheritance ReentrantLock)
ConcurrentHashMap is an array of segments. A Segment is locked by inheritingReentrantLock. As long as each Segment is thread-safe, global thread-safe is achieved.
4.2.3. Degree of parallelism (default 16)
ConcurrencyLevel: concurrencyLevel, number of concurrent sessions, number of segments. The default value is 16, which means that ConcurrentHashMap has 16 Segments, so in theory up to 16 concurrent writes can be supported at this point, as long as their operations are distributed over different Segments. This value can be set to another value at initialization, but it cannot be expanded once initialized. Each Segment looks like a HashMap, but it’s thread safe, so it’s a bit more difficult to handle.
4.2.4. Java8 implementation (red black tree introduced)
Java8 has made major changes to ConcurrentHashMap and also introduced red-black trees.
4.3. HashTable (Thread-safe)
Hashtable is a legacy class. Many common functions of HashMap are similar to those of Dictionary class, but it is thread-safe. Only one thread can write Hashtable at any time. ConcurrentHashMap introduces segmental locking. The use of Hashtable is not recommended in new code, and can be replaced with HashMap in cases where thread safety is not required, and ConcurrentHashMap in cases where thread safety is required.
4.4. TreeMap (sortable)
TreeMap implements the SortedMap interface, which sorts the records it holds by key. By default, the keys are sorted in ascending order. You can also specify a comparator for sorting.
If sorted mappings are used, TreeMap is recommended.
When using a TreeMap, key must implement the Comparable interface or in constructing TreeMap incoming custom Comparator, otherwise it will throw at runtime Java. Lang. ClassCastException type of exception.
Reference: www.ibm.com/developerwo…
4.5. LinkHashMap (Record insertion order)
LinkedHashMap is a subclass of HashMap, which stores the insertion order of records. When Iterator traverses a LinkedHashMap, the records obtained first must be inserted first. It can also be constructed with parameters and sorted by access order.
Reference 1:www.importnew.com/28263.html
Reference 2:www.importnew.com/20386.html#…