并发编程（十二）：ConcurrentHashMap源码分析

- 日理万妓 2023-06-04 10:59 18阅读 0赞

# 一，ConcurrentHashMap概述 #

## 1，ConcurrentHashMap ##

\* *ConcurrentHashMap* 和 *HashMap* 原理基本一致，就是在 *HashMap* 的基础上增加了锁处理，支持并发操作，在实现上比 *HashMap* 更复杂点。先比较与 JDK7，JDK8在实现上，修改原来通过 *Segment* 进行加锁的方式改为通过 *Node* 进行加锁，同时在链表方面，如果链表长度超过阈值，则转换为红黑树；红黑树部分没有分析，因为不会。。。

## 2，类图 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70][]

## 3，常量及常用API ##

### 3.1，常量 ###

// 最大允许长度
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 默认长度
    private static final int DEFAULT_CAPACITY = 16;
    
    // 最大数组长度-转数组使用
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 扩容因子
    private static final float LOAD_FACTOR = 0.75f;
    
    // 链表 -> 红黑树转换阈值
    static final int TREEIFY_THRESHOLD = 8;
    
    // 红黑水 -> 链表转换阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 最小树化容量，如果需要转换红黑树并且容量小于该值，则先扩容
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 扩容操作中，单个线程的最小步进
    // 数据迁移通过分段迁移，由多线程协调执行，最小段数量为16，则如果长度为16，由一个线程进行扩容
    private static final int MIN_TRANSFER_STRIDE = 16;
    
    // 扩容操作使用
    private static int RESIZE_STAMP_BITS = 16;
    
    // 扩容操作使用，进行sizeCtl高低位移动，进行扩容线程数判断
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    
    //最大扩容线程数量
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    
    // ForwardingNode的hash值，ForwardingNode是一种临时节点，在扩进行中才会出现，并且它不存储实际的数据，ForwardingNode继承自Node，默认hash初始化为-1
    static final int MOVED     = -1;
    
    // 红黑树的HASH值
    static final int TREEBIN   = -2;
    
    // ReservationNode的hash值，ReservationNode是一个保留节点，就是个占位符
    static final int RESERVED  = -3;
    
    // 用于和负数hash值进行 & 运算，将其转化为正数（绝对值不相等）
    static final int HASH_BITS = 0x7fffffff;
    
    // CPU的核心数
    static final int NCPU = Runtime.getRuntime().availableProcessors();

### 3.2，变量 ###

// 链表
    transient volatile Node<K,V>[] table;
    
    // 扩容时候的新链表
    private transient volatile Node<K,V>[] nextTable;
    
    // 分段计数，记录
    private transient volatile CounterCell[] counterCells;
    
    /*
     * 非常重要的一个属性，源码中的英文翻译，直译过来是下面的四行文字的意思
     *       sizeCtl = -1，表示有线程正在进行真正的初始化操作
     *       sizeCtl = -(1 + nThreads)，表示有nThreads个线程正在进行扩容操作
     *       sizeCtl > 0，表示接下来的真正的初始化操作中使用的容量，或者初始化/扩容完成后的阈值
     *       sizeCtl = 0，默认值，此时在真正的初始化操作中使用默认容量
     */
    private transient volatile int sizeCtl;
    
    // 扩容任务的起始下标
    private transient volatile int transferIndex;
    
    // CAS自旋锁标志位，用于初始化，或者counterCells扩容时
    private transient volatile int cellsBusy;
    
    // 计数器基本值，主要在没有碰到多线程竞争时使用，需要通过CAS进行更新
    private transient volatile long baseCount;
    
    /* Contended类 */
    // 当前统计数量
    volatile long value;

### 3.3，常用API ###

/* 初始化部分 */
    public ConcurrentHashMap();
    public ConcurrentHashMap(int initialCapacity);
    public ConcurrentHashMap(Map<? extends K, ? extends V> m);
    
    /* 写数据部分 */
    public V put(K key, V value);
    public void putAll(Map<? extends K, ? extends V> m);
    
    /* 读数据部分 */
    public V get(Object key);
    
    /* 移除数据部分 */
    public V remove(Object key);
    
    /* 获取长度 */
    public int size();

