Contents:
- What is ConcurrentHashMap
- Why is there a ConcurrentHashMap
- Source code analysis of ConcurrentHashMap
What is ConcurrentHashMap
The name of ConcurrentHashMap shows that it is a hash table that handles concurrency. It is very similar to HashMap. You can regard it as an extension class of HashMap.
Why is there a ConcurrentHashMap
We know that Hash Map is a non thread safe hash table, and its internal functions are not locked. In the actual development process, there are many maps that need to be processed in the case of concurrency.
Even though the JDK has provided a thread safe hash table such as Hashtable, its implementation is too violent. It adds synchronize to all functions. Although this method can ensure thread safety, the concurrency is very low (all read and write threads use a lock).
It is in this case that the ConcurrentHashMap came into being. It can make the read unlocked and the write only lock the slot to be written.
-----------------------------------
Tips:
Another way to synchronize a map is to use the synchronizedMap in the Collections tool class; Its principle is similar to that of Hashtable. It also uses synchronize to lock its internal mutex objects.
I intercepted part of the code and pasted it out. You can have a look.
1 private static class SynchronizedMap<K,V> 2 implements Map<K,V>, Serializable { 3 private static final long serialVersionUID = 1978198479659022715L; 4 5 private final Map<K,V> m; // Backing Map 6 final Object mutex; // Object on which to synchronize 7 8 SynchronizedMap(Map<K,V> m) { 9 if (m==null) 10 throw new NullPointerException(); 11 this.m = m; 12 mutex = this; 13 } 14 15 SynchronizedMap(Map<K,V> m, Object mutex) { 16 this.m = m; 17 this.mutex = mutex; 18 } 19 20 public int size() { 21 synchronized (mutex) {return m.size();} 22 } 23 public boolean isEmpty() { 24 synchronized (mutex) {return m.isEmpty();} 25 } 26 public boolean containsKey(Object key) { 27 synchronized (mutex) {return m.containsKey(key);} 28 } 29 public boolean containsValue(Object value) { 30 synchronized (mutex) {return m.containsValue(value);} 31 } 32 public V get(Object key) { 33 synchronized (mutex) {return m.get(key);} 34 } 35 36 public V put(K key, V value) { 37 synchronized (mutex) {return m.put(key, value);} 38 } 39 public V remove(Object key) { 40 synchronized (mutex) {return m.remove(key);} 41 } 42 public void putAll(Map<? extends K, ? extends V> map) { 43 synchronized (mutex) {m.putAll(map);} 44 } 45 public void clear() { 46 synchronized (mutex) {m.clear();} 47 } 48 }
Source code analysis of ConcurrentHashMap
As usual, I will introduce it from three aspects: internal classes, constructors and core methods.
Before the introduction, let's take a look at the core data structure of ConcurrentHashMap:
Internal class:
1,Segment:
Its main structure is Segment, which contains the properties and operations commonly used in HashMap. In fact, in general, it is a reentrant lock object that inherits ReentrantLock and wraps HashMap.
1 static final class Segment<K,V> extends ReentrantLock implements Serializable { 2 transient volatile HashEntry<K,V>[] table; 3 transient int count; 4 transient int modCount; 5 transient int threshold; 6 final float loadFactor; 7 8 Segment(float lf, int threshold, HashEntry<K,V>[] tab) { 9 this.loadFactor = lf; 10 this.threshold = threshold; 11 this.table = tab; 12 } 13 14 final V put(K key, int hash, V value, boolean onlyIfAbsent) { 15 // Omit implementation 16 } 17 18 private void rehash(HashEntry<K,V> node) { 19 // Omit implementation 20 } 21 }
Unlike HashMap, HashMap only needs to hash once to calculate the slot position. However, ConcurrentHashMap needs to hash to the Segment of the object first, and then hash to the slot where the data is actually stored.
-----------------------------------
2,HashEntry:
1 static final class HashEntry<K,V> { 2 final int hash; 3 final K key; 4 volatile V value; 5 volatile HashEntry<K,V> next; 6 }
The structure is basically the same as that of HashMap. The difference is that its internal value and next are decorated with volatile to ensure memory visibility, that is, read and write operations are visible to other threads.
Constructor:
1 public ConcurrentHashMap(int initialCapacity, 2 float loadFactor, int concurrencyLevel) { 3 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) 4 throw new IllegalArgumentException(); 5 if (concurrencyLevel > MAX_SEGMENTS) 6 concurrencyLevel = MAX_SEGMENTS; 7 // solve concurrencyLevel Nearest to the power of 2, e.g concurrencyLevel=5，Then and 2^3=8 Recently, then sshift=3，sszie=8 8 int sshift = 0; 9 int ssize = 1; 10 while (ssize < concurrencyLevel) { 11 ++sshift; 12 ssize <<= 1; 13 } 14 // segmentShift and segmentMask Mainly used for element hash 15 this.segmentShift = 32 - sshift; 16 this.segmentMask = ssize - 1; 17 if (initialCapacity > MAXIMUM_CAPACITY) 18 initialCapacity = MAXIMUM_CAPACITY; 19 // Get section lock segment in HashEntry[]size 20 int c = initialCapacity / ssize; 21 if (c * ssize < initialCapacity) 22 ++c; 23 int cap = MIN_SEGMENT_TABLE_CAPACITY; 24 while (cap < c) 25 cap <<= 1; 26 // establish segment 27 Segment<K,V> s0 = 28 new Segment<K,V>(loadFactor, (int)(cap * loadFactor), 29 (HashEntry<K,V>[])new HashEntry[cap]); 30 Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize]; 31 UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0] 32 this.segments = ss; 33 }
Core approach:
1,java.util.concurrent.ConcurrentHashMap#put:
1 public V put(K key, V value) { 2 Segment<K,V> s; 3 if (value == null) 4 throw new NullPointerException(); 5 // calculate key of hash value 6 int hash = hash(key); 7 // unsigned right shift segmentShift Bit (default 16), then&segmentMask(Default 15), and finally get segment Address in memory 8 int j = (hash >>> segmentShift) & segmentMask; 9 // If you get it segment by null 10 if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck 11 (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment 12 // Then initialize segment 13 s = ensureSegment(j); 14 return s.put(key, hash, value, false); 15 }
In fact, this logic is mainly to find the subscript of the segment and then save it to the HashEntry.
2,java.util.concurrent.ConcurrentHashMap.Segment#put:
1 final V put(K key, int hash, V value, boolean onlyIfAbsent) { 2 // Lock it and try again if it is not obtained( scanAndLockForPut) 3 HashEntry<K,V> node = tryLock() ? null : 4 scanAndLockForPut(key, hash, value); 5 V oldValue; 6 try { 7 HashEntry<K,V>[] tab = table; 8 // Calculate incoming hash Which slot should it be in 9 int index = (tab.length - 1) & hash; 10 // Get the header of the corresponding slot 11 HashEntry<K,V> first = entryAt(tab, index); 12 // Traverse the entire linked list 13 for (HashEntry<K,V> e = first;;) { 14 // If this key The slot to be stored already has nodes (the linked list pointer is not empty) 15 if (e != null) { 16 K k; 17 // If key Same overwrite value value 18 if ((k = e.key) == key || 19 (e.hash == hash && key.equals(k))) { 20 oldValue = e.value; 21 if (!onlyIfAbsent) { 22 e.value = value; 23 ++modCount; 24 } 25 break; 26 } 27 // Conditions that point to the next slot and can be cycled all the time 28 e = e.next; 29 } 30 // If this key The slot to be stored has no node (the linked list is empty) 31 else { 32 if (node != null) 33 node.setNext(first); 34 else 35 // Create a new slot 36 node = new HashEntry<K,V>(hash, key, value, first); 37 int c = count + 1; 38 // Capacity expansion beyond the threshold 39 if (c > threshold && tab.length < MAXIMUM_CAPACITY) 40 rehash(node); 41 else 42 // Add the value to the header if the threshold value is not exceeded 43 setEntryAt(tab, index, node); 44 ++modCount; 45 count = c; 46 oldValue = null; 47 break; 48 } 49 } 50 } finally { 51 // Release lock 52 unlock(); 53 } 54 return oldValue; 55 }
-----------------------------------