源码分析之ConcurrentHashMap容器

清疚 2022-11-17 11:29 228阅读 0赞

### 源码分析之ConcurrentHashMap容器 ###

*   *  1、ConcurrentHashMap容器概述
     *  2、JDK1.7中的ConcurrentHashMap容器
     *  3、JDK1.8中的ConcurrentHashMap容器
     *   *  3.1、主要属性
         *  3.2、构造、初始化相关的方法
         *  3.3、put方法
         *  3.4、get方法
         *  3.5、hash计算方法
         *  3.6、链表、红黑树转换方法
         *  3.7、扩容方法
     *  4、总结
     *  5、往期佳文
     *   *  5.1、面试系列
         *  5.2、技术系列
         *  5.3、源码系列
         *  5.4、数据结构和算法系列
         *  5.5、多线程系列

## 1、ConcurrentHashMap容器概述 ##

ConcurrentHashMap类声明：

package java.util.concurrent;
    
    public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
            implements ConcurrentMap<K, V>, Serializable

--------------------

## 2、JDK1.7中的ConcurrentHashMap容器 ##

JDK1.7中的ConcurrentHashMap容器采用分段管理，初始化构造时默认16个段（可进行动态修改），每个段都有一个ReentrantLock锁，并且每个Segment分别对应一个HashEntry（可以理解为一个小的Hashtable）。我们需要删除、增加一个key-value时，先判断key对应的hash所在的段，然后再在段中找到响应的位置删除或插入。（如果是多个线程同时进行读写操作，有很大可能是读写不同的段，所以效率较Hashtable有较大提升）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]

--------------------

## 3、JDK1.8中的ConcurrentHashMap容器 ##

在JDK1.8中，移除了ConcurrentHashMap容器中的分段管理，只剩下一个table数组，并且增加了红黑树结构优化链表过长访问降低效率的问题，与JDK1.8中的HashMap底层数据结构一致。  
      那么之前一直提到的ConcurrentHashMap相比于Hashtable分段管理（分段锁，减小锁的粒度）的优势岂不是没有了？JDK1.8也修改之前的ReentrantLock锁机制为CAS+synchronized，并且尽量减少了使用锁的代码（在Hashtable是synchronized同步函数，锁的粒度大）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]  
      CAS，Compare and Swap，主要思想是：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。  
      ConcurrentHashMap类中申明的三个关于CAS的方法:

