深入理解ConcurrentHashMap

第五季 2015.7.25

字数：893字时长：4分钟

基本认识

　　ConcurrentHashMap是一种线程安全的HashMap。它是基于分段锁技术的Map实现类，即对分段加锁同步以期在多线程环境下快速达到插入数据的一致性，因此只有在同一个分段内才存在竞态关系，不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计，分段锁大大的提高了高并发环境下的处理能力。但同时，由于不是对整个Map加锁，导致一些需要扫描整个Map的方法（如size(), containsValue()）需要使用特殊的实现，另外一些方法（如get()、clear()）甚至放弃了对一致性的要求，因此ConcurrentHashMap是弱一致性的。
　　ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构，一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。ConcurrentHashMap中的HashEntry相对于HashMap中的Entry有一定的差异性：HashEntry中的value以及next都被volatile修饰，这样在多线程读写过程中能够保持它们的可见性，从如下源码片段可有个大概了解：

static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;

　　与HashMap不同的是，ConcurrentHashMap并不允许key或者value为null，按照作者Doug Lea的说法，这么设计的原因是因为在ConcurrentHashMap中，一旦value出现null，则代表HashEntry的key/value没有映射完成就被其他线程所见，而并不只是简单的空值而已。
Doug Lea为util.concurrent包的作者。

Unsafe与CAS

　　在ConcurrentHashMap中，随处可以看到U, 大量使用了U.compareAndSwapXXX的方法，这个方法是利用一个CAS算法实现无锁化的修改值的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。
　　Unsafe代码块控制了一些属性的修改工作，比如最常用的SIZECTL 。在ConcurrentHashMap中，大量应用了CAS方法进行变量、属性的修改工作。利用CAS进行无锁操作，可以大大提高性能。

// Unsafe mechanics
    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
    private static final long SIZECTL;
    private static final long TRANSFERINDEX;
    private static final long BASECOUNT;
    private static final long CELLSBUSY;
    private static final long CELLVALUE;
    private static final int ABASE;
    private static final int ASHIFT;

    static {
        try {
            SIZECTL = U.objectFieldOffset
                (ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
            TRANSFERINDEX = U.objectFieldOffset
                (ConcurrentHashMap.class.getDeclaredField("transferIndex"));
            BASECOUNT = U.objectFieldOffset
                (ConcurrentHashMap.class.getDeclaredField("baseCount"));
            CELLSBUSY = U.objectFieldOffset
                (ConcurrentHashMap.class.getDeclaredField("cellsBusy"));

            CELLVALUE = U.objectFieldOffset
                (CounterCell.class.getDeclaredField("value"));

            ABASE = U.arrayBaseOffset(Node[].class);
            int scale = U.arrayIndexScale(Node[].class);
            if ((scale & (scale - 1)) != 0)
                throw new Error("array index scale not a power of two");
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (ReflectiveOperationException e) {
            throw new Error(e);
        }

        // Reduce the risk of rare disastrous classloading in first call to
        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
        Class<?> ensureLoaded = LockSupport.class;
    }