Jane book accounted for the small Wolf reproduced please indicate the original source, thank you!
Knowledge leads to stillness, and stillness leads to quietness, and stillness leads to safety, and safety to care, and care to attain.
ConcurrentHashMap
In multi-threaded environments, data may be lost when HashMap is used to perform put operations. To avoid this bug, ConcurrentHashMap is strongly recommended to replace HashMap. To have a deeper understanding of ConcurrentHashMap, This article examines the different implementations of ConcurrentHashMap1.7 and 1.8.
1.7 implementation
The data structure
Jdk1.7 uses Segment + HashEntry to implement the structure as follows:
ConcurrentHashMap initializes the Segment array by calculating the size of the Segment array (ssize) and the size of the HashEntry array (CAP) in each Segment. Where ssize is a power of 2, the default value is 16, cap size is also a power of 2, the minimum value is 2, the final result is calculated according to the initialCapacity, the calculation process is as follows:
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;Copy the codeSegment inherits ReentrantLock from the implementation, which provides lock functionality.
Put implementation
Insert data into the Segment array using the hash value of the key. If the Segment is uninitialized, CAS assigns the value to the Segment array. Insert data into the Segment array using the hash value of the key.
Scenario: Thread A and thread B both execute the PUT method on the same Segment object
Thread A (tryLock()) successfully obtains the lock, then inserts the HashEntry object into the corresponding position. 2. Thread B fails to acquire the lock, then execute scanAndLockForPut(). In scanAndLockForPut, tryLock() is repeated, 64 times in a multi-processor environment, 1 times in a single-processor environment. When the tryLock() method is executed more times than the limit, the lock() method is executed to suspend thread B; 3. When thread A completes an insert, it releases the lock using unlock() and wakes thread B to continue.
The size to achieve
Because ConcurrentHashMap can insert data concurrently, it is difficult to calculate elements accurately. The general idea is to count the number of elements in each Segment object and then sum them up. However, the result of this method is not exactly the same. Because when calculating the number of elements in the following segments, data may be inserted or deleted in the Segment already calculated. In implementation 1.7, the following method is adopted:
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}Copy the codeFirst, the number of elements is calculated consecutively without locking, and the number of elements is calculated three times at most: 1. If the results of two calculations are the same, the number of elements calculated is accurate; 2. If the Segment result is different from the previous one, lock each Segment and count the number of elements again.
1.8 implementation
The data structure
In 1.8, the design of Segment overcrowding was abandoned, and Node + CAS + Synchronized was adopted instead to ensure concurrency safety. The structure is as follows:
InitTable () is called to initialize the Node array only when the first put method is executed, as follows:
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<? ,? >[n]; table = tab = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }Copy the codePut implementation
When the put method is used to insert data, the Node array will find the corresponding position according to the hash value of the key, as follows:
1. If the Node at the corresponding location is not initialized, insert the corresponding data through CAS.
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}Copy the code2. If the Node at the corresponding position is not empty and the current Node is not in the moving state, a synchronized lock is applied to the Node. If the hash of the Node is not less than 0, the linked list is traversed to update the Node or a new Node is inserted.
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}Copy the code3. If the node is a TreeBin node, it is a red-black tree structure. Insert the node into the red-black tree using putTreeVal.
else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; }}Copy the codeIf binCount is not 0, the put operation affects the data. If the current number of linked lists reaches 8, the treeifyBin method is used to convert the list to a red-black tree. If oldVal is not empty, the update operation does not affect the number of elements, and the old value is returned.
if (binCount ! = 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! = null) return oldVal; break; }Copy the code5. If a new node is inserted, the addCount() method will try to update the baseCount element number.
The size to achieve
In 1.8, baseCount, a volatile variable, is used to count the number of elements. AddCount () is used to update baseCount when new data is inserted or deleted.
if ((as = counterCells) ! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || ! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); }Copy the code1. When initializing, counterCells are empty. If two threads execute CAS to modify baseCount at the same time, the failed thread will continue to execute the logic in the method body and use CounterCell to record the change in the number of elements.
CellsBusy = cellsBusy = cellsBusy = cellsBusy = cellsBusy = cellsBusy = cellsBusy = cellsBusy = cellsBusy
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break;
}Copy the code3. If the baseCount field fails to be set by CAS, the baseCount field fails to be set by CAS. If the baseCount field succeeds, the baseCount field exits the loop.
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break;Copy the codeThe number of elements is stored in baseCount, and the number of changes to some elements is stored in CounterCell.
public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as ! = null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) ! = null) sum += a.value; } } return sum; }Copy the codeTo get the total number of elements, count baseCount and CounterCell arrays.
I am a small Wolf, if you read the harvest, welcome to like and attention