### 3.4，核心原子方法 ###

// 获取 i 索引处对象
    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);
    }
    
    // 把 i 索引处为 c 的对象替换为 v
    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);
    }
    
    // 把 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);
    }

# 四，源码分析 #

## 1，初始化源码分析 ##

### 1.1，ConcurrentHashMap(int initialCapacity) ###

\* ConcurrentHashMap(int initialCapacity)

public ConcurrentHashMap(int initialCapacity) {
    	// 校验参数合法性
    	if (initialCapacity < 0)
    		throw new IllegalArgumentException();
    	// 大于最大值，取最大值
    	// 合法数据，进行数据重处理，向上取整为2的整数次方
    	// 向上取整数倍为了再下标计算时更分散，该部分后续有机会在 HashMap 中分析
    	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
    			   MAXIMUM_CAPACITY :
    			   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    	this.sizeCtl = cap;
    }

\* tableSizeFor(int c)

private static final int tableSizeFor(int c) {
    	// 通过下列一系列或等于操作后，获取到的值肯定是2的整数次方
    	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;
    }

### 1.2，ConcurrentHashMap(Map<? extends K, ? extends V> m) ###

\* ConcurrentHashMap(Map<? extends K, ? extends V> m)

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    	// 初始化长度为默认长度，即16
    	this.sizeCtl = DEFAULT_CAPACITY;
    	// 调用 putAll 方法进行数据添加
    	// putAll 内部循环调用 putVal 方法，后续分析
    	putAll(m);
    }

## 2，put()源码分析 ##

### 2.1，put() 总述 ###

\* put(K key, V value)

public V put(K key, V value) {
    	// 直接调用 putVal() 进行数据添加
    	return putVal(key, value, false);
    }

\* putVal(K key, V value, boolean onlyIfAbsent)

final V putVal(K key, V value, boolean onlyIfAbsent) {
    	if (key == null || value == null) throw new NullPointerException();
    	// 获取hash值
    	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) {
    			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) {
    					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;
    }

\* spread(int h)：获取key值对应的hash值，此处注意不是下标

static final int spread(int h) {
    	// 此处用当前key哈希值的高16位与低16位按位异或之后，在于魔数进行与运算
    	// 步骤的目的是尽量使hash值分散，之后与(length - 1)进行与运算，尽量保证数据能均匀分散
    	// 这也是为什么长度要是2的整数次方，比如16的二进制是100000，减1就是11111，再进行与运算，尽量保证分散
    	return (h ^ (h >>> 16)) & HASH_BITS;
    }
    
    static final int HASH_BITS = 0x7fffffff;

### 2.2，put() 第一阶段：初始化阶段 ###

\* initTable()

private final Node<K,V>[] initTable() {
    	Node<K,V>[] tab; int sc;
    	// 此处通过自旋，保证初始化成功
    	while ((tab = table) == null || tab.length == 0) {
    		// sizeCtl 在初始化时候已经复制为长度，即tab.length
    		// sizeCtl 表示正在初始化或者正在扩容
    		if ((sc = sizeCtl) < 0)
    			Thread.yield();
    		// 初始化时候，将 SIZECTL 的值修改为 -1，该状态比较重要，后续多处会涉及
    		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
    			try {
    				// 再对 table 进行判断，确定为空时候进行初始化
    				if ((tab = table) == null || tab.length == 0) {
    					// 长度为0，取默认长度，即16
    					int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
    					// 初始化 Node 数组，并赋值给 table
    					@SuppressWarnings("unchecked")
    					Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
    					table = tab = nt;
    					// 此处的结果是 3/4 * n，即0.75 * n，也就是扩容因子
    					// 后续如果数量超过 sc 的数量，说明需要扩容
    					sc = n - (n >>> 2);
    				}
    			} finally {
    				sizeCtl = sc;
    			}
    			break;
    		}
    	}
    	return tab;
    }

### 2.3，put() 第二阶段（1）：数据统计阶段 ###

\* *ConcurrentHashMap* 数据统计采用分段统计。使用 CounterCell 数组存储每一段的数据数量，再获取总数据时，遍历求和。

\* addCount(long x, int check)

