preface
ConcurrentHashMap is a thread-safe and efficient HashMap. Different JDK versions implement it in slightly different ways, and this article focuses on JDK1.8.
1 Why is ConcurrentHashMap used
HashMap
Is thread unsafe. In a multithreaded environment, putting using HashMap causes an infinite loop.HashTable
Synchronization is inefficient because it uses synchronized for thread safety in almost every way.ConcurrentHashMap
During data modification operations, such as PUT and remove, only one bucket is locked, effectively increasing the concurrent access rate.
2 Main Methods
2.1 the put ()
First on the wave source code to analyze.
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; // no lock when adding to empty bin
}
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(! 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) {
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) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the code
In the first step, a check is performed. If the key or value is null, an exception is thrown. It then gets the hash value and initializes binCount to record the length of the list.
This is an infinite loop. Check whether the table is initialized. If no, initialize the table. (n-1) &hash out the insertion subscript, if there is no data at that location, just put it in. (fh = f.hash) == MOVED If other threads are expanding, help them expand.
// If there is a conflict, go in else
synchronized (f) { // Lock the current head node
if (tabAt(tab, i) == f) { // Check again if the subscript is f node
if (fh >= 0) { // If the hash value of the head node is greater than 0, it is a linked list
binCount = 1;
for (Node<K,V> e = f;; ++binCount) { / / traverse
K ek;
// If the key is the same, determine whether to overwrite the old value
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent)// By default, old values are overwritten
e.val = value;
break;
}
Node<K,V> pred = e;
// Insert into the back
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break; }}}else if (f instanceof TreeBin) { // If it is a red-black tree, insert the data as a red-black tree
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 code
Finally, judge whether the length of the list reaches 8. If the value is 8, determine whether to expand the array. If the array length is less than 64, expand the array. If the array length is greater than 64, the list is converted to a red-black tree.
2.2 the get ()
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))))
returne.val; }}return null;
}
Copy the code
The get method is not locked!
- Empty table, return null;
- Compute the hash value, find the corresponding bucket location, and return value for node, otherwise return null
3 summary
ConcurrentHashMap has a locking mechanism compared with HashMap, which is less efficient, but it is safe in multi-threading and does not cause infinite loops. Compared to HashTable, it locks only one bucket that needs to be accessed, so it is much more efficient. You can choose to use HashMap or ConcurrentHashMap as appropriate.