Shulou(Shulou.com)05/31 Report--

This article mainly explains "what's the use of ConcurrentHashMap". Interested friends might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what's the use of ConcurrentHashMap"?

❝HashTable's put, get, remove and other methods are modified by synchronized to ensure its thread safety. HashTable does not allow key and value to be null. The problem is that synchronized is a keyword-level weight lock, and no write operation is allowed when get data is used. The performance is relatively poor. Therefore, ConcurrentHashMap is mainly used to ensure thread safety. ❞

ConcurrentHashMap is mainly divided into two versions of JDK=8. The space utilization of ConcurrentHashMap is generally only 10% to 20%, which is described below.

JDK7

First of all, let's talk about the general composition of JDK7. ConcurrentHashMap is composed of Segment array structure and HashEntry array. Segment is a reentrant lock, an array and linked list structure. A Segment contains an HashEntry array, and each HashEntry is a linked list structure. It is through Segment segmented locking that ConcurrentHashMap achieves efficient concurrency. The disadvantage is that the degree of concurrency is determined by the segment array, and the degree of concurrency cannot be expanded once initialized. First draw a visual picture of ConcurrentHashMap. To understand currentHashMap, it can be simply understood as "sub-table and sub-database" of data. ConcurrentHashMap is composed of Segment array structure and HashEntry array structure.

❝Segment is a subclass of reentrant lock ReentrantLock, which acts as a lock in ConcurrentHashMap, and HashEntry is used to store key-value pair data. ConcurrentHashMap contains a Segment array to achieve lock separation, the structure of Segment is similar to HashMap, a Segment contains an HashEntry array, each HashEntry is a linked list structure element, each Segment guardian an element in the HashEntry array, when modifying the data of the HashEntry array, you must first obtain its corresponding Segment lock. ❞, let's take a look at the segment class: static final class Segment extends ReentrantLock implements Serializable {

Transient volatile HashEntry [] table; / / including a HashMap can be understood as

}

It can be understood that each of our segment is a HashMap that implements the Lock function. If we have multiple segment at the same time to form a segment array, then we can achieve concurrency.

Let's take a look at the constructor of currentHashMap and summarize a few points. The initialization size of table (HashEntry array) contained in each segment must also be the power of 2. Here there are several parameters for bit calculation. InitialCapacity: initial capacity size. Default is 16. LoadFactor: capacity expansion factor. Default is 0.75. When the number of elements stored in a Segment is greater than that of initialCapacity* loadFactor, the Segment will be expanded once. ConcurrencyLevel: concurrency. Default is 16. Concurrency can be understood as the maximum number of threads that can "update" ConccurentHashMap at the same time without lock contention when the program is running, which is actually the number of segmented locks in ConcurrentHashMap, that is, the array length of Segment []. If the concurrency setting is too small, it will bring serious lock competition problems; if the concurrency setting is too large, the access originally located in the same Segment will spread to different Segment, and the CPU cache hit rate will decline, resulting in a decline in program performance. The array size of segment must eventually be the power of 2.

Constructor details:

/ / initialCapacity is the initial value of all the KV data that we save

/ / loadFactor, this is the load factor of HashMap.

/ / initialization size of our segment array

@ SuppressWarnings ("unchecked")

Public ConcurrentHashMap (int initialCapacity

Float loadFactor, int concurrencyLevel) {

If (! (loadFactor > 0) | | initialCapacity

< 0 || concurrencyLevel MAX_SEGMENTS) // 最大允许segment的个数，不能超过 1< 24 concurrencyLevel = MAX_SEGMENTS; int sshift = 0; // 类似扰动函数 int ssize = 1; while (ssize < concurrencyLevel) { ++sshift; ssize >

6)

H + = (h > 16)

}

Get is relatively simple, it is nothing more than finding the corresponding segment through hash, continuing to find the corresponding table through hash, and then traversing the linked list to see if it can be found, and note that get is not locked. Public V get (Object key) {

Segment s

HashEntry [] tab

Int h = hash (key); / / Standard hash value acquisition algorithm in JDK7

Long u = ((h > segmentShift) & segmentMask) > segmentShift) & the segment array position corresponding to the segmentMask; / / hash value bit operation

