1.引子

并发编程中使用HashMap可能导致程序死循环。因为多线程会put方法添加键值对时将导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。

另外Hashtable只是简单地使用阻塞式锁（synchronized关键字）来保证线程安全，在并发编程中使用HashTable效率较低。

基于此，ConcurrentHashMap解决了上面的两方面的不足，它能够高效安全地对键值对进行读写操作。

ConcurrentHashMap的锁分段技术可有效提升并发访问率。Hashtable效率低的原因是多个线程竞争同一把锁。如果将容器中的数据划分为不同的部分或段，并为这些不同的段分别分配一把锁，当将线程要访问某数据，只需要竞争此数据所属分段的锁，而其他段的数据还是能被其他线程访问。这样就将锁的粒度细化了，实现了更高效的并发处理。

2 类结构

ConcurrentHashMap在JDK1.7和JDK1.8中的内部实现有较大的差异。JDK1.7中，ConcurrentHashMap直接使用Segment类型的数组segments作为分段锁数组（segments是成员变量），同时又是每个分段数据的的容器，每个segments又包含一个Entry数组。可将segments的每个元素看作一个HashMap对象，基于此可进一步想象，ConcurrentHashMap包含多个HashMap，每个HashMap是一个分段数据集，每个HashMap上有一把锁。

而在JDK1.8中，ConcurrentHashMap还是像HashMap一样，使用Node类型数组table作用为哈希表（table是其成员变量），将Node对象作为储存包含键值对节点的容器，不像JDK1.7中可以直接看到RentantLock锁。虽然也定义了Segment静态内部类，但JDK1.8中只有在（反）序列化方法中使用了这个类，只是为了（反）序列化时与JDK1.7相兼容而已。与JDK1.7的版本相比，这里Segment的重要性已经降低太多了,它与ConcurrentHashMap之间的类关系只是依赖而已。

JDK1.7
JDK1.8

3 常量与成员变量

成员变量

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

    private transient volatile Node<K,V>[] nextTable;

    private transient volatile long baseCount;

    private transient volatile int sizeCtl;

    private transient volatile int transferIndex;

    private transient volatile int cellsBusy;

    private transient volatile CounterCell[] counterCells;

    // views
    private transient KeySetView<K,V> keySet;
    private transient ValuesView<K,V> values;
    private transient EntrySetView<K,V> entrySet;

table ：哈希表，其长度始终是2的幂次方。

nextTable: 下个要用到的哈希表，在重新调用哈希表table的容量是会用到且只有此时不为null。这主要在保证resize时并发访问，ConcurrentHashMap还是可用的。

baseCount： 键值对个数的计数器，主要在没有线程竞争的时候使用。

sizeCtl: table初始化和大小调整控制的依据。 如果为负，则table将被初始化或resize：-1用于初始化，若为其它负数时，|sizeCtl|=（1 +正在resize的线程数）。若sizeCtl是非负数且table为null时，它表示数组table初始化时的长度。初始化之后，表示table 调整大小时下个元素计数值。

transferIndex: resize时要拆分的nextTable表索引。

cellsBusy: 基于CAS的自旋锁，它会在resize和创建CounterCells时被使用。

counterCells：一个分布式计数的帮助类

而keySet 、values、entrySet就是各种视图。

4初始化

ConcurrentHashMap有多个构造方法，我们直接研究其参数最多的构造方法。

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

参数concurrencyLevel代表预估的并发线程数，它会影响table的长度。构造方法首先通过“if (initialCapacity < concurrencyLevel)”确定用户设定的初始容量和并发级别是否匹配。如果inititalCapacity小于concurrencyLevel，就让inititalCapacity重设为concurrencyLevel。如果环境中真的有concurrencyLevel个线程，那么就应该有concurrencyLevel个锁，因为每个锁管理一段数据，那么就至少要有concurrencyLevel个段数据，每段数据至少包含一个哈希桶，也就是说至少table的长度至少要是concurrencyLevel。

