This article is only for my personal understanding. The editor is not in Java, but has a high interest in learning Java.
If there is anything wrong, I hope the boss will give me some advice
The underlying layer of HashMap is array + linked table, (Many people should know)
JDK1.7 is an array + linked table
(1.7 is just an example, in the past, I will take 1.7 as an example)
First is an array, and then the type of the array isLink List
Elements are header insertion method
JDK1.8 is an array + linked list or an array + red and black tree
First is an array, and then the type of the array is a linked table
When the element of the linked list is greater than 8, it will becomeRed and black tree
When the element of the red and black tree is less than 6, it will become a link list
Elements are inserted at the end
The default size of HashMap array is 16
Arrays are also calledHashbucket
(It seems that this value isAlibaba Java Development ManualIt seems to be related)
The subscript of the HashMap element isHashCode(element) & (length of array-1)
HashMap expansion Resize
For capacity expansion, there is a value called loadFactor (threshold), with the default value of 0.75;
When the arrayNumber of elements > array size (default 16) * loadFactor (default 0.75)
The capacity expansion will be triggered, and the capacity expansion is twice the capacity expansion (the default is 16 and it will be 32 after the capacity expansion is 16)
At this time, the subscript of each element will also change (because the length of the array has changed)
Then you need to reassign each element to subscript and re-add it to the linked list or red and black tree
HashMap threads are not safe
When put, Resize (capacity expansion) will cause data overwrite
JDK1.7Because it is a head insertion method, it may cause a circular link table
JDK1.8It's the tail insertion method
How to make it thread-safe using HashMap
Using ConcurrentHashMap,
JDK1.7 is a segmented array, with a Segment lock (inherited from ReentrantLock) to accelerate a small segment guaranteeconcurrent
JDK1.8 is the same as HashMap, array + linked list (or red and black tree)
Synchronized and CAS (compare and swap)
(JVM optimizes Synchronize in 1.6 very well)
CAS is easy to understand, compare and replace
(CAS is a lock-free algorithm. CAS has 3 operands, memory value V, old expected value A, and new value B to be modified. If and only if the expected value A and memory value V are the same, modify the memory value V to B, otherwise do nothing)
(The operation of unlocked modification value can greatly reduce the lock proxyperformanceConsumption. The basic idea of this algorithm is to constantly compare whether the current variable value in memory is equal to the variable value you specified. If it is equal, accept the modified value you specified, otherwise you will reject your operation. Because the value in the current thread is no longer the latest value, your modification may overwrite the result of other threads' modifications. This is similar to the idea of optimism, SVN)
Use HashTable (basically abandoned)
HashTable puts a Synchronized HashMap
()Package
Use synchronized to add, but this is to lock a certain Hash bucket (a value of the array), not to lock the entire map, and other threads can also access it when locking
The editor has learned a lot about this for the time being. I hope the big guy will comment if there are any missing things.