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

  1. HashMapIs thread unsafe. In a multithreaded environment, putting using HashMap causes an infinite loop.
  2. HashTableSynchronization is inefficient because it uses synchronized for thread safety in almost every way.
  3. ConcurrentHashMapDuring 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!

  1. Empty table, return null;
  2. 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.