ConcurrentHashMap (jdk1.7)

1.1 Main member variables

Static final int DEFAULT_INITIAL_CAPACITY = 16; Static final float DEFAULT_LOAD_FACTOR = 0.75f; //Segment final Segment<K,V>[] segments;Copy the code

Paragraph 1.2 Segment

Static final class Segment<K,V> extends ReentrantLock implements Serializable {// List array transient volatile HashEntry<K,V>[] table; //Segment number of elements transient int count; // Transient int modCount; // The Segment will be expanded if the number of elements exceeds this threshold. Transient int threshold; // segment loadFactor, whose value is equivalent to the loadFactor of ConcurrentHashMap final float loadFactor; . }Copy the code
    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
    }
Copy the code

ConcurrentHashMap is an array of segments. Each Segment is a hashmap. This Segment inherits a reentrant lock. Locking one Segment does not affect other Segment reads and writes. Both HashEntry and value are volatile to ensure memory visibility.

1.3 put operation

public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); int hash = hash(key); int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); Return s.hash (key, hash, value, false); return s.hash (key, hash, value); } final V put(K key, int hash, V value, Boolean onlyIfAbsent) {HashEntry<K,V> node = tryLock()? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry<K,V>[] tab = table; int index = (tab.length - 1) & hash; HashEntry<K,V> first = entryAt(TAB, index); for (HashEntry<K,V> e = first;;) { if (e ! = null) {// There is a key K K in the array; 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 {// There is no key if (node! = null) node.setNext(first); else node = new HashEntry<K,V>(hash, key, value, first); int c = count + 1; if (c > threshold && tab.length < MAXIMUM_CAPACITY) rehash(node); Else setEntryAt(TAB, index, node); // Put node in array ++modCount; count = c; oldValue = null; break; }}} finally {// unlock(); } return oldValue; }Copy the code

Locate the Segment based on the hash of the key, lock the Segment, not all segments, and then locate the Segment based on the hash of the key and release the lock.

1.4 get operation

public V get(Object key) { Segment<K,V> s; // manually integrate access methods to reduce overhead HashEntry<K,V>[] tab; int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; Unsafe. getObjectVolatile(segments, u))! // unsafe. getObjectVolatile(segments, u))! = null && (tab = s.table) ! = null) { 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 ((k = e.key) == key || (e.hash == h && key.equals(k))) return e.value; } } return null; }Copy the code

The GET operation is not locked.

1.5 the size method

public int size() { final Segment<K,V>[] 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 the number of retries is greater than 2, then lock every segments 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(); } } return overflow ? Integer.MAX_VALUE : size; }Copy the code

General process:

  1. Iterate through all segments in an infinite loop.
  2. Add the size of each segment to get sum.
  3. Determine whether the sum of this loop is equal to the sum of the last loop. If the sum is equal, it indicates that the size has not changed during this period and directly exits the loop. If the number of retries exceeds the threshold, lock all segments. This ensures that the size of the segment will not change again.
  4. If the lock is unlocked, return size.

From here you can see the idea of optimistic locking, first optimistically assume that the size of the statistical process will not be modified by other threads, if it does change, then try several times, really can not lock again.

ConcurrentHashMap

2.1 Data structure of ConcurrentHashMap?

Jdk1.7:

In essence, a ConcurrentHashMap is an array that stores a Segment, which in turn is a HashMap structure. The Segment inherits a reentrant lock so that the Segment can act as a lock. Each Segment guards buckets of ConcurrentHashMap, each of which is in turn a linked list of HashEntry objects. The ConcurrentHashMap is divided into several parts by using segments, so that each part has a lock. Modifying one part does not affect the modification of other parts at the same time, which is the core idea of Segment locking.

Jdk1.8:

The structure is similar to that of HashMap1.8, which is array + linked list + red-black tree structure. CAS operation and synchronized are used to ensure concurrency safety.

2.2 what is the difference between the put implementation of jdk1.7 and jdk1.8?

Jdk1.8 put the source code:

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); Int hash = spread(key.hashcode ()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; } else if ((fh = f.hash) == MOVED) TAB = helpTransfer(TAB, f); else { V oldVal = null; Synchronized (f) {if (tabAt(TAB, I) == f) {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 key is equal, override value 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; }}} else if (f instanceof TreeBin) { binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! = 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! = null) return oldVal; break; } } } addCount(1L, binCount); return null; }Copy the code

If the node located on the array is empty, CAS operation is used to write data; if there is data, synchronized locks the head node of the linked list to write data.

2.3 What is the difference between ConcurrentHashMap and HashMap?

  • ConcurrentHashMap thread is safe, but HashMap thread is not.
  • ConcurrentHashMap does not allow the storage of null keys and values, and HashMap does allow the storage of null keys and values.

2.4 Why cannot the Key and Value of ConcurrentHashMap be NULL?

Because author Doug Lea doesn’t like null. You cannot tell whether the key has not found a NULL or whether the key has a null value.

Third, summary

In jdk1.8, ConcurrentHashMap abandons Segment Segment locking and adopts CAS and synchronized to ensure thread safety. This is an optimistic locking idea, refining the lock granularity.