// x 表示增加数量
    // check 表示链表数量
    // 总数量增加后可能会触发扩容，即正式触发第三阶段
    private final void addCount(long x, int check) {
    	CounterCell[] as; long b, s;
    	// 首先对 CounterCell[] 进行判空，如果 CounterCell[] 为空，则依旧尝试通过CAS修改 baseCount 的值，由该值记录元素个数
    	// 如果CAS失败，说明存在线程竞争，则通过 CounterCell 记录个数
    	// CounterCell[] 不为空，直接通过 CounterCell 记录个数
    	if ((as = counterCells) != null ||
    		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
    		CounterCell a; long v; int m;
    		// 是否冲突，默认表示没有冲突
    		boolean uncontended = true;
    		// 计数表为空，直接调用下面方法
    		// 计数表元素为空，直接调用下面方法; 技术表元素不为空，则随机获取一个有效元素作为 CounterCell 进行CAS处理
    		// ThreadLocalRandom.getProbe() 随机数，和 m 即计数表长度进行与运算后，取一个有效的下标
    		// 通过CAS修改 CounterCell 的值，如果修改失败，说明存在线程竞争，调用下面方法
    		if (as == null || (m = as.length - 1) < 0 ||
    			(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
    			!(uncontended =
    			  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
    			// if条件走完后，没有递增成功，则进行递增操作
    			fullAddCount(x, uncontended);
    			return;
    		}
    		// 链表长度小于等于1，不考虑扩容
    		// 链表转红黑树需要满足两个条件：链表长度大于8，数组长度大于64
    		// 如果链表长度大于8，但是数组长度没有超过64，则先进行扩容操作
    		if (check <= 1)
    			return;
    		// 统计 ConcurrentHashMap 的元素个数
    		s = sumCount();
    	}
    	// >=0，表示该位置存在元素
    	if (check >= 0) {
    		Node<K,V>[] tab, nt; int n, sc;
    		// s表示当前元素总数，sizeCtl表示扩容阈值，大于表示需要扩容
    		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
    			   (n = tab.length) < MAXIMUM_CAPACITY) {
    			// 此处在扩容阶段再具体分析，涉及辅助扩容方面东西，此处正式开始第三阶段
    			int rs = resizeStamp(n);
    			if (sc < 0) {
    				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);
    			s = sumCount();
    		}
    	}
    }

\* fullAddCount(long x, boolean wasUncontended)：增加数量，该部分不涉及扩容

// x : 增加数量
    // wasUncontended：是否存在冲突
    private final void fullAddCount(long x, boolean wasUncontended) {
    	int h;
    	// 获取线程的 probe 值，值如果没有初始化，则进行初始化，并重置未冲突表示为true
    	if ((h = ThreadLocalRandom.getProbe()) == 0) {
    		ThreadLocalRandom.localInit(); 
    		h = ThreadLocalRandom.getProbe();
    		wasUncontended = true;
    	}
    	boolean collide = false;
    	for (;;) {
    		CounterCell[] as; CounterCell a; int n; long v;
    		// CounterCell[] 数组不为空，已经存在有效的 CounterCell 元素
    		if ((as = counterCells) != null && (n = as.length) > 0) {
    			// 获取下标，找到对应的 CounterCell 进行递增操作
    			if ((a = as[(n - 1) & h]) == null) {
    				// 为0表示不存在线程进行递增处理
    				if (cellsBusy == 0) {
    					// 初始化一个 CounterCell，并赋初值为递增值
    					CounterCell r = new CounterCell(x);
    					// 将 cellsBusy 状态改为正在进行递增处理
    					if (cellsBusy == 0 &&
    						U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
    						boolean created = false;
    						try {
    							// 将初始化的 CounterCell 添加到数组中
    							CounterCell[] rs; int m, j;
    							if ((rs = counterCells) != null &&
    								(m = rs.length) > 0 &&
    								rs[j = (m - 1) & h] == null) {
    								rs[j] = r;
    								created = true;
    							}
    						} finally {
    							cellsBusy = 0;
    						}
    						// 创建失败，说明存在竞争，则继续自旋处理
    						if (created)
    							break;
    						continue;
    					}
    				}
    				collide = false;
    			}
    			// 后续操作首先说明 CounterCell 不为空
    			// 貌似没有应用，先不用管
    			else if (!wasUncontended)
    				wasUncontended = true;
    			// 通过CAS递增 value 值，修改成功则执行完成
    			else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
    				break;
    			// 此处说明竞争下冲突，获取已经超过CPU数量，当前循环失败
    			else if (counterCells != as || n >= NCPU)
    				collide = false;
    			else if (!collide)
    				collide = true;
    			// 对 CounterCell 数组进行扩容，保证高并发下的操作
    			else if (cellsBusy == 0 &&
    					 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
    				try {
    					if (counterCells == as) {
    						CounterCell[] rs = new CounterCell[n << 1];
    						for (int i = 0; i < n; ++i)
    							rs[i] = as[i];
    						counterCells = rs;
    					}
    				} finally {
    					cellsBusy = 0;
    				}
    				collide = false;
    				continue;
    			}
    			h = ThreadLocalRandom.advanceProbe(h);
    		}
    		// cellsBusy 为0，表示没有线程在做初始化，修改值为1
    		// CounterCell[] 数组为空，但是不为null，如果不为空会走上一个if，如果为null会走下一个if
    		else if (cellsBusy == 0 && counterCells == as &&
    				 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
    			// 此处添加初始化标志
    			boolean init = false;
    			try {
    				// 第一个if已经进行了as复制，所以此处==，不存在竞争情况下基本成立
    				if (counterCells == as) {
    					// 初始化CounterCell[]数组，数组长度初始化为2
    					CounterCell[] rs = new CounterCell[2];
    					// 将递增的数量，复制给其中之一，
    					rs[h & 1] = new CounterCell(x);
    					counterCells = rs;
    					// 初始化为true
    					init = true;
    				}
    			// 递增完成后，重置值
    			} finally {
    				cellsBusy = 0;
    			}
    			if (init)
    				break;
    		}
    		// 上面两条都不符合，则直接对baseCount递增，CAS成功后返回
    		else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
    			break; 
    		// 否则进入自旋
    	}
    }

\* sumCount()：获取 ConcurrentHashMap 元素总数量

final long sumCount() {
    	CounterCell[] as = counterCells; CounterCell a;
    	// 如果不存在线程竞争，则 counterCells 为空，则数据存储在 baseCount 中
    	long sum = baseCount;
    	// counterCells 不为空，存在线程竞争，则遍历获取总数
    	if (as != null) {
    		for (int i = 0; i < as.length; ++i) {
    			if ((a = as[i]) != null)
    				sum += a.value;
    		}
    	}
    	return sum;
    }

### 2.4，put() 第二阶段（2）：扩容阶段 ###

\* 第三阶段扩容扩容阶段分为两部分内容，首先是 addCount() 部分的扩容操作，因为数量递增引起的扩容，算是正式开启扩容阶段；第二部分是 putVal() 时候的分支条件进行辅助扩容，是在已经有线程进行扩容的基础上，如果还存在线程进行数据操作，则进行辅助扩容。扩容部分应该是难度最大的一部分

\* addCount(long x, int check)：再探扩容触发条件

private final void addCount(long x, int check) {
    	CounterCell[] as; long b, s;
    	... // 中间部分省略，上面已经分析
    	if (check >= 0) {
    		Node<K,V>[] tab, nt; int n, sc;
    		// 如果已经超过了扩容阈值，达到了扩容条件，则进行扩容
    		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
    			   (n = tab.length) < MAXIMUM_CAPACITY) {
    			// 生成一个唯一的扩容戳，此处主要进行高低链转换
    			int rs = resizeStamp(n);
    			// sizeCtl小于0，说明有其他线程正在进行扩容处理，则此时sc已经经过扩容戳处理
    			if (sc < 0) {
    				// 这五个条件有一个为true，说明当前线程不再进行扩容处理
    				// sc >>> RESIZE_STAMP_SHIFT != rs，如果不存在线程竞争，则此时获取到的值应该相等，不等于说明存在竞争
    				// sc == rs + 1 ： 扩容已经结束
    				// sc == rs + MAX_RESIZERS：帮助线程已经最大值
    				// (nt = nextTable) == null：扩容已经结束
    				// transferIndex <= 0：表示所有的扩容任务已经被领完，没有剩余的hash桶来给自己线程做扩容
    				if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
    					sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
    					transferIndex <= 0)
    					break;
    				// 当前线程尝试帮助扩容，如果成功，则进行扩容
    				// sc + 1：表示扩容线程数量递增
    				if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
    					transfer(tab, nt);
    			}
    			// sizeCtl > 0，直接进行扩容处理
    			// rs << RESIZE_STAMP_SHIFT：将sc设置为一个负数，+2表示有一个线程在执行扩容任务
    			// 计算完resizeStamp()再继续看，结果集为 00000000 00000000 10000000 00011011
    			// 则sc替换后的值应该为 10000000 00011011 00000000 00000010，此时低16位就表示并行线程数，后续表示并行线程数也是对该值加1
    			else if (U.compareAndSwapInt(this, SIZECTL, sc,
    										 (rs << RESIZE_STAMP_SHIFT) + 2))
    				transfer(tab, null);
    			s = sumCount();
    		}
    	}
    }