根据“thread=loadFactor*capacity”公式可以看出，“(1.0 + (long)initialCapacity / loadFactor)”算出理论上table的最小长度size，这里加"+1"的原因是考虑不能整除时，要保留小数位的值，只能在整数位进一。而这个长度可size可能并是我们真正会使用的table的长度，因为我们要使用按位与的哈希算法来确定table的下标，就必须使table的长度为2的幂次方，而此时的size可能并不是2的幂次方，我们需要进一步处理。tableSizeFor()方法很巧妙使用了位运算，此方法能求出一个大于等于size的最小且是2的幂次方的值cap。如initialCapacity为14，loadFactor为0.75，concurrencyLevel为4，那么size=20,cap=32.所以最终初始化table时，其长度是32.

private static final int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3 核心API

1）添加键值对

put(K,V)和putIfAbsent(K,V)都是直接调用putVal(K,V,boolean)方法。putVal方法包含了添加键值对的流程框架。

public V put(K key, V value) {
    return putVal(key, value, false);
}
public V putIfAbsent(K key, V value) {
    return putVal(key, value, true);
}

putVal()方法的主要逻辑：①先确认table是空，若为空则将其初始化。②再根据位运算“(n-1)& hash”取余求出table的索引i，并进一步获取table下标为i的元素f,此f代表一个哈希桶，它一个单向链表或红黑树。③然后再确认f是否为空,若f为空，就使用CAS更新将f初始化。若CAS更新成功，则退出死循环，否则将再次进入“for (Node<K,V>[] tab = table;??”循环重试（自旋）。此时并没有使用阻塞锁，而是使用基于CAS的自旋锁。④若f的hash是-1，则表明table正在resize,要调用helpTransfer加速扩容。helpTransfer方法结束后，自旋重试添加键值对 ⑤若f不为空且其hash也不是-1时,就使用阻塞锁（synchronized关键字）将对象f锁住，再遍历链表f，查找此链表上是否存在Key对应的节点e。⑥若链表f上存在这样的节点e，就将e的val属性更新为当前需要添加键值对的value 。⑦若链表上不存在这样的节点e,就新构建一个节点，并将这个节点添加链表的尾部⑧若f是红黑树结构，就使用其特有的putTreeVal()方法进行键值对的添加。⑧若f的数据结构是ReservationNode等其他类型节点就同样需要自旋重试，等待状态正常时再来添加键值。⑨若链表长度超过了树形化的阀值，将链表转化为红黑树。链表上若存在这样的e节点，将e节点的原value直接返回；若不存在就调用addCount()来更新元素个数，再返回null 。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode()); //再散列，求key对应的hash
    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是空就初始化table
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                    new Node<K,V>(hash, key, value, null)))
                //键值对要添加到的哈希桶为空时，只要CAS成功初始化此哈希桶即可退出循环。此时不需要加锁
                //这个添加键值对的node是这个哈希桶的头节点
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)//MOVED是常量-1
       //哈希桶不为空且hash为-1，表明table正在resize，使用helpTransfer加速扩容
            tab = helpTransfer(tab, f);
        else {
            //要添加键值对的Key可能在链表或红黑树上f了，需要遍历它
            V oldVal = null;
            synchronized (f) { //锁定此链表或红黑树f
                //"if (tabAt(tab, i) == f)"主要是保证f是我们要遍历的目标哈希桶。
                // 在执行“((fh = f.hash) == MOVED)”时，可能会有其它线程修改了table
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { //f是正常的哈希节点
                        binCount = 1;//链表长度
                        for (Node<K,V> e = f;; ++binCount) {//开始遍历链表（红黑树）f
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {//哈希桶f上已存在这个Key对应的节点
                                oldVal = e.val;//保存原Value，最后需要返回它
                                if (!onlyIfAbsent)
                                    e.val = value; //将原节点的val属性更新成新添加的value
                                break; //退出遍历链表的循环
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                //遍历完链表发现,哈希桶f上不存在这个Key对应的节点。
                                //需要构建一个Node节点，将此节点添加在链表的尾部
                                pred.next = new Node<K,V>(hash, key,
                                        value, null);
                                break;//退出遍历链表的循环
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 哈希桶f是红黑树型结构，使用其特有的putTreeVal方法添加键值对。
                        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) {
                // 只要保证fh>0或f是红黑树，bineCount的最小值就是1。
                // 那么也就一定会进入当前if分支
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i); //链表长度超过了树形化的阀值，将链表转化为红黑树
                if (oldVal != null)
                    //原value不为空，直接返回这个值。
                    // 这时没有添加新的节点，不需要调用addCount方法去更新元素个数
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

(1)putVal()对键值都做了非空判断，这与HashMap有所不同，ConcurrentHashMap的Key和Value都不能为null。

(2)计算hash

而计算hash值的方法spread(int)的算法也与HashMap不同。"(h ^ (h >>> 16))"是HashMap计算hash的方式。此处在此基础之上，将“(h ^ (h >>> 16))”的结果和0x7fffffff进行按位与运算 (HASH_BITS是常量0x7fffffff），0x7fffffff的进二进制形式是“01111111_11111111_11111111_11111111”。根据位运算特点可知，经y=x&0x7fffffff计算后,y与x的四字节二进制形式可能只有最高位不同（y与x可能是相等的），y的最高位一定是0。这里和HASH_BITS按位与运算的目的是将其最高位强制设为0。因为计算机中数字的最高位是符号位，所以spread()方法返回值始终是非负数。

HASH_BITS的注释是“ usable bits of normal node hash”，那么所有正常节点的hash属性都非负数，因为才有putVal()方法体中的“if (fh >= 0) ”，只有哈希桶的头节点是正常节点才会遍历所哈希桶的所有节点。

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

(3)初始化table

其主要逻辑是：先根据构造方法中计算出的sizeCtl来决定数组table长度，当状态合适时就将table初始化，再将sizeCtl设为原值的四分之三。

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                //只有sizeCtl是非负数时，才表示table需要初始化。
                // sizeCtl是负数表明其他线程可能正在初始化,当前线程放弃对table初始化的竞争，进入自旋状态。
                Thread.yield(); // lost initialization race; just spin

            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                // CAS尝试将sizeCtl为-1，主要目的让其他线程得到通知。
                //其他线程检测有sizeCtl是-1，这些线程就能知道某线程正在初始化table,这些线程就会放弃初始化table
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        //这里sc不可能小于0，只可能等于0,若sc=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); //sc=0.75*n
                    }
                } finally {
                    sizeCtl = sc; //无条件将sizeCtl设为原值的3/4
                }
                break; //CAS更新成功后，一定会将table初始化,可以退出自旋了。
            }
        }
        return tab;
    }

