ConcurrentHashMap（基于jdk1.8）

水深无声 2024-04-19 08:13 41阅读 0赞

### ConcurrentHashMap（基于jdk1.8） ###

[之前写过关于HashMap和HashTable的区别][HashMap_HashTable]

1.  HashMap 无锁 ConcurrentHashMap是有锁的

ConcurrentHashMap结构介绍

/*Key-value entry. This class is never exported out as a user-mutable Map.Entry (i.e., one supporting setValue; see MapEntry below), but can be used for read-only traversals used in bulk tasks. Subclasses of Node with a negative hash field are special, and contain null keys and values (but are never exported). Otherwise, keys and vals are never null.*/
    /*译：键值结构。这个类不可以导出成为一个用户可变的Map.Entry。但是可以在批量任务中做只读遍历。是一个具有负的hash值的特殊子类。并且包含null的值和键（但是不能导出），否则，键和值不可为空。*/
    static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            volatile V val;
            volatile Node<K,V> next;
    
            Node(int hash, K key, V val, Node<K,V> next) { 
                this.hash = hash;
                this.key = key;
                this.val = val;
                this.next = next;
            }
    
            public final K getKey()       {  return key; }
            public final V getValue()     {  return val; }
            public final int hashCode()   {  return key.hashCode() ^ val.hashCode(); }
            public final String toString(){  return key + "=" + val; }
            public final V setValue(V value) { 
                throw new UnsupportedOperationException();
            }
    
            public final boolean equals(Object o) { 
                Object k, v, u; Map.Entry<?,?> e;
                return ((o instanceof Map.Entry) &&
                        (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                        (v = e.getValue()) != null &&
                        (k == key || k.equals(key)) &&
                        (v == (u = val) || v.equals(u)));
            }
    
            /** * Virtualized support for map.get(); overridden in subclasses. */
            Node<K,V> find(int h, Object k) { 
                Node<K,V> e = this;
                if (k != null) { 
                    do { 
                        K ek;
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                    } while ((e = e.next) != null);
                }
                return null;
            }
        }

#### 底层实现采用的是Node和红黑树（[红黑树][Link 1]）以及cas实现的 ####

*  首先来看一下get方法

/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code key.equals(k)}, * then this method returns {@code v}; otherwise it returns * {@code null}. (There can be at most one such mapping.) * * @throws NullPointerException if the specified key is null */
        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;
        }

看一下这个spread方法是干啥的？

在Java 8 中求hash的方法从hash改为了spread。Key的hashCode值与其高16位作异或并保证最高位为0（从而保证最终结果为正整数）。

(tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null

/**
         * The array of bins. Lazily initialized upon first insertion.
         * Size is always a power of two. Accessed directly by iterators.
         */
        transient volatile Node<K,V>[] table;

看一下这个比较条件

> tab 局部变量的Node数组 table是一个全局的Node数组 被transient 修饰的属性如果实现的是Serializable接口则不被序列化 volatile 保证了 table的可见性，也就是任意一个线程对table做了修改他会马上同步到主存中
> 
>     e=tabAt(tab, (n - 1) & h)) 作用是获取首节点的的Node元素
> 
> 也就是说如果table不为null且 长度大于0 且首节点不为空，那么就继续判断
> 
>     if ((eh = e.hash) == h) { 
>         if ((ek = e.key) == key || (ek != null && key.equals(ek)))
>             return e.val;
>     }
> 
> 这个的意思的如果获取到的e节点的hash值等于要获取值的hash值，那么就判断key值是否相同（hash冲突）如果满足则返回valu值
> 
>     else if (eh < 0)
>         return (p = e.find(h, key)) != null ? p.val : null;
> 
> hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来  
> eh=-1，说明该节点是一个ForwardingNode，正在迁移，此时调用ForwardingNode的find方法去nextTable里找。  
> eh=-2，说明该节点是一个TreeBin，此时调用TreeBin的find方法遍历红黑树，由于红黑树有可能正在旋转变色，所以find里会有读写锁。  
> eh>=0，说明该节点下挂的是一个链表，直接遍历该链表即可。

*  put方法

public V put(K key, V value) { 
            return putVal(key, value, false);
        }
    
        /** Implementation for put and putIfAbsent */
        final V putVal(K key, V value, boolean onlyIfAbsent) { 
            if (key == null || value == null) throw new NullPointerException();//值和value不可以为null
            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)    //如果为空初始化table
                    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)     // 如果当前结点为forwarding则帮助扩容
                                                     
                    tab = helpTransfer(tab, f);
                else { 
                    V oldVal = null;
                    synchronized (f) {                       // 如果非forwarding且非null则加锁
                        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;
        }

[HashMap_HashTable]: https://blog.csdn.net/ProgramMonika/article/details/86629892
[Link 1]: https://blog.csdn.net/ProgramMonika/article/details/100642460