\* resizeStamp(int n)：扩容戳详细分析

// n：表长度
    static final int resizeStamp(int n) {
    	// Integer.numberOfLeadingZeros 这个方法是返回无符号整数 n 最高位非 0 位前面的 0 的个数
    	// 比如 16 的32位是 00000000 00000000 00000000 00010000，则值为27
    	// RESIZE_STAMP_BITS为16，就是1右移15位，及 00000000 00000000 10000000 00000000
    	// 最终结果就是 00000000 00000000 10000000 00011011
    	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

\* transfer(Node<K,V>\[\] tab, Node<K,V>\[\] nextTab)：扩容，扩容是核心内容，重点在于数据迁移及链表部分处理。ConcurrentHashMap 内容通过多线程来进行协调扩容，把 Node 数组作为一个多线程共享的共享队列，然后通过指针来划分每个线程负责的区间，每个线程区间通过线程逆向遍历来进行扩容。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    	int n = tab.length, stride;
    	// 一个CPU一次最少默认处理16个hash位置，即步进
    	// 大于则计算，小于则取默认16，由一个CPU执行
    	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    		stride = MIN_TRANSFER_STRIDE;
    	// nextTab 表示需要扩容的表，如果为空，则初始化，注意初始化长度为当前长度的二倍
    	if (nextTab == null) {            
    		try {
    			@SuppressWarnings("unchecked")
    			Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
    			nextTab = nt;
    		} catch (Throwable ex) {      
    			sizeCtl = Integer.MAX_VALUE;
    			return;
    		}
    		nextTable = nextTab;
    		transferIndex = n;
    	}
    	// 新数组长度
    	int nextn = nextTab.length;
    	// 构建一个 ForwardingNode 节点，表示一个正在迁移的Node，hash值为-1(MOVED)，表示构建一个标示位
    	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    	// 下标推进标识，为true，说明需要推进，为false，说明未处理完成
    	// 推进表示推进一个 stride 的区间
    	boolean advance = true;
    	// 是否已经完成，默认false，即对当前 stride 区间数据迁移完成
    	boolean finishing = false; 
    	// i表示当前处理的槽位序号，bound表示需要处理的槽位边界
    	for (int i = 0, bound = 0;;) {
    		Node<K,V> f; int fh;
    		// 该循环通过CAS不断尝试为当前线程分配任务，即一个 stride
    		// 线程对 stride 区间处理，从尾部到头部倒叙处理
    		// 如果当前线程已经被分配过 stride 区域，那么通过--i递减后继续进行节点迁移
    		while (advance) {
    			int nextIndex, nextBound;
    			// bound 表示 stride 边界的头节点
    			// i 表示 stride 边界的尾结点
    			// 因为是倒叙进行处理，所以在任务处理中， i 肯定大于 bound
    			if (--i >= bound || finishing)
    				advance = false;
    			// transferIndex 表示扩容前数组长度，赋值给 nextIndex
    			else if ((nextIndex = transferIndex) <= 0) {
    				i = -1;
    				advance = false;
    			}
    			// 上一个if分支已经给 nextIndex 赋值
    			// 假如数组长度目前为16，则 nextIndex为16，nextBound为0，当前任务区间为 [0, 15]
    			else if (U.compareAndSwapInt
    					 (this, TRANSFERINDEX, nextIndex,
    					  nextBound = (nextIndex > stride ?
    								   nextIndex - stride : 0))) {
    				bound = nextBound;
    				i = nextIndex - 1;
    				advance = false;
    			}
    		}
    		// i < 0 说明已经遍历完成，也就是当前线程已经处理完成所有的 stride
    		if (i < 0 || i >= n || i + n >= nextn) {
    			int sc;
    			// 总任务已经完成
    			if (finishing) {
    				// 对相关参数进行重置后退出
    				nextTable = null;
    				table = nextTab;
    				// 更新扩容阈值
    				sizeCtl = (n << 1) - (n >>> 1);
    				return;
    			}
    			// 此处表示总任务没有完成，只是当前线程已经处理完成任务
    			// 之前有提过多线程同时处理时对 sizeCtl 进行高低位操作后用来计数，执行完成后，对应计数递减
    			if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
    				// 在扩容时，会对 SIZECTL 进行基本计算赋值 (rs << RESIZE_STAMP_SHIFT) + 2)
    				// 所以在对最后一个线程进行处理时，必然存在条件成立
    				// 如果条件不成立，说明已经全部执行完成，直接退出
    				if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
    					return;
    				// 任务执行完成，扩容结束没更新finishing变量
    				finishing = advance = true;
    				// 再次循环检查一次
    				i = n; 
    			}
    		}
    		// 如果i位置元素空，则放入刚才初始化的 ForwardingNode 空节点，标识该位置正在迁移
    		else if ((f = tabAt(tab, i)) == null)
    			advance = casTabAt(tab, i, null, fwd);
    		// 表示位置已经完成了迁移
    		else if ((fh = f.hash) == MOVED)
    			advance = true; 
    		else {
    			// 对当前遍历的hash位置进行迁移，加锁处理，这也是JDK8不同于JDK7的一个主要地方，对Node加锁
    			// 再分析这部分前先对链表迁移的高低链原理进行分析
    			synchronized (f) {
    				...
    			}
    		}
    	}
    }

