This is the first day of my participation in Gwen Challenge
I haven’t read hashmap source code for so long. Recently I came to understand the underlying structure of HashMap. Although there are many articles about Hashmap on the Internet, I still want to learn and summarize. In jdk1.8, hashmap is an array + linked list + red-black tree.
Basic structure drawing
The node class
Node object Properties
Hash: Hash value of the key
Key: Indicates the key of the node. The type is the same as that used to define the HashMap
Value: The value of the node, which is of the same type as the value defined in the HashMap
Next: The default capacity is 16. The second capacity is 32. The third capacity is 64. To prevent some index results from appearing more frequently after modular operation, and some index results will never appear, in order to make index distribution more uniform, the power of 2 is adopted. See hashMap
If TAB [I] is empty, place node there, and node.next is null. If TAB [I] is empty, place node there. If TAB [I] is not empty it will determine whether the key value is equal (hashCode is always the same), if the key value is equal it will replace the node, if the key value is not equal it will insert the node at the top of the list, next will connect to the previous node, Table [0] = C; table[0] = C; table[0] = C;
Hashmap also has loadFactor loadFactor (0.75 by default), capacity capacity (16 by default), and threshold (loadFactor * capacity), which is used to measure how full hashmap is. When the capacity of a map divided by the total capacity of capacity is >=loadFactor, the current capacity of a map is greater than threshold and the map will be expanded.
Put method
If the length of the list is greater than TREEIFY_THRESHOLD, it will be converted to a red-black tree. If the length of the list is greater than TREEIFY_THRESHOLD, it will be converted to a red-black tree. However, if the TAB length is less than MIN_TREEIFY_CAPACITY (the default value is 64), it will not be converted to a red-black tree, but will be expanded and hashed again ((n-1) & mod, because the length changes after the expansion, node subscript will be changed to prevent the list from becoming too long) to prevent the list from becoming too long.
Linked list to red black tree
Since hashmap is not thread-safe, deadlock problems may occur when multi-threading hashmap expansion. Suppose we have two threads A and B, hashmap capacity is 2, thread A puts key T1, T2, T3, T4, T5, and T1, T2, and T3 have the same hash value. Create A linked table T1->T2->T3, but T4 and T5have different hash values, so the capacity is insufficient and needs to be rehash. Create A larger hash table to migrate data from the old hash table. At this time, thread B enters and thread A hangs. At this point, thread B finds that the capacity is insufficient and needs to be expanded. At this point, thread B’s linked list after expansion is T1->T2. Then thread B finishes executing, thread A continues executing, and the linked list becomes T2->T1, forming T1. T2.next=T1, so when the user evaluates the key, it gets stuck in an infinite loop and doesn’t respond.
ConcurrenHashmap is a thread-safe hashtable, so why not just use hashtable? Although hashtable is thread safe, hashtable locks the entire hashtable, which is inefficient. ConcurrenHashmap can read data without locking, and achieve Segment locking because its internal structure has the existence of a Segment. The granularity of locks can be kept as small as possible during write operations.