Differences between HashMap and SynchronizedMap

1.The HashMap thread is not safe2.ConcurrentHashMap in JDK17.In JDK1, concurrency is guaranteed by locking segments8.Where is CAS andsynchronizedTo ensure concurrency3.SynchronizedMap's PUT and GET encapsulate hashMap-related methods and are thread-safe through mutex4.When ConcurrentHashMap is put, CAS and Synchronized are used to ensure thread safety and lightweightCopy the code

JDK1.7 implementation

1.Segment array -> HashEntry array -> HashEntry list2.Read the segment without locking. Write the segment without locking3.Hash twice, once to segment and once to HashEntry headerCopy the code

JDK1.8 implementation

1.Implemented as a Node array plus list or red-black tree2.Collisions will result in linked lists whose number is greater than8It's going to be stored as a red-black tree3.The time complexity of traversing the linked list is O(n), and the time complexity of traversing the red-black tree is O(logN), which is conducive to the scene with a large number of conflictsCopy the code

The Node object

1.Both Val and Next will change during expansion, so they are usedvolatileTo maintain visibility and disallow reordering2.Use next to point to the next Node to handle conflictsCopy the code

Implementation details of PUT in JDK1.8

1.If the Node array is empty, the initTable method is called to initialize the Node array2.If the Node position is empty, that is, there is no conflict, CAS is used to insert the Node3.If the Node position is not empty, a conflict exists, and the Node is addedsynchronizedLock and add to the linked list that Node points to4.If the number of linked list nodes contained in Node is greater than8, the treeifyBin method is called to turn the list into a red-black tree5.If Node already stores data using a red-black tree, a new key-value pair is inserted using the putTreeVal method6.When multiple threads attempt to update the same variable using CAS at the same time, only one thread can update the value of the variable, and all other threads fail. The failed thread is not suspended, but is informed that the contention failed and can try againCopy the code

CAS

1.Compare And Swap, CAS has three arguments: V, E, N (CAS(V, E, N)), if V is equal to E, set V to N; If V and E are different, the current thread does nothing or changes the parameters of V,E, and N and tries again2.The casTabAt method in PUT is actually implemented by calling the compareAndSwapObject method3.Compares whether the I index in the current TAB isnullIf yes, insert Node<K, V>. If no, other threads have changed and no operation is performedCopy the code

Implementation details of GET in JDK1.8

Returns the hash value of the key if the Node array matches the first Node. Otherwise, call next to traverse the linked list or red-black treeCopy the code

Volatile instance

1.Both the array that holds the Node and the variable that represents its lengthvolatileModified, design motivation: Multiple threads operate concurrently, one thread changes through after completionvolatileMake it visible between threads so that other threads can immediately sense changes made by the current threadCopy the code