Java并发编程之ConcurrentHashMap原理解析

/**
 *  根据键值key获取value，根据key.equals方法判断两个元素是否相同
 *  @param key 键
 *  @return 如果key存在则返回对应的value，否则返回null
 */
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //将key的hashcode进一步散列，减少hash碰撞
    int h = spread(key.hashCode());
    //具体的元素信息是存在Node[]数组中，先判断key对应hash值映射到数组元素的位置释放有值
    //如果对应的数组位置没有值，直接返回null，否则继续判断
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果当前数组位置的元素的hash值和key值均相等，则直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //如果hash值为负数，说明相同hash值的元素组成了红黑树，则直接在红黑数内部查找：TreeBin.find
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //有相同hash值（发生了hash碰撞）的元素组成一个链表，依次在链表中查询目标元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //value为volatile类型的，从而保证了多线程读写的可见性
    volatile V val;
    //发生hash碰撞时，记录下一个元素，类型也是volatile的，从而保证可见性
    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 V put(K key, V value) {
    //具体的实现逻辑在putVal
    return putVal(key, value, false);
}
/**
  * 将key,value键值对放入到map中
  * @param key 键
  * @param value 值
  * @return 如果先前key的位置有值，则返回老的值，否则返回null
  */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //可以看到ConcurrentHashMap的key和value都不允许为null
    if (key == null || value == null) throw new NullPointerException();
    //将key的hashcode进一步散列，减少hash碰撞
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //记录元素的Node数组为null时要先进行初始化
        if (tab == null || (n = tab.length) == 0)
            //初始化table，见下文分析
            tab = initTable();
        //如果当前位置为null，可以直接放入元素
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //CAS写入元素，如果成功则返回；CAS失败说明有另外的线程在进行put操作，需要自旋等待
            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;
            //对当前节点加锁，防止其他线程并发更新
            synchronized (f) {
                if (tabAt(tab, i) == f) {//防止其他线程更改tabb在i位置的值，如果发生更新则继续循环
                    if (fh >= 0) {//hash值相同的节点为链表
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //如果找到key值相同的节点，说明需要更新数据
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                //保存原来的值
                                oldVal = e.val;
                                //putIfAbsent?
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            //更新节点的next节点为新加入的节点
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //如果hash值相同的节点为红黑树，则在红黑树内部执行节点新增或者更新逻辑
                    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;
                        }
                    }
                }
            }
            //hash值相同的元素个数>0
            if (binCount != 0) {
                //节点超过8个，若<64则扩容链表，否则从链表转化为红黑树，提升查询效率
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //增加数组元素个数，并判断是否需要扩容，若需要则进行扩容操作
    addCount(1L, binCount);
    return null;
}
/**
  * 初始化Node数组
  */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //数组为空时，持续循环
    while ((tab = table) == null || tab.length == 0) {
        //sc == -1，说明有多个线程同时在执行初始化操作，此线程竞争失败，让出cpu执行权
        if ((sc = sizeCtl) < 0)
            Thread.yield(); //让出cpu控制权，自旋等待
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//cas成功，进行初始化，并将sizectl的值设置为-1
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}