阅读笔记:ConcurrentHashMap

我们知道HashMap不是Thread-safe的,而HashTable内部采取了同步操作,是线程安全的。然而有趣的是你去看HashTable的文档,它会建议你:如果不要Thread-Safe你就用HashMap吧,否则你用ConcurrentHashMap好了。

一般如果对线程安全有要求,我们有如下的一些选择:

  • ConcurrentHashMap
  • Hashtable
  • Collections.synchronizedMap

Collections.synchronizedMap

这个实现很粗暴,实际上就是将Map的各个操作都进行了包装和同步:

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
    private final Map<K,V> m;     // Backing Map
    final Object      mutex;  

    SynchronizedMap(Map<K,V> m) {
        this.m = Objects.requireNonNull(m);
        mutex = this;
    }

在构造函数中传入了原来的Map,以及一个对象锁(如果不传那就默认是this了)。然后,所有的操作都进行了同步处理:

public boolean containsValue(Object value) {
    synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
    synchronized (mutex) {return m.get(key);}
}
// ...

HashTable

HashTable实现线程安全的方式与上面有些类似,对所有需要同步的地方直接进行了同步:

public synchronized int size() {
    return count;
}

那么HashMap和HashTable有什么区别呢?除了同步之外,总结下来有以下几点:

  • HashMap允许一个null的key,value也可以为null;但是HashTable不允许null作为key或者value
  • HashMap是JDK1.2才引入的
  • HashTable是基于Dictionary接口实现的

HashTable(以及ConcurrentHashMap)都是不允许null值作为Key和Vaule的,主要的原因是因为要支持并发,假设调用get(key)得到了null,你是不能确认是key不存在,还是说存在但是值为null。在非并发场景下可以通过contains(key)来判断是否真的存在,但是在并发场景下,很可能会被其他线程修改。在JDK注释中有这样的解释:

The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

ConcurrentHashMap

在Java1.7和1.8中ConcurrentHashMap实现差别较大,在1.7中采用分段锁的方式实现,将Map分为许多个Segment(Segment继承自ReentrantLock),操作的时候,只会去占用某一个Segment,而其他的Segment不会受到影响。

而在1.8中直接使用CAS+ synchronized来实现。其在内存中的结构与HashMap几乎相同了。

get操作

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;

    // 得到最终的hash值(将高位混合到低位去避免哈希冲突)
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // (n-1) & h 计算出所在的index值(与HashMap相同)
        (e = tabAt(tab, (n - 1) & h)) != null) { 
        // 如果哈希值相同,则直接定位到节点,再判断是否equal即可
        if ((eh = e.hash) == h) {                
            // 这里比较key是否equal,单纯只凭hashCode是不够的。
            // 首先比较内存地址是否一致;然后再调用equals方法,是一种优化手段。
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        /*
            Hash值的首位被用作标记位,为负数的hash值是特殊的节点(也就是红黑树化了)
        */
        // 如果根据哈希值没有匹配到,那证明可能有哈希冲突,为负数是红黑树则在树中查找
        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操作没有加任何的锁,而是通过将transient volatile Node<K,V>[] table;将table设置为volatile来保证可见性的。

transient volatile Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    //...
}

put操作

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) {
            // 尝试CAS插入节点到空桶中,如果失败,则会重新走上面的流程进来
            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;
            // f为当前定位到的桶中的第一个节点,将其同步进行后续操作
            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;
}