\* 链表迁移的高低链原理分析

// 首先明确一个概念，Map的下标计算是通过 hash & length 获取到的下标，而不是单纯的 hash 表示
    // 所以在每一个链表表示的节点上，虽然众多元素下标值冲突，挂载同一个下标点下，但是 hash 值基本上是不一致的
    // 在这种情况下，链表迁移的hash链表示，其实是对 hash 值二进制下，与原数组长度进行与操作后进行非0判断
    // 该位置数字如果为0，则表示低链，该位置数组如果为1，则表示高链
    // 低链说明该链上的元素在当前索引不变
    // 高链表示该链上的元素会随着扩容同时增加一个扩容长度的下标，比如扩容前长度为16，下标为4，则扩容后下标为20
    // 计算方式如下，比如对于hash值4和20的元素，在16原始长度下
    4	= 00000000 00000000 00000000 00000100
    15	= 00000000 00000000 00000000 00001111	&
    ---------------------------------------------
    	  00000000 00000000 00000000 00000100 = 4 (下标为4)
    	  
    20	= 00000000 00000000 00000000 00010100
    15	= 00000000 00000000 00000000 00001111	&
    ---------------------------------------------
    	  00000000 00000000 00000000 00000100 = 4 (下标为4)
    	  
    // 如上，在16长度下，对于4和20，下标都为4，此时如果对16进行扩容，扩容到32
    4	= 00000000 00000000 00000000 00000100
    16	= 00000000 00000000 00000000 00010000	&
    ---------------------------------------------
    	  00000000 00000000 00000000 00000100 = 4 (下标为4)
    	  
    20	= 00000000 00000000 00000000 00010100
    31	= 00000000 00000000 00000000 00010000	&
    ---------------------------------------------
    	  00000000 00000000 00000000 00010100 = 20 (下标为20 = 4 + 16)
    	  
    // 这个例子就是说明，数组库容后，(新数组长度 - 1)最高非0位为倒数第五位，
    // 则对4和20的第五位进行判断，4为0，则在低链。20为1，则在高链
    // 数据迁移时，低链位置不动，高链位置 = 原位置 + 扩容长度
    // 继续往上加冲突索引，到36,52,68...也是遵循这个规则