If (s = (Segment) UNSAFE.getObject

(segments, (j threshold & & tab.length)

< MAXIMUM_CAPACITY) rehash(node); // 扩容 else // 没有达到阈值，将 node 放到数组 tab 的 index 位置， // 将新的结点设置成原链表的表头 setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { // 解锁 unlock(); } return oldValue; } 如果加锁失败了调用scanAndLockForPut，完成查找或新建节点的工作。当获取到锁后直接将该节点加入链表即可，「提升」了put操作的性能，这里涉及到自旋。大致过程： ❝在我获取不到锁的时候我进行tryLock,准备好new的数据，同时还有一定的次数限制，还要考虑别的已经获得线程的节点修改该头节点。❞private HashEntry scanAndLockForPut(K key, int hash, V value) { 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 // 进到这里说明数组该位置的链表是空的，没有任何元素 // 当然，进到这里的另一个原因是 tryLock() 失败，所以该槽存在并发，不一定是该位置 node = new HashEntry(hash, key, value, null); retries = 0; } else if (key.equals(e.key)) retries = 0; else // 顺着链表往下走 e = e.next; } // 重试次数如果超过 MAX_SCAN_RETRIES（单核 1 次多核 64 次），那么不抢了，进入到阻塞队列等待锁 // lock() 是阻塞方法，直到获取锁后返回 else if (++retries >

MAX_SCAN_RETRIES) {

Lock ()

Break

}

Else if ((retries & 1) 0 & &

/ / enter here, indicating that a new element has entered the linked list and become the new header

/ / the strategy here is to re-execute the scanAndLockForPut method

(F = entryForHash (this, hash))! = first) {

E = first = f; / / re-traverse if entry changed

Retries =-1

}

}

Return node

}

Size

This size method is more interesting, it is the first unlocked statistics of all the data to see whether the two times before and after the data are the same, if the same, then return the data, if not, then all the segment to lock, statistics, unlock. And the size method only returns a statistical number, so size is used with caution.

Public int size () {

/ / Try a few times to get accurate count. On failure due to

/ / continuous async changes in table, resort to locking.

Final Segment [] segments = this.segments

Int size

Boolean overflow; / / true if size overflows 32 bits

Long sum; / / sum of modCounts

Long last = 0L; / / previous sum

Int retries =-1; / / first iteration isn't retry

Try {

For (;;) {

If (retries++ RETRIES_BEFORE_LOCK) {/ / all locks are added for more than 2 times

For (int j = 0; j

< segments.length; ++j) ensureSegment(j).lock(); // 直接对全部segment加锁消耗性太大 } sum = 0L; size = 0; overflow = false; for (int j = 0; j < segments.length; ++j) { Segment seg = segmentAt(segments, j); if (seg != null) { sum += seg.modCount; // 统计的是modCount,涉及到增删该都会加1 int c = seg.count; if (c < 0 || (size += c) < 0) overflow = true; } } if (sum last) // 每一个前后的修改次数一样 则认为一样，但凡有一个不一样则直接break。 break; last = sum; } } finally { if (retries >

RETRIES_BEFORE_LOCK) {

For (int j = 0; j < segments.length; + + j)

SegmentAt (segments, j). Unlock ()

}

}

Return overflow? Integer.MAX_VALUE: size

}

The rehash segment array is immutable after initialization, that is, "concurrency immutable", but the table in segment can be expanded by two times, this method does not take concurrency into account, because the lock has been acquired before the method is executed. Among them, the idea of rehash in JDK7 is the same as that of dealing with linked lists after expansion in JDK8, but I don't feel as good as the essence of 8 writes. / / the node on the method parameters is the data that needs to be added to the new array after this expansion.

Private void rehash (HashEntry node) {

HashEntry [] oldTable = table

Int oldCapacity = oldTable.length

/ / 2x

Int newCapacity = oldCapacity

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.