This is the 21st day of my participation in the August Text Challenge.More challenges in August
This article is from chaoCode, chaoCode, chaoCode, chaoCode and chaoCode.
Violators, the author reserves the right to pursue.
preface
ConcurrentHashMap (JDK1.7 and JDK1.8)
Hash table
introduce
Hash table is a key-valued data storage structure. We can find the corresponding value by inputting the value to be searched, that is, key.
The idea of hashing is simple: if all keys are integers, you can use a simple unordered array: the key is the index, and the value is the corresponding value, so that you can quickly access the value of any key. This is the case for simple keys, and we extend it to handle more complex types of keys.
Chained hash table
A chained hash table is basically a set of linked lists. Each list can be thought of as a bucket, and we hash all the elements into specific buckets. When an element is inserted, its key is first passed to a hash function (a process called hash keys) that hashes it to tell it which bucket it belongs to, and then inserts the element in the corresponding list header. To find or delete an element, find the bucket of the element in the same way, and then iterate through the corresponding linked list until we find the element we want. Because each bucket is a linked list, a chained hash table does not limit the number of elements it can contain. However, if the table becomes too large, its performance will degrade.
Application scenarios
At the heart of familiar caching techniques such as Redis and memcached is the maintenance of a large hash table in memory, as well as applications such as HashMap and CurrentHashMap.
ConcurrentHashMap and HashMap
HashMap
We know that HashMap is not thread-safe, and in a multi-threaded environment, putting with HashMap causes an infinite loop that leads to CPU utilization approaching 100%, so we cannot use HashMap in concurrent situations.
HashTable
HashTable and HashMap are implemented in much the same way, except that they differ
- HashTable does not allow null keys and values
- HashTable is thread-safe
However, the implementation cost of HashTable thread-safe strategy is too high. It is simple and crude. All related operations of get/put are synchronized, which is equivalent to adding a large lock to the entire HashTable.
In multithreaded access, as long as one thread accesses or manipulates the object, the other threads can only block, which is equivalent to serializing all operations, resulting in poor performance in a highly competitive concurrent scenario.
ConcurrentHashMap
It is mainly designed to deal with the insecurity of HashMap in concurrent environment. The design and implementation of ConcurrentHashMap is very clever, and a large number of lock-free technologies such as volatile, final and CAS are used to reduce the impact of lock competition on performance.
We all know that a Map is an array + a linked list structure.
The implementation principle of CurrentHashMap in JDK1.7
In JDK1.7, ConcurrentHashMap is implemented by array +Segment+ Segment lock.
The Segment lock in ConcurrentHashMap is called a Segment, which is similar to a HashMap structure and contains an array of entries. Each element in an array is a linked list and a ReentrantLock (the Segment inherits ReentrantLock).
2. Internal structure
ConcurrentHashMap uses the segmented locking technology to divide data into segments and assign a lock to each segment of data. When a thread uses the lock to access one segment of data, the data in other segments can also be accessed by other threads, achieving real concurrent access. The internal structure of ConcurrentHashMap is shown below:
The first Hash goes to the Segment, and the second Hash goes to the head of the list that the element is in.
3. Advantages and disadvantages of this structure: The side effect of this structure is that the Hash process is longer than normal HashMap benefits: Lock the Segment in which the element resides. In the best case, lock the Segment where the element resides. ConcurrentHashMap can support writes of the maximum number of segments at the same time (just as these writes are evenly distributed across all segments).
Therefore, the concurrency capability of ConcurrentHashMap can be greatly improved by using this structure.
The implementation principle of CurrentHashMap in JDK1.8
In JDK8, ConcurrentHashMap refers to the implementation of JDK8 HashMap, and adopts the implementation of array + linked list + red-black tree to design. A large number of internal CAS operations are used. Here I briefly introduce CAS.
CAS stands for compare and swap, as we call it. Cas is a lock-based operation, and it is optimistic locking. In Java, there are optimistic locks and pessimistic locks. Pessimistic locking means that a resource is locked until the next thread can access it after the previous thread has released the lock. Optimistic locking, which takes a broad approach and processes resources in some way without locking, such as fetching data by adding version to records, has a significant performance improvement over pessimistic locking.
The CAS operation contains three operands — the memory location (V), the expected old value (A), and the new value (B). If the value in the memory address is the same as the value of A, then the value in memory is updated to B. CAS fetches data through an infinite loop. If thread A gets the address in the first loop and the value in the address is changed by thread B, then thread A needs to spin until the next loop is executed.
In JDK8, the Segment is completely abandoned in favor of Node, and the design concept is no longer the Segment locking concept in JDK1.7.
Node: data structure that stores keys, values, and hash values for keys. Value and next are volatile to ensure concurrent visibility.
The structure of ConcurrentHashMap in JDK8 is very complicated due to the introduction of red-black tree. As we all know, red-black tree is a binary search tree with excellent performance, and its search performance is O (logN). However, the implementation process is also very complex, and the readability is very poor. Doug Lea’s thinking ability is really not as good as that of ordinary people. In the early stage when the linked list structure was fully adopted, the search time complexity of Map was O (N). ConcurrentHashMap in JDK8 converts lists to red-black trees when their length exceeds a certain threshold to further improve lookup performance.
conclusion
The ConcurrentHashMap data structure is similar to that of HashMap. ConcurrentHashMap only adds synchronous operations to control concurrency. From ReentrantLock+Segment+HashEntry in JDK1.7 to synchronized+CAS+HashEntry+ red-black tree in JDK1.8
- Data structure: Remove Segment locking and replace it with arrays, linked lists, and red-black trees.
- Ensure thread-safe mechanism: JDK1.7 uses segment locking mechanism to achieve thread-safe, where segments inherit from ReentrantLock. JDK1.8 adopts CAS+Synchronized to ensure thread safety.
- Lock granularity: Lock each element of array (Node) from Segment where data is to be manipulated.
- Conversion of linked list to red-black tree: The simplification of hash algorithm for locating nodes will bring disadvantages and aggravate hash conflicts. Therefore, when the number of linked list nodes is larger than 8, the linked list will be converted to red-black tree for storage.
- Query time complexity: from traversal list O(n) to traversal red-black tree O(logN).
Thank you for watching, if there is a mistake in the article, welcome to the comment section to communicate. If this article has helped you, please like it at 👍.