\* 继续分析槽点元素迁移

// 对当前遍历的hash位置进行迁移，加锁处理，这也是JDK8不同于JDK7的一个主要地方，对Node加锁
    // 再分析这部分前先对链表迁移的高低链原理进行分析
    synchronized (f) {
    	// 判断当前必然有值
    	if (tabAt(tab, i) == f) {
    		Node<K,V> ln, hn;
    		// hash 值大于0，说明当前节点表示单元素或者链表
    		if (fh >= 0) {
    			// n 为原数组长度，下标位置计算，是 fh & (n - 1)
    			// 此处直接 & n，为了获取元素 hash 值对应长度1位置的数字是否为0
    			int runBit = fh & n;
    			Node<K,V> lastRun = f;
    			// 因为 Node 为单向链表，此处直接遍历到尾部，获取到尾部节点
    			for (Node<K,V> p = f.next; p != null; p = p.next) {
    				int b = p.hash & n;
    				if (b != runBit) {
    					runBit = b;
    					lastRun = p;
    				}
    			}
    			// 先把尾部节点进行高低链归属处理
    			// 为0表示在低链
    			// 为1表示在高链
    			if (runBit == 0) {
    				ln = lastRun; // low
    				hn = null;
    			}
    			else {
    				hn = lastRun; // high
    				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);
    			}
    			// 处理完成后，低链位置不动，高链位置递增一个扩容位置
    			setTabAt(nextTab, i, ln);
    			setTabAt(nextTab, i + n, hn);
    			// 把旧表中的hash桶中放置标识位节点，表示已经被处理
    			setTabAt(tab, i, fwd);
    			advance = true;
    		}
    		// 表示红黑树，红黑树部分真TM不会，以后会了再补充吧 TODO
    		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;
    			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;
    				}
    			}
    			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;
    			setTabAt(nextTab, i, ln);
    			setTabAt(nextTab, i + n, hn);
    			setTabAt(tab, i, fwd);
    			advance = true;
    		}
    	}
    }

