对ConcurrentHashMap更深一步认识

ConcurrentHashMap 的存在意义

我们知道，Java中有了HashMap和HashTable 那为何还需要ConcurrentHashMap?

对比HashMap

ConcurrentHashMap 数据存储结构是：数组+链表+红黑树

HashMap 不是线程安全的，不能在多线程场景使用。

两者相同之处:

• 数组、链表结构几乎相同，因此底层对数据结构的操作思路是相同的
• 都实现 Map 接口，多数方法也都是相同的

两者不同之处:

• 红黑树结构略有不同，HashMap的红黑树节点叫做TreeNode,TreeNode不仅有属性还维护着红黑树的结构,比如查找、新增等；ConcurrentHashMap中红黑树拆分成两块,TreeNode仅维护属性和查找功能, 新增TreeBin来维护红黑树的结构，负责根节点的加锁和解锁
• ConcurrentHashMap新增ForwardingNode转移节点,扩容会用到,该节点用来保证扩容时线程安全

对比HashTable

• Hashtable使用synchronized保证线程安全,当一个线程访问其中一个同步方法时，其他线程是不能访问其同步方法(竞争同一把锁)。会导致在put数据时,其他线程也不能get数据之类操作，导致并发效率非常低.
• ConcurrentHashMap使用分段锁(Segment)技术,将数组分成多段,每个分段锁维护着 HashEntry, 修改数据时先将这一段锁起来,其他线程此时要操作其他分段的数据互不干扰. 操作不是同一分段数据, 线程间不存在竞争关系,大大提高并发效率.

ConcurrentHashMap部分源码分析

数据初始化

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //1. 通过死循环来保证一定能初始化成功,通过对sizeCtl变量的赋值来保证只被初始化一次
    while ((tab = table) == null || tab.length == 0) {
        //2. sizeCtl小于0,表示有其他线程正在初始化,释放当前CPU的调度权,重新发起锁的竞争,自旋
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        //3. CAS 赋值,保证当前只有一个线程正在初始化,如果第一次初始化这里会将sizeCtl的值赋值为-1,
        //保证了数组的初始化安全性
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                //4. 可能执行到这里的时候,table已经不为空了,双重check
                if ((tab = table) == null || tab.length == 0) {
                    //5. 初始化数组
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    //>>>：无符号右移,无论是正数还是负数,高位通通补0
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

从上面源码看出使用自旋+CAS+双重check来保证数组初始化时的线程安全.

获取数据：Get

ConcurrentHashMap 读取数据比较简单，先获取数组下标，然后通过判断数组下标的 key 是否与目标 key 一致，相等直接返回。如果下标的槽点是链表或红黑树，分别调用相应的查找数据方法，整体思路和 HashMap 很像

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //计算hashcode
    int h = spread(key.hashCode());
    //不是空的数组 && 并且当前索引的槽点数据不是空的
    //否则该key对应的值不存在，返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //槽点第一个值和key相等，直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //如果是红黑树或者转移节点，使用对应的find方法
        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;
}

扩容机制

ConcurrentHashMap 扩容时机是和HashMap相同，都在put方法最后一步检查一下是否需要扩容.但实现上有差别：

1. 需要把老数组的值全部拷贝到扩容之后的新数组上,先从数组的队尾开始拷贝；
2. 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷贝到新数组时,把原数组槽点赋值为转移节点；
3. 若有新数据正好需要put到此槽点,发现槽点为转移节点,会一直等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化；
4. 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置为转移节点；
5. 直到所有数组数据都拷贝到新数组时,直接把新数组赋值给数组容器,拷贝即完成。