Java中的Map【十二】ConcurrentHashMap 类

淩亂°似流年 2021-09-21 09:42 315阅读 0赞

**          所使用的jdk版本为1.8.0\_172版本**，先看一下 ConcurrentHashMap<K,V> 在JDK中Map的类图中的主要继承实现关系：

![20200726165324662.png][]

# 概述 #

我们知道Java中的 HashMap 是线程不安全的（比如数组table扩容、put 操作多线程下值覆盖等都会导致数据不一致问题），ConcurrentHashMap 就是为了解决这个问题存在的。ConcurrentHashMap 数据结构大致是由Node数组+Node链表+TreeBin红黑树结构组成。相比于JDK7，JDK8 ConcurrentHashMap里面更多地使用CAS操作，使用锁（synchronized）时也是对Node进行加锁，锁的粒度更小。另外需要注意的是，ConcurrentHashMap 是不支持 key 或者 value 为 null 的，而 HashMap 是支持的。

# 数据结构 #

**Node<K,V>** 节点，注意使用 volatile 修饰 V val，这保证了可见性，但值value被修改时，其他线程能得到最新的修改值：

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            //使用 volatile 修饰， 保证多线程下值V的可见性:线程A修改，线程B能立刻感知到，这也是get(K k)方法不用加锁原因
            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;
            }

**  TreeBin<K,V>** 类继承了 Node<K,V>，内部指向了一个红黑树的实现（节点为 TreeNode 类型）和一个读写锁值：

static final class TreeBin<K,V> extends Node<K,V> {
            TreeNode<K,V> root;
            volatile TreeNode<K,V> first;
            volatile Thread waiter;
            volatile int lockState;
            // values for lockState
            static final int WRITER = 1; // set while holding write lock 持有写锁状态
            static final int WAITER = 2; // set when waiting for write lock 等待写锁
            static final int READER = 4; // increment value for setting read lock 设置读锁的增量值
    
            .......

# 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();
            // 混淆 hashCode,得到 hash 值
            int hash = spread(key.hashCode());
            // binCount:链表节点数目
            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();//table 数组初始化
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    //key 在数组上的哈希索引位置节点为null
                    //这种情况 cas 把 key-value 放在该位置上，不需要加锁
                    // cas 成功，跳出for循环；cas 失败，进到下一次循环，就走到下面的 if-else 分支了
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                // 如果table数组上的节点（链表头节点/树的根结点）hash值为-1，表示数组在进行扩容迁移数据，这个数组索引位置上的节点数据正在进行迁移
                // 帮助迁移节点数据到 nextTable[] 数组
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                else {
                    V oldVal = null;
                    //synchronized修饰链表头节点/红黑树根结点
                    synchronized (f) {
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {//hash 值大于0，说明是链表节点
                                binCount = 1;
                                for (Node<K,V> e = f;; ++binCount) {
                                    K ek;
                                    // key 已存在的情况，替换value值
                                    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;
                                    // key 不存在的情况，尾插法插入
                                    if ((e = e.next) == null) {
                                        pred.next = new Node<K,V>(hash, key,
                                                                  value, null);
                                        break;
                                    }
                                }
                            }
                            // 如果数组索引位置节点为TreeBi，表明是红黑树结构
                            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) {
                        // 链表节点数目超过8且table数组的长度大于64，才会把链表转化为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        // key-value 已经存在的情况，返回旧值即可，不影响size
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            // 新插入不存在的key-value的情况，需要计数器 + 1，用于计算当前Map的size
            // 还要检查是否需要数组扩容以及迁移数据
            addCount(1L, binCount);
            return null;
        }

put 方法，首先用混淆函数得到 key 的 hash 值，Node数组table为空，会进行数组的初始化【*注意：Node<K,V>\[\] table 使用volatile修饰，保证数组修改的可见性*】，initTable() 方法内部采用CAS操作保证只有一个线程进行数组初始化，其他线程自旋 Thread.yield() ，直至ConcurrentHashMap初始化完成。初始化之后，会根据hash 值找到 key 在数组上的索引位置【(n - 1) & hash 也即 hash % n】，通过cas把要插入的key,value放在数组索引位置上。如果失败，表明这个位置已被其它线程放入了值，则会进到下一层循环。此时如果 else if((fh ==f.hash) == MOVED)，表明当前map正在扩容迁移数据，当前线程会加入帮助迁移数据，MOVED 的值为 -1，因为数组在扩容迁移数据的时候，每个线程分段帮助迁移数据的同时会把数组位置头节点（ForwardingNode，Node的子类）的hash值设为-1。 如果当前没有扩容，则进入else 分支中，通过对数组位置头节点Node加锁，在链表或者红黑树中查找key，插入或者替换旧值。

put 操作时，如果链表节点数目超过8并且数组table的长度大于64，才会把链表结构转换为红黑树结构。至于为什么是8，是因为根据泊松分布统计学得到的数值。

put 最后，addCount 方法用于计算map中的键值对数量，同时检查键值对数量是否超过了阈值，是否需要进行数组扩容以及迁移操作。计算size时，如果使用锁实现计数器，则高并发下势必会有大量线程抢夺锁，影响计数器性能。ConcurrentHashMap中使用CounterCell数组和基本计数器baseCount，baseCount的值加上CounterCell数组元素值之和就是键值对总数。通过这种方式用CAS代替了锁，具体细节还要再研究下。

## size()方法 ##

/**
         * {@inheritDoc}
         * 基准数值累加CounterCell[]数组中每个值，即为map中的键值对个数
         * 可以理解为，为了防止多个线程竞争计数器，把每个线程的变更数映射到CounterCell[]数组的不同位置上
         */
        public int size() {
            long n = sumCount();
            return ((n < 0L) ? 0 :
                    (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                    (int)n);
        }
    
        final long sumCount() {
            CounterCell[] as = counterCells; CounterCell a;
            long sum = baseCount;
            if (as != null) {
                for (int i = 0; i < as.length; ++i) {
                    if ((a = as[i]) != null)
                        sum += a.value;
                }
            }
            return sum;
        }

##    get 方法 ##

/**
         * Returns the value to which the specified key is mapped,
         * or {@code null} if this map contains no mapping for the key.
         * 返回指定键所映射到的值，如果此映射不包含该键的映射关系，则返回 null。
         *
         * <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.)
         * 更确切地讲，如果此映射包含满足从键 k 到值 v 的映射关系 key.equals(k)，则此方法返回 v；
         * 否则它返回 null。（最多只能有一个这样的映射关系）。
         *
         * @throws NullPointerException if the specified key is null 如果指定键为 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());
            //先定位key在table[]的位置
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null) {
                if ((eh = e.hash) == h) {
                    // table数组位置节点就是key，返回值val
                    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                        return e.val;
                }
                //数组位置节点的hash值为负数，则可能数组在扩容或者头节点结构为红黑树
                //两种情况分别对照Node子类ForwardingNode 和 TreeBin 中的覆盖方法实现
                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;
        }

get 方法的实现就比较简单了，因为Node中value使用的volatile关键字保证可见性，也不需要加锁。

ConcurrentHashMap虽然复杂但是设计得很巧妙，里面数组数据迁移方法 helpTransfer(tab, f)，以及上面的CounterCell数组的使用还有些不清楚的地方后续还需要仔细理解一下。

[20200726165324662.png]: /images/20210920/abab19583b8a4e87bfa40ff78917298f.png