### 2.5，put() 第三阶段：辅助扩容阶段 ###

\* helpTransfer(Node<K,V>\[\] tab, Node<K,V> f)

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    	Node<K,V>[] nextTab; int sc;
    	// f instanceof ForwardingNode 表示当前节点正在扩容，则辅助扩容
    	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) {
    			// (sc >>> RESIZE_STAMP_SHIFT) != rs：说明扩容已经结束了
    			// sc == rs + 1：说明扩容已经结束 这两个条件根据扩容戳的高低位转换后判断可以得出
    			// sc == rs + MAX_RESIZERS：已经到达最大扩容数，不再参与
    			// transferIndex <= 0：所有hash位置已经分配完毕
    			if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
    				sc == rs + MAX_RESIZERS || transferIndex <= 0)
    				break;
    			// 参与扩容，扩容线程数+1，进行库容处理
    			if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
    				transfer(tab, nextTab);
    				break;
    			}
    		}
    		return nextTab;
    	}
    	return table;
    }

### 2.6，put() 第四阶段：链表到红黑树构造阶段 ###

\* 继续回到 putVal() 方法中，单掕出来查看链表到红黑树构造的代码，红黑树不分析，因为不会

else {
    	V oldVal = null;
    	// 对Node进行加锁，同步处理
    	synchronized (f) {
    		// 再次判断下标位置是否是f节点
    		if (tabAt(tab, i) == f) {
    			// 头节点值大于0，说明是链表
    			if (fh >= 0) {
    				// 记录链表长度
    				binCount = 1;
    				// 遍历链表
    				for (Node<K,V> e = f;; ++binCount) {
    					K ek;
    					// 判断是否是相同hash，hash相同进行value替换
    					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;
    					}
    				}
    			}
    			// 头节点置小于0，说明是红黑树
    			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;
    				}
    			}
    		}
    	}
    	// 此处是链表长度大于8，进行红黑树处理
    	if (binCount != 0) {
    		if (binCount >= TREEIFY_THRESHOLD)
    			treeifyBin(tab, i);
    		if (oldVal != null)
    			return oldVal;
    		break;
    	}
    }