(4) 确定哈希桶

确定哈希桶的主要是找到哈希桶在哈希表table中的索引。

“tabAt(tab, i = (n - 1) & hash))”可看出也是像HashMap利用位运算“(n - 1) & hash”取余来确定索引。这种利用位运算取余算法的基本前提是n必须是2的幂次方，所以table的长度也一直是2的幂次方。

而tabAt(Node[],int)方法也是简单地调用Unsafe类的getObjectVolatile方法。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

(5)哈希桶为空，利用CAS初始化哈希桶（的头节点）

casTabAt(Node[],int)简单调用Unsafe类的CAS方法更新table中i索引的元素。

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

（6）哈希桶的头节点的hash是-1，表明这个是forward节点（正常节点的hash是非负数），table正在resize，使用helpTransfer加速扩容。

ForwardingNode是Node的子类，其构造方法中调用了父类的构造方法Node(int, K, V , Node<K,V> )。可以看出ForawrdingNode所有实例的hash都是常量-1(MOVED是常量-1)，其next属性为null,表明其没有后继节点。ForwardingNode类的设计目的本就是在转移扩容期间，将一个实例添加在哈希桶的头部，且其无后继节点，它是检测是否在转移扩容期间的flag标记。

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    //f是转移节点，且其节点的下个table不为空。
    if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        //扩容时的标记位
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
                //局部变量与成员变量相等，即nextTablet和table没有被其它线程修改
         (sc = sizeCtl) < 0) {//sizeCtl小于0，表明正在扩容（-1时正在初始化table,显然此时不可能初始化table）
            /**
             *  若sc右移16位（取其高16位）与rs不等（表明标记位rs变化了）
             *  或cs等于rs+1(扩容可以结束了，没有线程在扩容了。默认第一个线程设置sc=rs<<16+2,第一个线程结束扩容sizeCtl自减1，此时sc和rs就相差1)
             *  或sc = rs + MAX_RESIZERS（已经达到了最大扩容线程数）
             *  或transferIndex<=0(下标正在调整，扩容结束)
             *  时，退出循环
             */
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || //RESIZE_STAMP_SHIFT是常量16
                    sc == rs + MAX_RESIZERS || transferIndex <= 0) //MAX_RESIZERS是常量65535，表示最大扩容线程数
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { //CAS将sizeCtl加1
                transfer(tab, nextTab);//CAS更新成功，table进行转移扩容(将tab的元素转移到nextTab)
                break;
            }
        }
        return nextTab;
    }
    return table;
}

