Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about the JAVA concurrent container ConcurrentHashMap 1.7 and 1.8 source code, the article is rich in content and professional analysis and description for you, I hope you can get something after reading this article.

HashMap is a thread-safe class, which will cause a lot of problems in the case of concurrency. For more information, please see HashMap source code parsing; HashTable is a thread-safe class, but it uses synchronized to ensure thread safety, which is very inefficient in the case of fierce thread competition. ConcurrentHashMap is introduced in jdk1.5, which is also a thread-safe class, which uses segmented locking technology to improve the efficiency of concurrent access.

The reason why the HashTable container is inefficient in the highly competitive concurrent environment is that all threads accessing HashTable must compete for the same lock. If there are multiple locks in the container, and each lock is used to lock part of the data in the container, then when multiple threads access the data of different data segments in the container, there will be no lock competition between threads, which can effectively improve the efficiency of concurrent access. This is the lock segmentation technique used by ConcurrentHashMap.

In jdk1.7 and before, ConcurrentHashMap is composed of Segment array structure and HashEntry array structure, and then adopts the same structure as HashMap.

ConcurrentHashMap jdk1.7 structure diagram

It is composed of Segment array structure and HashEntry array structure, and the size of Segment array is the concurrency degree of ConcurrentHashMap. Segment inherits from ReentrantLock, so he is a lock himself. Once the Segment array is initialized, it will not be expanded, which is why jdk1.8 removed it. Segment also contains a table array, which can be expanded.

As shown in the figure, we need to address the key hash value twice when locating the data, finding the location in the Segment array for the first time and the location in the table array for the second time.

The Segment class / / inherits directly from ReentrantLock, so a Segment itself is a lock static final class Segment extends ReentrantLock implements Serializable {/ / table array transient volatile HashEntry [] table; / / the number of elements in a Segment transient int count; / / expansion threshold transient int threshold; / / expansion factor final float loadFactor; Segment (float lf, int threshold, HashEntry [] tab) {this.loadFactor = lf This.threshold = threshold; this.table = tab;}.

We found that Segment inherits directly from ReentrantLock, so a Segment itself is a lock. Therefore, the length of the Segment array directly affects the concurrency of ConcurrentHashMap. In addition, each Segment maintains the expansion threshold and expansion factor separately, so the expansion operation of each Segment is completely independent and does not interfere with each other.

The HashEntry class static final class HashEntry {/ / immutable final int hash; final K key; / / volatile ensures visibility so that we do not have to lock volatile V value; volatile HashEntry next; HashEntry (int hash, K key, V value, HashEntry next) {this.hash = hash; this.key = key; this.value = value; this.next = next during get operation. }.} Constructor public ConcurrentHashMap (int initialCapacity, float loadFactor, int concurrencyLevel) {/ / Parameter check if (! (loadFactor > 0) | | initialCapacity

< 0 || concurrencyLevel MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // Find power-of-two sizes best matching arguments // 等于ssize从1向左移位的 次数 int sshift = 0; int ssize = 1; // 找出最接近concurrencyLevel的2的n次幂的数值 while (ssize < concurrencyLevel) { ++sshift; ssize segmentShift) & segmentMask; if ((s = (Segment)UNSAFE.getObject // nonvolatile; recheck (segments, (j >

10); h + = (h > 6); h + = (h > 16);}

The general idea of this method is to get the hashCode of key first, and then hash the value.

Segment.put () method final V put (K key, int hash, V value, boolean onlyIfAbsent) {/ / 1. Lock HashEntry node = tryLock ()? Null: / / scanAndLockForPut query whether key exists without acquiring the lock, and create a new Node scanAndLockForPut (key, hash, value) if it does not exist; V oldValue; try {HashEntry [] tab = table; / / determine the position of the element on the tabl array int index = (tab.length-1) & hash; HashEntry first = entryAt (tab, index) For (HashEntry e = first;;) {if (e! = null) {K k / / if there is a value in the original position and the key is the same, then directly replace the original value if ((k = e.key) = = key | | (e.hash = = hash & & key.equals (k) {oldValue = e.value If (! onlyIfAbsent) {e.value = value; + + modCount;} break;} e = e.next } else {if (node! = null) node.setNext (first); else node = new HashEntry (hash, key, value, first); / / Total number of elements plus one int c = count + 1 / / determine whether to expand if (c > threshold & & tab.length)

< MAXIMUM_CAPACITY) rehash(node); else setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { unlock(); } return oldValue;} 大致过程是： 加锁 定位key在tabl数组上的索引位置index，获取到头结点 判断是否有hash冲突 如果没有冲突直接将新节点node添加到数组index索引位 如果有冲突，先判断是否有相同key 有相同key直接替换对应node的value值 没有添加新元素到链表尾部 解锁 这里需要注意的是scanAndLockForPut方法，他在没有获取到锁的时候不仅会通过自旋获取锁，还会做一些其他的查找或新增节点的工，以此来提升put性能。 Segment.scanAndLockForPut() 方法private HashEntry scanAndLockForPut(K key, int hash, V value) { //定位HashEntry数组位置，获取第一个节点 HashEntry first = entryForHash(this, hash); HashEntry e = first; HashEntry node = null; //扫描次数，循环标记位 int retries = -1; // negative while locating node while (!tryLock()) { HashEntry f; // to recheck first below // 表示遍历链表还没有结束 if (retries < 0) { if (e == null) { if (node == null) // speculatively create node // 完成新节点初始化 node = new HashEntry(hash, key, value, null); // 完成链表的遍历，还是没有找到相同key的节点 retries = 0; } // 有hash冲突，开始查找是否有相同的key else if (key.equals(e.key)) retries = 0; else e = e.next; } // 断循环次数是否大于最大扫描次数 else if (++retries >

MAX_SCAN_RETRIES) {/ / spin acquisition lock lock (); break } / / cycle once every interval to check whether the first node has changed else if ((retries & 1) = = 0 & & (f = entryForHash (this, hash))! = first) {/ / first node has changed, update first, rescan e = first = f; / / re-traverse if entry changed retries =-1 }} return node;}

The scanAndLockForPut method finishes finding or creating a new node without the current thread acquiring the segment lock. When the lock is acquired, the node can be added to the linked list directly, which improves the performance of put operation. General process:

Locate the index bit of key in the HashEntry array and get the first node

Try to acquire the lock and return directly if you succeed, otherwise enter the spin

Determine whether there is a hash conflict and complete the initialization of the new node directly.

If there is a hash conflict, start traversing the linked list to see if there is the same key

If the same key is not found, initialize the new node

If the same key is found, determine whether the number of cycles is greater than the maximum number of scans.

If the number of cycles is greater than the maximum number of scans, CAS directly takes the lock (blocking type).

If the number of cycles is not greater than the maximum number of scans, determine whether the head node has changed.

Enter the next cycle

Segment.rehash () capacity expansion method private void rehash (HashEntry node) {/ / copy old array HashEntry [] oldTable = table; int oldCapacity = oldTable.length; / / table array expansion 2x int newCapacity = oldCapacity > > segmentShift) & segmentMask)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.