/** * 获取tab数组的引用 */
    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);
    }
    /** * 更新tab[i]，c是更新前的预期值（tab[i]可能被其它线程改动了），v是需要更新为的值 * 调用compareAndSwapObject方法，更新前先对比tab[i] == c，不相等则说明被其它线程改动了，更新失败，否则更新 */
    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);
    }
    /** * 设置tab[i] = v */
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { 
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

### 3.1、主要属性 ###

/** * table表的最大长度 */
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /** * 默认table表的长度为16（必须是2的次幂） */
    private static final int DEFAULT_CAPACITY = 16;
    
    /** * array数组的最大长度，与toArray方法有关 */
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    /** * 并发级别，在jdk1.7中有段的概念，需要分段锁，此为向前兼容 */
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    
    /** * table表的负载因子 */
    private static final float LOAD_FACTOR = 0.75f;
    
    /** * 若某链表的长度超过该值就需要转换成红黑树（当然还需要一个条件，继续往下看） */
    static final int TREEIFY_THRESHOLD = 8;
    
    /** * 若某红黑树中key-value数少于该值，需要重新转换回链表 */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /** * 前面说如果某链表的长度 > TREEIFY_THRESHOLD 就需要转换为红黑树 * 实际上还有一个附加条件，就是table数组的长度 不小于 MIN_TREEIFY_CAPACITY * 该值主要是考虑到table数组短而造成严重的hash冲突问题，即某链表下的节点数过多 * 此时首要考虑的是扩大table数组的长度，而不是将链表转换为红黑树 */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /** * 扩容线程每次最少要迁移的hash桶数（至少是table数组的长度） */
    private static final int MIN_TRANSFER_STRIDE = 16;
    
    
    /** * The maximum number of threads that can help resize. * Must fit in 32 - RESIZE_STAMP_BITS bits. */
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    
    
    /* * 一般标记在hash桶中的第一个元素 */
    static final int MOVED     = -1; // 正在移动
    static final int TREEBIN   = -2; // 红黑树
    static final int RESERVED  = -3; // hash for transient reservations
    /** * 在spread方法中有用到，主要是将int型最高位置零，放置hash出现负数，不好进行求余操作 */
    static final int HASH_BITS = 0x7fffffff;
    
    /** CPU个数, to place bounds on some sizings */
    static final int NCPU = Runtime.getRuntime().availableProcessors();
        
    /* ---------------- Fields -------------- */
    
    /** * table数组（hash桶数组），ConcurrentHashMap容器存放key-value的核心 */
    transient volatile Node<K,V>[] table;
    
    /** * 临时tab数组，用于正在扩容时的暂时存放 */
    private transient volatile Node<K,V>[] nextTable;
    
    /** * 这个值比较重要，也比较复杂，有好几种状态。。。 * 构造的时候（调用构造方法） * = 0，未设置（初始化会使用DEFAULT_CAPACITY默认大小） * > 0,表示的table数组需要初始化的长度（必须是2的次幂） * 初始化的时候（调用initTable方法），需要使用构造时候设置的值 * = -1 正在初始化 * > 0(初始化完了，= max(构造的时候的值, DEFAULT_CAPACITY) * 负载因子)，表示容器中存放key-value的阈值 * 其它值 * < -1,分为两部分，高15位是新容量的值，低16位(M)表示并行扩容线程数+1，具体在resizeStamp函数介绍。 */
    private transient volatile int sizeCtl;
    
    /** * [0, transferIndex)表示table数组中待移动的hash桶（主要用在扩容时） */
    private transient volatile int transferIndex;

### 3.2、构造、初始化相关的方法 ###

public ConcurrentHashMap(int initialCapacity) { 
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        // initialCapacity 超过 MAXIMUM_CAPACITY / 2， 则赋值为最大值 MAXIMUM_CAPACITY（前面属性已经介绍过这个值，2^30 , 不记得的往前面翻翻吧）
        // initialCapacity + (initialCapacity >>> 1) + 1,由于有负载因子的存在，所以你想初始化的大小 ÷ 负载因子（默认是0.75）就是容器table数组真正初始化的长度
        // 否则需要调用tableSizeFor(number)方法，计算不小于number的2的次幂，这个方法在HashMap中介绍过，想要打破砂锅问到底的可以去翻前一篇介绍hashMap的博客
        // 最终 cap 是一个2的次幂
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        // 赋值给sizeCtl（前面也介绍过这个属性， 不记得的往前面翻翻吧）
        this.sizeCtl = cap;
    }
    /** * @parm initialCapacity 初始化容量 * @parm loadFactor 初始化负载因子 * @parm concurrencyLevel 并发量（类似JDK1.7中的段数，分段锁，主要是向前兼容，可以忽略 */
    public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { 
    	// 检查initialCapacity、loadFactor、concurrencyLevel参数合法性
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // 初始化容量总不能小于并发量吧。。。
        if (initialCapacity < concurrencyLevel)
            initialCapacity = concurrencyLevel;
        // 你希望初始化的大小是initialCapacity，但是负载因子的存在，容器的table数组的长度应该是 (long)initialCapacity / loadFactor，加上1.0主要是向上取整
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        // 超过MAXIMUM_CAPACITY（前面介绍过这个属性），则附最大值，否则调用tableSizeFor
        // tableSizeFor(number)方法，计算不小于number的2的次幂，这个方法在HashMap中介绍过，想要打破砂锅问到底的可以去翻前一篇介绍hashMap的博客
        int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size);
        // 最终 sizeCtl仍然是2的次幂
        this.sizeCtl = cap;
    }
    
    /** * 此方法是复制构造方法，需要将容器m中的内容复制到新建的容器 */
    public ConcurrentHashMap(Map<? extends K, ? extends V> m) { 
        this.sizeCtl = DEFAULT_CAPACITY;
        // 此方法调用了putVal方法，进而调用initTable初始化方法
        putAll(m);
    }