\* treeifyBin(Node<K,V>\[\] tab, int index)：链表转树处理，此处多跟一步，为了说明在链表长度大于阈值后，还要判断数组长度是否大于阈值，不大于后，直接扩容

private final void treeifyBin(Node<K,V>[] tab, int index) {
    	Node<K,V> b; int n, sc;
    	if (tab != null) {
    		// 判断数组长度是否大于阈值64，如果不大于，首先触发扩容
    		if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
    			tryPresize(n << 1);
    		// 条件全部满足，触发树
    		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
    			synchronized (b) {
    				if (tabAt(tab, index) == b) {
    					TreeNode<K,V> hd = null, tl = null;
    					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;
    					}
    					setTabAt(tab, index, new TreeBin<K,V>(hd));
    				}
    			}
    		}
    	}
    }

## 3，get()源码分析 ##

\* get(Object key)

public V get(Object key) {
    	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    	// 获取key对应的hash值
    	int h = spread(key.hashCode());
    	// 数组不为空，且数组对应元素不为空，继续寻找
    	if ((tab = table) != null && (n = tab.length) > 0 &&
    		(e = tabAt(tab, (n - 1) & h)) != null) {
    		// hash值匹配，直接返回值
    		if ((eh = e.hash) == h) {
    			if ((ek = e.key) == key || (ek != null && key.equals(ek)))
    				return e.val;
    		}
    		// hash值为0，表示为红黑数，不分析。。。
    		else if (eh < 0)
    			return (p = e.find(h, key)) != null ? p.val : null;
    		// 走到此处说明为链表。遍历树不对hash，获取值
    		while ((e = e.next) != null) {
    			if (e.hash == h &&
    				((ek = e.key) == key || (ek != null && key.equals(ek))))
    				return e.val;
    		}
    	}
    	return null;
    }

## 4，remove()源码分析 ##

\* remove(Object key)

public V remove(Object key) {
    	// 移除节点，并返回当前节点，不存在返回null
    	return replaceNode(key, null, null);
    }

\* replaceNode(Object key, V value, Object cv)

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;
    		// 数组正在扩容中，辅助扩容
    		else if ((fh = f.hash) == MOVED)
    			tab = helpTransfer(tab, f);
    		else {
    			// 节点元素不为空，判断移除
    			V oldVal = null;
    			boolean validated = false;
    			synchronized (f) {
    				// 二次校验
    				if (tabAt(tab, i) == f) {
    					// 当前下标元素存在，为单个元素或者链表
    					if (fh >= 0) {
    						validated = true;
    						// 遍历当前节点的链表进行处理
    						for (Node<K,V> e = f, pred = null;;) {
    							K ek;
    							// 此部分表示找到对应的hash值
    							// 然后移除该节点，将后续节点填充
    							if (e.hash == hash &&
    								((ek = e.key) == key ||
    								 (ek != null && key.equals(ek)))) {
    								V ev = e.val;
    								if (cv == null || cv == ev ||
    									(ev != null && cv.equals(ev))) {
    									oldVal = ev;
    									if (value != null)
    										e.val = value;
    									else if (pred != null)
    										pred.next = e.next;
    									else
    										setTabAt(tab, i, e.next);
    								}
    								break;
    							}
    							pred = e;
    							if ((e = e.next) == null)
    								break;
    						}
    					}
    					// 红黑树，不分析。。。
    					else if (f instanceof TreeBin) {
    						validated = true;
    						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) {
    							V pv = p.val;
    							if (cv == null || cv == pv ||
    								(pv != null && cv.equals(pv))) {
    								oldVal = pv;
    								if (value != null)
    									p.val = value;
    								else if (t.removeTreeNode(p))
    									setTabAt(tab, i, untreeify(t.first));
    							}
    						}
    					}
    				}
    			}
    			if (validated) {
    				// 返回oldValue
    				if (oldVal != null) {
    					if (value == null)
    						addCount(-1L, -1);
    					return oldVal;
    				}
    				break;
    			}
    		}
    	}
    	return null;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]: /images/20230601/3ff8b596590c47888d0adf121175139b.png