In the interview, I often ask about JUC. The common one is CHM. Let's talk about the methods and operations of different versions of CHM
The underlying implementation of CHM in JDK7 is implemented by segmented segment array. Segment contains hashentries, and each HashEntry forms a linked list.
Common get methods:
- First, obtain the lock of segment;
- Then locate the position of the specific bucket according to the Hash algorithm;
- If the bucket is not empty, and according to the judgment, the first node is the position to be inserted, directly replace the old value;
- Otherwise, traverse and search one by one. If there is no conflict, create a new node for header insertion,
- If the bucket is empty, create a node and insert it directly;
- Then judge whether the current node number exceeds the limit value and expand the capacity
- Then base + 1,
- Finally, you need to release the Lock, because segment inherits the Lock lock to prevent blocking.
//This is the put method in Segment
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//The lock that needs to go back to segment is implemented here
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
//table array of current Segment
HashEntry<K,V>[] tab = table;
//Perform Hash calculation and find the subscript of the HashEntry array
int index = (tab.length - 1) & hash;
//The first HashEntry node at the current subscript location
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
//If the first node is not empty
if (e != null) {
K k;
//If the first node is the node to be inserted, replace the value value, otherwise continue to look backward
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
//Replace the original value
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
//If there are no nodes in the current location
//Or the current linked list has been traversed and no equal key has been found
else {
//If it is not empty, insert it directly
if (node != null)
node.setNext(first);
//Otherwise, create a new node and insert the header
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
//If the element in the current Segment is greater than the threshold and the tab length does not exceed the maximum capacity, the capacity will be expanded
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
//Update count value
count = c;
oldValue = null;
break;
}
}
} finally {
//ReentrantLock must be unlocked manually
unlock();
}
return oldValue;
}
}
get method:
Relatively simple
- Calculate the position of segment according to Hash
- Judge whether it is empty, judge whether the linked list is empty, and then traverse the linked list
- It is returned according to the search result. If it does not return null, it is OK
Because the value attribute in HashEntry is decorated with volatile keyword to ensure memory visibility, it is the latest value every time it is obtained.
The get method of ConcurrentHashMap is very efficient because the whole process does not need to be locked.
public V get(Object key) {
Segment<K,V> s;
HashEntry<K,V>[] tab;
//Calculate hash value
int h = hash(key);
//First locate the Segment where the key is located
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
//If the Segment is not empty and the linked list is not empty, traverse the lookup node
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
//If it is found, it returns its value value; otherwise, it returns null
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
Common methods of JDK8
The CHM in JDK8 has become different from the original. The data structure is implemented by Node array + linked list + red black tree. Instead of using segmented lock, the optimized synchronized+CAS is used for concurrency.
Steps of the put method:
final V putVal(K key, V value, boolean onlyIfAbsent) {
//The first thing you can see is that null values are not allowed
if (key == null || value == null) throw new NullPointerException();
//Calculate Hash
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//Judge whether CHM is empty
if (tab == null || (n = tab.length) == 0)
//Only one thread can be initialized
tab = initTable();
//If it has been initialized, calculate the index according to the Hash to see if the table[index] is empty
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//If it is empty, CAS inserts a new node, and only one node succeeds
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
//If the bucket is not empty, judge whether the node Hash is MOVDE(-1) and whether to expand the array
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//Otherwise, lock to ensure thread safety
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
//Traverse to find whether there is a node with conflicting key, and directly replace the node value
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 not found, create a new node tail insert
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//Judge whether it is a tree node
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;
}
}
}
}
if (binCount != 0) {
//Judge whether the number of nodes is greater than or equal to 8, otherwise carry out red black tree conversion
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//If there is no abnormality, increase the number of nodes
addCount(1L, binCount);
return null;
}
get method:
- Calculate Hash value according to key
- If the table is not empty and a specific bucket is found, traverse and find it
- Otherwise, the tree is traversed
- Otherwise, the linked list will be traversed, and the query will return if any. Otherwise, null will be returned
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Another is how JDK7 calculates size:
- The calculation is carried out in an optimistic way. It is assumed that there is no operation to modify the segment structure during the calculation, but if it occurs, it will be retried. If two retries fail, all segments will be locked, and then the size will be calculated to determine the exact size.