（7）若哈希桶上没有key对应的节点，在添加节点后还需要调用addCount重新计数元素个数

2）获取键的值

根据键获取值的方法主要有get(Object)、getOrDefault(Object,V)这两个，而getOrDefault方法又是委托get(Object)实现的，因此我们重点关注get(Object)方法。

public V getOrDefault(Object key, V defaultValue) {
    V v;
    return (v = get(key)) == null ? defaultValue : v;
}

这里的get(Obejct)方法和HashMap的get方法类似。先确定Key对应的节点可能存在的某个桶上，然后再遍历这个桶上的所有节点，如果遍历过程中找到这样的节点，就返回节点的val属性，若遍历完后没找到这样的节点，就返回null 。值得注意的是当哈希桶的头节点是非正常节点时，不能直接按照常规的方式获取节点的val属性，此时需要调用其特定类类型的find()方法。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode()); //算出hash
    //key对应的节点应可能在数组table的"(n - 1) & h)"索引元素上时。
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            //因为h>=0,所以eh>=0,此时e是正常节点，且是e是链表的头节点（红黑树TreeBin的hash常量-2）
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val; //在哈希桶的头节点上时，可直接返回此节点的val.
        }
        else if (eh < 0)//查找的节点不是哈希桶的头节点,且头节点是非正常节点,使用其特定的find(int,Object)查找
            //正常节点的hash是非负数,可能是MOVED(转移)节点、TREEBIN(红黑树)根节点或RESERVED(暂存)节点。
            //只有以上三种节点是负数。
            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;//在链表上找到此节点，返回此节点的val
        }
    }
    return null;//没找到返回null
}

3) 移除键值对

remove(Object,Object)和remove(Object,Object)方法均调用replaceNode（Object,V,Object)来实现自己的功能。

public boolean remove(Object key, Object value) {
        if (key == null)
            throw new NullPointerException();
        return value != null && replaceNode(key, null, value) != null;
    }
    public V remove(Object key) {
        return replaceNode(key, null, null);
    }

replaceNode()方法比较长，但主要逻辑还是很清楚的。

此方法是四个remove/replace方法的核心实现，也就是说另外的replace(K,V,V) 、replace(K,V)两个API也是基于replaceNode方法实现。

根据传入replaceNode方法的参数value是否为空，来确定是移除键值对还是替换某个键的值。当参数value为空，表明将移除键值对，而参数value非空则表明要替换某个键的值。

replaceNode的核心逻辑：先根据Key的hash确定节点可能在哪个哈希桶上，若计算出的哈希桶f为空，哈希桶还未被初始化，表明哈希表上不可能存在Key对应的节点，退出死循环，返回空。此哈希桶f的头节点是转移节点，表明table正有扩容，调用helpTransfer方法多线程加速扩容。在helpTransfer方法结束后，自旋重试再来移除键值对或替换某个键的值。若哈希桶的头节点是非转移节点，就使用阻塞锁（synchronized关键字）将此哈希桶f锁住，准备遍历这个哈希桶中的所有节点。若哈希桶是链表结构，就遍历链表查找Key对应的节点e。若遍历过程中找到这样的节点e，且条件允许（即预期被替换值（移除值）与实际被替换值（移除值）相等），就更新节点e的val属性或将e的前后节点直接链接起来以移除节点e .若哈希桶是红黑树，也要遍历红黑树查找节点e,其处理流程与链表相似。若哈希桶的数据结构是ReservationNode等其他类型节点就同样需要自旋重试，等待状态正常时再来移除键值对或替换某个键的值。