put的时候才会初始化容器，初始化方法：

private final Node<K,V>[] initTable() { 
        Node<K,V>[] tab; int sc;
        // while循环检查table是否初始化了
        while ((tab = table) == null || tab.length == 0) { 
            if ((sc = sizeCtl) < 0)
            	// 前面介绍sizeCtl属性时，sizeCtl < 0 可能是在扩容或者初始化
            	// 次数tab为null显然不是扩容，只能说明其它线程正在初始化，此时当前线程调用yield方法让出此时运行的CPU时间片
                Thread.yield(); // lost initialization race; just spin
            // 调用Unsafe的compareAndSwapInt方法，更新sizeCtl = -1
            // 不过compareAndSwapInt方法更新前需要判断sizeCtl是否发生了修改，我们之前用sc保存了sizeCtl的值
            // SIZECTL是sizeCtl内存地址（在类中有赋值，不用纠结在哪赋值的，再深入我博客篇幅就太长了。。。）
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 
                try { 
                	// tab为空，新建nt数组，长度为sc（sizeCtl初始化的值，table数组的长度）
                    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;
                        // n >>> 2是n的四分之一，相当于n * 0.75，0.75不正是默认的负载因子么。。。得到的结果是容器可放置的key-value阈值
                        sc = n - (n >>> 2);
                    }
                } finally { 
                	// 最后sizeCtl更新为容器可放置的key-value阈值
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

### 3.3、put方法 ###

public V put(K key, V value) { 
    	// 调用putVal方法，第三个参数表示是否只做单纯的插入，false代表容器中如果存在key对应的value进行更新操作，否则插入
        return putVal(key, value, false);
    }
    
    /** * @parm onlyIfAbsent 表示是否只做单纯的插入，false代表容器中如果存在key对应的value进行更新操作，否则插入 */
    final V putVal(K key, V value, boolean onlyIfAbsent) { 
    	// ConcurrentHashMap不支持key/value为null
        if (key == null || value == null) 
        	throw new NullPointerException();
        // 调用spread得到hash值（此方法在下文有介绍）
        int hash = spread(key.hashCode());
        // 用于计算key所在的链表（hash桶）中的key-value数（最后判断是否要改红黑树）
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) { 
            Node<K,V> f; int n, i, fh;
            // 前面提及过，在插入前需要判断table是否初始化了
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // (n - 1) & hash其实是对hash % n,(多次提到table数组长是2的次幂，就是为了求余方便)
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
            	// table[i] == null,则调用封装好的cas操作，替换table[i]，即插入到这个位置
                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[i]处于MOVED状态，则当前线程也帮忙move（后面有介绍helpTransfer方法）
                tab = helpTransfer(tab, f);
            else { 
            	// 考虑完上面的情况就可以插入
                V oldVal = null;
                // synchronized通过代码块，f对象锁
                synchronized (f) { 
                	// f是之前保存的tab[i]值，判断是否修改了
                    if (tabAt(tab, i) == f) { 
                        if (fh >= 0) { 
                        	// 遍历tab[i]这个链表
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) { 
                                K ek;
                                // 如果key相等（容器中已经含有key）
                                if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { 
                                    oldVal = e.val;
                                    // onlyIfAbsent = false就要更新（在前面已经介绍过这个参数了）
                                    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) { 
                        	// 此hash桶还可能是红黑树实现
                            Node<K,V> p;
                            // 由于已经是红黑树实现，插入节点只会增加数量，binCount记录hash桶中的元素个数已经没有意义了
                            binCount = 2;
                            // 调用红黑树中的putTreeVal方法插入/更新节点（与此方法类似）
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { 
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                // 如果binCount > TREEIFY_THRESHOLD(前面介绍过该属性，链表转红黑树阈值，默认是8)
                if (binCount != 0) { 
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                		// 说明只是更新操作，提前返回
                        return oldVal;
                    break;
                }
            }
        }
        // 计数
        addCount(1L, binCount);
        return null;
    }

### 3.4、get方法 ###

public V get(Object key) { 
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        // 调用spread方法计算hash值（下文有介绍此方法）
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { 
            if ((eh = e.hash) == h) { 
            	// 此种情况hash桶是链表实现，判断表头的key是否是要找的
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
            	// tab[(n - 1) & h].hash < 0 此时表示正在扩容，调用find查找
                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;
    }

### 3.5、hash计算方法 ###

/** * 入口参数h一般为某个对象的hashCode（此方法在Object类中有定义） */
    static final int spread(int h) { 
    	// 将 h的低 16 位 与 高 16 位 异或
    	// HASH_BITS是一个常量 0x7fffffff（32位有符号int型的最大值）
    	// & HASH_BITS,主要是将前面异或的结果最高位置零，int是有符号整形，计算在table中的index时要求余，所以不能出现负数
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

### 3.6、链表、红黑树转换方法 ###

链表实现转为红黑树：

/** * 将tab[index]的hash桶由链表转换成红黑树 */
    private final void treeifyBin(Node<K,V>[] tab, int index) { 
        Node<K,V> b; int n, sc;
        if (tab != null) { 
        	// 转换前还要满足一条件，tab.length > MIN_TREEIFY_CAPACITY(前面介绍过这个常量)
        	// 这样做的目的是防止tab数组太短而造成链表太长（hash冲突较多）的情况
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            	// 尝试扩容为原来的2倍
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { 
                synchronized (b) { 
                	// 修改tab[index]肯定需要把这个hash桶锁起来（与Hashtable相比，后者锁整个容器，ConcurrentHashMap减少了锁的粒度）
                    if (tabAt(tab, index) == b) { 
                        TreeNode<K,V> hd = null, tl = null;
                        // 下面遍历该链表，把链表中的所有节点Node转换成TreeNode对象，并且串成链表
                        for (Node<K,V> e = b; e != null; e = e.next) { 
                            TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        // 这里调用TreeBin构造方法生成红黑树，并且赋值给tab[index]即转成了红黑树
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

红黑树实现转为链表：

static <K,V> Node<K,V> untreeify(Node<K,V> b) { 
        Node<K,V> hd = null, tl = null;
        // 遍历红黑树，将节点全部转换哼Node对象，并且串成链表，返回即可
        for (Node<K,V> q = b; q != null; q = q.next) { 
            Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

### 3.7、扩容方法 ###

static final int resizeStamp(int n) { 
    	// Integer.numberOfLeadingZeros(n)用于计算n转换成二进制后前面有几个0
    	// RESIZE_STAMP_BITS = 16常量，也就是(1 << (RESIZE_STAMP_BITS - 1)结果为 0000 0000 0000 0000 1000 0000 0000 0000
    	// resizeStamp的返回值高16位置0，第16位为1，低15位存放当前容量m，代表的2^m == n
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }
    /** * 尝试扩容当前容器，使能接收size个key-value * 此方法在putAll（复制其它容器）、treeifyBin链表转红黑树有调用（在对应的方法中标记了，可以去前面看看） */
    private final void tryPresize(int size) { 
    	// size是预计存放的key-value数，但是由于负载因子（默认0.75）的存在，所以实际上还需要扩大，
    	// tableSizeFor(n)计算不小于n的最小2的次幂,比如n = 12时，返回16=2^4
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        // 翻翻前面介绍sizeCtl属性吧，>= 0表示 刚构造完 获取 初始化完
        while ((sc = sizeCtl) >= 0) { 
            Node<K,V>[] tab = table; int n;
            if (tab == null || (n = tab.length) == 0) { 
            	// 此种情况是tab没有初始化，与initTable方法（前面已介绍过了）几乎一毛一样的
                n = (sc > c) ? sc : c;
                // UnSafe类，将SIZECTL（可理解为sizeCtl的内存地址）修改为-1
                // 修改前判断sizeCtl是否发生了修改，sc之前复制sizeCtl的值
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 
                    try { 
                        if (table == tab) { 
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = nt;
                            // n >>> 2的结果是n / 4，因为默认负载因子是0.75
                            // sc保存key-value的阈值
                            sc = n - (n >>> 2);
                        }
                    } finally { 
                    	// 初始化后sizeCtl保存为sc(前面已经赋值tab.length * 负载因子)
                        sizeCtl = sc;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
            	// tab 已经判断了非null，则sc(sizeCtl)存储的是key-value的阈值，超过需要的容量c，此时不用扩容，同样也不用移动key-value
                break;
            else if (tab == table) { 
            	// 前面已经扩容了table容量能得下size个key-value
            	// 现在需要考虑移动各个hash桶中的key-value
                int rs = resizeStamp(n);
                if (sc < 0) { 
                    Node<K,V>[] nt;
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
            }
        }
    }
    /** * 作用是在有其它线程在扩容，当前容器尝试去辅助移动key-value，缩短扩容的时间 */
    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) { 
        Node<K,V>[] nextTab; int sc;
        // 在transfer方法中，我们把table[i]置为ForwardingNode对象，说明该hash桶正在移动
        // 移动完后nextTab == null（在transfer方法中有设置）
        if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) { 
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { 
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                // 每有一个线程来帮助迁移，sizeCtl就+1，初始值为(rs << RESIZE_STAMP_SHIFT) + 2)（在tryPresize()设置），之后再transfer中会用到
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { 
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
    /** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { 
        int n = tab.length, stride;
        // stride记录并发量，NCPU常量记录CPU的数
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) { 
        	// 初始化nextTab
            try { 
                @SuppressWarnings("unchecked")
                // n << 1相当于 n * 2,也就是扩大为原来的2倍
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {       // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            // nextTable是实例属性，用于记录正在扩容时暂时存放（前面介绍属性说过）
            nextTable = nextTab;
            // [0, transferIndex)的hash桶中的key-value待移动nextTab，>=transferIndex的桶都已分配出去
            transferIndex = n;
        }
        int nextn = nextTab.length;
        // 扩容时的特殊节点，标明此节点正在进行迁移，扩容期间的元素查找要调用其find()方法在nextTable中查找元素。
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        // 当前线程是否需要继续寻找下一个可处理的节点
        boolean advance = true;
        // 所有桶是否已经完成迁移
        boolean finishing = false;
        for (int i = 0, bound = 0;;) { 
            Node<K,V> f; int fh;
            // 此循环的作用是确定当前线程要迁移的桶的范围或通过更新i的值确定当前范围内下一个要处理的节点。
            while (advance) { 
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) { 
                	// 当前已经迁移完毕
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { 
                	// 确定当前线程每次分配的待迁移桶的范围为[bound, nextIndex)
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            // tab的长为n，需要移动的桶范围[0, n)
            if (i < 0 || i >= n || i + n >= nextn) { 
                int sc;
                // 扩容操作全部完成，赋值table = nextTab，清空nextTable（临时指向新表）
                if (finishing) { 
                    nextTable = null;
                    table = nextTab;
                    // sizeCtl重新恢复为 nextTab.length * 0.75(即2*n - n / 2)
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                // 当前线程已经完成移动任务，sizeCtl - 1
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { 
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    // 这里又赋值i = n，主要是在上面的while循环中再次检查是否还有没移动的hash桶
                    i = n;
                }
            }
            else if ((f = tabAt(tab, i)) == null)
            	// tabAt[i] == null,将它置为fwd
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
            	// MOVED是一个常量，标记已经移动完毕了
                advance = true;
            else { 
                synchronized (f) { 
                	// 移动f 即tab[i]中的元素，给f加上锁（Hashtable是锁上整个对象，这样减少锁的粒度，故效率高）
                    if (tabAt(tab, i) == f) { 
                    	// 当前hash桶拆分成两个hash桶（因为整个容器扩大为原来2倍）
                        Node<K,V> ln, hn;
                        if (fh >= 0) { 
                        	// fh >= 0，表示该hash桶是链表实现
    						
    						// （关键）此处的n是扩展前的table大小（并且n是2的次幂），& n 结果是判断 二进制中这一位是否为1，比如n = 16 = 0001 0000
    						// 任何数与n与操作，要不是得到 0001 0000，要不就是 0000 0000
                            int runBit = fh & n;
                            
                            // 下面这段代码与Hashtable中的扩容是一样的，主要的思想是拆分成两个链表，
                            // 原始有16个hash桶，并且当前扩展的桶存放的是余数为10的元素，则放入该桶的hash值有 10、26、42、58...
                            // 现在扩展为原来的2倍，32个桶，则当前桶下的元素 分别移动到 hash % 32 == 10 和 hash % 32 = 10 + 16两个桶下
                            // 比如10、42放入第一个桶，26、48放入第二个桶
                            // 其实要判断的就是 hash & 2n 是否大于 n
                            
                            // 首先取出链表的尾端节点，更新runBit为尾节点的hash值与n的二进制形式与操作后对应的为是否为1
                            Node<K,V> lastRun = f;
                            for (Node<K,V> p = f.next; p != null; p = p.next) { 
                                // 与runBit一样，此处同样计算的是节点p的hash值二进制形式中对应位是否是1
                                int b = p.hash & n;
                                if (b != runBit) { 
                                	// 更新runBit，为p.hash & n（为啥要用if判断，b == runBit 如果相等就不用更新）
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            // 判断尾端节点放到哪个链表下，前面更新runBit
                            // runBit == 0,说明p.hash % 2n < n
                            if (runBit == 0) { 
                                ln = lastRun;
                                hn = null;
                            }
                            else { 
                                hn = lastRun;
                                ln = null;
                            }
                            // 然后将链表其它节点也串接到两个链表上
                            for (Node<K,V> p = f; p != lastRun; p = p.next) { 
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            // ln链表 hash % 2n < n
                            setTabAt(nextTab, i, ln);
                            // ln链表 hash % 2n > n
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        else if (f instanceof TreeBin) { 
                        	// 剩下的就是红黑树实现了
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            // 遍历红黑树，同上拆分成两个链表，判断条件(h & n) == 0（其实就是判断 h % 2n > n）
                            for (Node<K,V> e = t.first; e != null; e = e.next) { 
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);
                                if ((h & n) == 0) { 
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else { 
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            // 如果链表的长度超过UNTREEIFY_THRESHOLD阈值，则转换成红黑树
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;
                            // 然后分别放入nextTab[i],nextTab[i + n]
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

## 4、总结 ##

总的来说JDK1.7版本的ConcurrentHashMap相当于多个Hashtable容器（其实就是段的概念），使用多个RententLock锁，当要修改某个段中的元素时，只要锁住对应的段即可（分段锁），这样相比于Hashtable容器锁住整个容器，减少了锁的粒度，大大提高了并发效率。  
      在JDK1.8版本的ConcurrentHashMap中，去除了段的概念，但它仍然高效的原因是进行插入、删除等结构性调整时锁hash桶（table数组中的元素），并且在扩容时，其他读写线程可以帮助正在扩容的线程一起进行扩容，同样减少了锁的粒度。

--------------------

## 5、往期佳文 ##

### 5.1、面试系列 ###

1、[吊打面试官之一面自我介绍][Link 1]  
2、[吊打面试官之一面项目介绍][Link 2]  
3、[吊打面试官之一面系统架构设计][Link 3]  
4、[吊打面试官之一面你负责哪一块][Link 4]  
5、[吊打面试官之一面试官提问][Link 5]  
6、[吊打面试官之一面你有什么问题吗][Link 6]

······持续更新中······

--------------------

### 5.2、技术系列 ###

1、[吊打面试官之分布式会话][Link 7]  
2、[吊打面试官之分布式锁][Link 8]  
3、[吊打面试官之乐观锁][Link 9]  
4、[吊打面试官之幂等性问题][Link 10]  
5、[吊打面试关之分布式事务][Link 11]  
6、[吊打面试官之项目线上问题排查][Link 12]

······持续更新中······

### 5.3、源码系列 ###

1、[源码分析之SpringBoot启动流程原理][SpringBoot]  
2、[源码分析之SpringBoot自动装配原理][SpringBoot 1]  
3、[源码分析之ArrayList容器][ArrayList]  
4、[源码分析之LinkedList容器][LinkedList]  
5、[码分析之HashMap容器][HashMap]

### 5.4、数据结构和算法系列 ###

1、[数据结构之八大数据结构][Link 13]  
2、[数据结构之动态查找树（二叉查找树，平衡二叉树，红黑树）][Link 14]

······持续更新中······

### 5.5、多线程系列 ###

1、[并发系列之初识多线程][Link 15]  
2、[并发系列之JMM内存模型][JMM]  
3、[并发系列之synchronized解析][synchronized]  
4、[并发系列之volatile解析][volatile]  
5、[并发系列之synchronized与volatile的区别][synchronized_volatile]  
6、[并发系列之Lock解析][Lock]  
7、[并发系列之synchronized与lock的区别][synchronized_lock]

······持续更新中······

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]: /images/20221022/ad5f4b361bd84556a4c809b72dd9b764.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/2839123ded5b4264862c8aeae6c54705.png
[Link 1]: https://blog.csdn.net/wtyicy/article/details/114933478
[Link 2]: https://blog.csdn.net/wtyicy/article/details/114983053
[Link 3]: https://blog.csdn.net/wtyicy/article/details/115005012
[Link 4]: https://blog.csdn.net/wtyicy/article/details/115064661
[Link 5]: https://blog.csdn.net/wtyicy/article/details/115296365
[Link 6]: https://blog.csdn.net/wtyicy/article/details/115402511
[Link 7]: https://blog.csdn.net/wtyicy/article/details/114685293
[Link 8]: https://blog.csdn.net/wtyicy/article/details/114915987
[Link 9]: https://blog.csdn.net/wtyicy/article/details/114915177
[Link 10]: https://blog.csdn.net/wtyicy/article/details/114888754
[Link 11]: https://blog.csdn.net/wtyicy/article/details/115081790
[Link 12]: https://blog.csdn.net/wtyicy/article/details/115292969
[SpringBoot]: https://blog.csdn.net/wtyicy/article/details/115181539
[SpringBoot 1]: https://blog.csdn.net/wtyicy/article/details/115233701
[ArrayList]: https://blog.csdn.net/wtyicy/article/details/115244565
[LinkedList]: https://blog.csdn.net/wtyicy/article/details/115314536
[HashMap]: https://blog.csdn.net/wtyicy/article/details/115365586
[Link 13]: https://blog.csdn.net/wtyicy/article/details/115342236
[Link 14]: https://blog.csdn.net/wtyicy/article/details/115353145
[Link 15]: https://blog.csdn.net/wtyicy/article/details/115386707
[JMM]: https://blog.csdn.net/wtyicy/article/details/115455467
[synchronized]: https://blog.csdn.net/wtyicy/article/details/115454573
[volatile]: https://blog.csdn.net/wtyicy/article/details/115502376
[synchronized_volatile]: https://blog.csdn.net/wtyicy/article/details/115512541
[Lock]: https://blog.csdn.net/wtyicy/article/details/115524613
[synchronized_lock]: https://blog.csdn.net/wtyicy/article/details/115536187