final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break; //Key对应的哈希桶为nul,它不可能在哈希表table上，退出死循环
        else if ((fh = f.hash) == MOVED)
            //和putVal类似，检测有table正有扩容，多线程加速扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            synchronized (f) { //锁住这个哈希桶
                if (tabAt(tab, i) == f) { //保证table没有被其他线程修改
                    //fh>0表明f是正常节点，且是链表的头节点（红黑色根节点treeBin的hash是常量-2）
                    if (fh >= 0) {
                        validated = true; //f是链表，验证通过
                        for (Node<K,V> e = f, pred = null;;) {//开始遍历链表
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {//找到了Key对应的节点
                                V ev = e.val;
                                //cv预期被替换的原value, ev是实际会被替换的原value
                                //若预期被替换值为空或预期被替换值与实际被替换值相等，就执行value替换或节点移除操作
                                if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                    oldVal = ev;//保存节点的原val，方法最后需要返回此值
                                //传入当前方法replaceNode的参数value非空，表明调用者想修改节点的val属性
                                //参数value为空，表明调用者想移除节点
                                    if (value != null)
                    //"replace(K,V)"和"replace(K,V,V)"传入当前replaceNode方法的参数value均非空。
                    //预期替换后的新value不为空，就更新此节点的val属性，
                    //将其设为预期替换后的value.
                                        e.val = value;
                                    else if (pred != null)
                   // "remove(Object,Ojbect)"和"remove(Object)"传入当前replaceNode方法的参数value都是null
                    //预期替换后的新value为空，表明这是个移除节点的操作，而前驱节点pred非空，表明e不是链表的头节点。
                    //将前当前节点e的前驱节点和后继节点直接利用next属性越过自身e将两者链接起来。当前节点e也就被移除了。
                                        pred.next = e.next;
                                    else
                                        //value为空，pred为空，表明这是个移除节点的操作且e是链表的头节点
                                        //将e的后继节点作为链表新的头节点，这个原头节点e也就被移除了
                                        setTabAt(tab, i, e.next);
                                }
                                break;//找到节点，退出遍历
                            }
                            pred = e;
                            if ((e = e.next) == null)//遍历完链表也需退出遍历过程
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {
                        validated = true;//f是红黑树，验证通过
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) { //找到了Key对应节点
                            V pv = p.val;
                           // 若预期被替换值为空或预期被替换值与实际被替换值相等，就执行value替换或节点移除操作
                            if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                oldVal = pv;//保存节点的原val，方法最后需要返回此值
                                if (value != null)
                                    //value非空，进行节点value替换（val属性更新）
                                    p.val = value;
                                else if (t.removeTreeNode(p)) //value为空，进行节点移除
                                    //若移除这个节点p后，红黑树的节点个数太少，则需要将红黑树转为链表，
                                    // 并将这个链表放在table上。
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            //只要f是链表或红黑树，validated就会被设为true. 这种情况下可能进行了节点的移除或节点的val属性更新
            //而f若是Forwarding这类标识型节点，根本就不可能会执行节点的移除和节点的val属性更新，
            // 因为这类节点不存放具体有意义的键值对。
            if (validated) {
                //节点的原value不为空，表明确实执行节点的移除或节点的val属性更新操作，返回原value
                if (oldVal != null) { 
                    if (value == null)
                        //value为空，执行了移除节点操作，需要更新元素个数。
                        addCount(-1L, -1);
                    return oldVal;
                }
                //没找到Key对应节点或找到节点但条件不满足（这里的条件不满足是指预期被替换值与实际被替换值不等），
                // 将返回null
                break; 
            }
        }
    }
    return null;
}

4.总结

1）与JDK1.7相比，在JDK1.8 中ConcurrentHashMap使用了更细粒度的锁，JDK1.7中多个哈希桶对应一把锁，而JDK1.8中一个哈希桶对应一把锁，且不一定会用到这个锁（如在添加键值对时恰好是为哈希桶添加头节点，此时使用CAS自旋）。这能够显著提升并发的效率。

2）与JDK1.7相比，在JDK1.8 ConcurrentHashMap代码逻辑更清晰易懂。在JDK1.7中构造方法需要对segments数组进行初始化，里面包含不少的位运算，需要计算段偏移量、段掩码等。而JDK1.8 中构造方法主要是计算初始化容量，没有太多位运算。

3)与JDK1.7相比，在JDK1.8 ConcurrentHashMap对哈希桶的定位更快. 因为在JDK1.7中需要两次散列计算，先要根据通过segmentFor(int)定位到Segment，再继续在segment中找到哈希桶HashEntry的下标。而JDK1.8中只需要一次散列计算后，即可定位到节点所在的哈希桶。