线程安全集合类概述
线程安全集合类可以分为三大类：
- 遗留的线程安全集合如 Hashtable ， Vector
- 使用 Collections 装饰的线程安全集合（每个方法都加上了 sychronized，性能不是很高），如：
- Collections.synchronizedCollection
- Collections.synchronizedList
- Collections.synchronizedMap
- Collections.synchronizedSet
- ....
- java.util.concurrent.*
重点介绍 java.util.concurrent.* 下的线程安全集合类，可以发现它们有规律，里面包含三类关键词： Blocking、CopyOnWrite、Concurrent
- Blocking 大部分实现基于锁（ReentrantLock），并提供用来阻塞的方法（例如阻塞队列：put 时队列满则阻塞，get 时队列空则阻塞）
- CopyOnWrite 之类容器修改开销相对较重（适用于读多写少）
- Concurrent 类型的容器
- 内部很多操作使用 cas 优化，一般可以提供较高吞吐量
- 弱一致性
- 遍历时弱一致性，例如，当利用迭代器遍历时，如果容器发生修改，迭代器仍然可以继续进行遍历，这时内容是旧的
- 求 size 弱一致性，size 操作未必是 100% 准确
- 读取弱一致性
遍历时如果发生了修改，对于非安全容器来讲，使用 fail-fast 机制也就是让遍历立刻失败，抛出 ConcurrentModificationException，不再继续遍历
对于安全容器，使用 fail-safe 机制，遍历还可以继续
ConcurrentHashMap 计数
多个方法（get put），有线程安全问题
map = new HashMap<String, Integer>(); for (String word : words) { Integer counter = map.get(word); int newValue = counter == null ? 1 : counter + 1; map.put(word, newValue); }
改为：
computeIfAbsent 传入 key 和一个关于 key 的 lambda 表达式。如果 key 不存在，根据 key 和 lambda 表达式计算得到 value，返回 value 的最新值。
LongAdder 累加
map = new ConcurrentHashMap<String, LongAdder>(); for (String word : words) { // 注意不能使用 putIfAbsent，此方法返回的是上一次的 value，首次调用返回 null LongAdder longAdder = map.computeIfAbsent(word, (key) -> new LongAdder()); longAdder.increment() }
注意 computeIfAbsent 和 putIfAbsent 的区别
它们俩都是不存在才会放入
computeIfAbsent 返回的是操作后的值，putIfAbsent 返回的是操作前的值
Map<String, Integer> map = new ConcurrentHashMap<>(); Integer v = map.computeIfAbsent("a3", (key) -> (key.length()+2)); System.out.println(v);//4 v = map.computeIfAbsent("a3", (key) -> (key.length()+8)); System.out.println(v); //4 Integer b = map.putIfAbsent("a5", 5); System.out.println(b);//null b = map.putIfAbsent("a5", 10); System.out.println(b);//5
HashMap
扩容
达到负载因子后扩容，冲突链表缩短，查找性能提升
- jdk7 每次加元素，加到链表头，多线程扩容时有死链问题
- 而 jdk8 每次加元素，加到链表尾，多线程扩容时，避免了 jdk7 中的死链问题，但是有丢数据问题
JDK7 扩容问题：并发死链（头插）
在两个线程同时对 HashMap 进行扩容时，可能会产生死链。
关键是，每次哈希冲突链表，会把新元素加到链表头。
public static void main(String[] args) { // 测试 java 7 中哪些数字的 hash 结果相等 System.out.println("长度为16时，桶下标为1的key"); for (int i = 0; i < 64; i++) { if (hash(i) % 16 == 1) { System.out.println(i); } } System.out.println("长度为32时，桶下标为1的key"); for (int i = 0; i < 64; i++) { if (hash(i) % 32 == 1) { System.out.println(i); } } // 1, 35, 16, 50 当大小为16时，它们在一个桶内 final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // 放 12 个元素 map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); map.put(6, null); map.put(7, null); map.put(8, null); map.put(9, null); map.put(10, null); map.put(16, null); map.put(35, null); map.put(1, null); System.out.println("扩容前大小[main]:"+map.size());
new Thread() { @Override public void run() { // 放第 13 个元素, 发生扩容。16 扩到 32 map.put(50, null); System.out.println("扩容后大小[Thread-0]:"+map.size()); } }.start();
new Thread() { @Override public void run() { // 放第 13 个元素, 发生扩容。16 扩到 32 map.put(50, null); System.out.println("扩容后大小[Thread-1]:"+map.size()); } }.start(); }
final static int hash(Object k) { int h = 0; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
扩容源码
// 将 table 迁移至 newTable void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; // 1 处 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); // 2 处 // 将新元素加入 newTable[i], 原 newTable[i] 作为新元素的 next e.next = newTable[i]; newTable[i] = e; e = next; } } }
产生死链的过程
原始链表，格式：[下标] (key,next) [1] (1,35)->(35,16)->(16,null) 线程 a 执行到 1 处 ，此时局部变量 e 为 (1,35)，而局部变量 next 为 (35,16) 线程 a 挂起 线程 b 开始执行 第一次循环 [1] (1,null) 第二次循环 [1] (35,1)->(1,null) 第三次循环 [1] (35,1)->(1,null) [17] (16,null) 切换回线程 a，此时局部变量 e 和 next 被恢复，引用没变但内容变了：e 的内容被改为 (1,null)，而 next 的内 容被改为 (35,1) 并链向 (1,null) 第一次循环 [1] (1,null) 第二次循环，注意这时 e 是 (35,1) 并链向 (1,null) 所以 next 又是 (1,null) [1] (35,1)->(1,null) 第三次循环，e 是 (1,null)，而 next 是 null，但 e 被放入链表头，这样 e.next 变成了 35 （2 处） [1] (1,35)->(35,1)->(1,35) 已经是死链了
JDK8 ConcurrentHashMap
重要属性和内部类
// 默认为0。如果显示指定了初始容量，则为这个初始容量。如果没有显示指定，第一次 initTable 时判断 <=0 就会默认16 // 当正在初始化时, 为 -1 // 当扩容时, 为 -(1 + 扩容线程数) // 当初始化或扩容完成后，为 下一次的扩容的阈值大小（容量的 3/4） private transient volatile int sizeCtl; // 整个 ConcurrentHashMap 就是一个 Node[] static class Node<K,V> implements Map.Entry<K,V> {} // hash 表 transient volatile Node<K,V>[] table; // 扩容时的 新 hash 表 private transient volatile Node<K,V>[] nextTable; // 扩容时如果某个 bin 迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点 static final class ForwardingNode<K,V> extends Node<K,V> {} // 用在 compute 以及 computeIfAbsent 时, 用来占位, 计算完成后替换为普通 Node static final class ReservationNode<K,V> extends Node<K,V> {} // 作为 treebin （红黑树）的头节点, 存储 root 和 first（链表长度超过 8 时转为红黑树。长度小于 64 ，会先扩容） static final class TreeBin<K,V> extends Node<K,V> {} // 作为 treebin （红黑树）的节点, 存储 parent, left, right static final class TreeNode<K,V> extends Node<K,V> {}
某个 bin 已经扩容完毕，搬到新的 hashTable，加一个 ForwardingNode 作为标志。这样来 get 的时候就知道要去新的表查
容量小于 64 时，有 bin 链表长度超过 8 时，会先扩容
如果容量大于 64 时，有 bin 链表长度超过 8 时，会转换为红黑树
重要方法
// 获取 Node[] 中第 i 个 Node static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) // cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) // 直接修改 Node[] 中第 i 个 Node 的值, v 为新值 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)
构造器分析
可以看到实现了懒惰初始化，在构造方法中仅仅计算了 table 的大小，以后在第一次使用时才会真正创建
初始容量，负载因子，并发度
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
// 1+初始容量/负载因子
long size = (long)(1.0 + (long)initialCapacity / loadFactor); // tableSizeFor 仍然是保证计算的大小是 2^n, 即 16,32,64 ... int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }
tabAt / setTabAt / casTabAt
虽然上面的table变量加了volatile，但也只能保证其引用的可见性，并不能确保其数组中的对象是否是最新的，所以需要Unsafe类volatile式地拿到最新的Node。
/** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by iterators. */ transient volatile Node<K,V>[] table; /** * The next table to use; non-null only while resizing. */ private transient volatile Node<K,V>[] nextTable; static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; //...... } private static final sun.misc.Unsafe U; @SuppressWarnings("unchecked") 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); } 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); } static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) { U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }
get 流程（全程无锁）
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // spread 方法能确保返回结果是正数（.hashCode() 方法可能返回负数。而负数在后面有另外的含义）。h 就是后面要用到的真正的哈希码 int h = spread(key.hashCode());
// table 不为空，并且 table 里面有元素（长度大于0），才继续去寻找 if ((tab = table) != null && (n = tab.length) > 0 &&
// (n-1)&h 哈希码与长度按位与，就相当于取模运算（前提时长度是2的n次方）。然后获得到所在bin链表的头节点。头节点不为空 (e = tabAt(tab, (n - 1) & h)) != null) { // 如果头结点已经是要查找的 key（先比较头节点key的哈希码和当前get值的哈希码） if ((eh = e.hash) == h) {
// 比较完哈希码了，进一步比较头节点 key 值和当前 get 值是否相等。 == 比较为同一对象 || equals比较值相同 都可以认为是相等的 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } // 所在 bin 的头节点的 hash 为负数表示该 bin 在【扩容中-1】或是 【treebin-2】, 这时调用 ForwardingNode 或 Treebin 的 find 方法来查找
// 1.扩容中：原 table 头节点会变成 ForwardingNode，它的 hash 就是负数（-1）。同时 ForwardingNode 节点实现了 find 方法。
// 2.treebin：红黑树的头节点，hash 是负数（-2）。treebin 节点也实现了 find 方法 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null;
// 正常遍历链表, 用 == 或 equals 比较 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } }
// 没有查找到的情况：1.table为null 2.table 的长度为0 3.元素所在位置bin的头节点为null
return null; }
put 流程（锁bin链表头，扩容时帮忙扩容，扩容完才真正 put）
以下数组简称（table），链表简称（bin）
public V put(K key, V value) {
return putVal(key, value, false);
}
// onlyIfAbsent 为 true：key只有第一次放才会放进去，后面都不放进去。put 方法默认是 fasle ，也就是每次都会放进去
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 都不能为 null (普通 HashMap 可以为 null) if (key == null || value == null) throw new NullPointerException(); // 其中 spread 方法会综合高位低位, 具有更好的 hash 性。保证是正整数（hash 负数有特殊含义：-1 ForwardingNode 正在扩容；-2 treebin 红黑树） int hash = spread(key.hashCode());
// bin 所在链表长度 int binCount = 0;
// 一个死循环，无递增和结束条件 for (Node<K,V>[] tab = table;;) { // f 是链表头节点 // fh 是链表头结点的 hash // i 是链表在 table 中的下标 Node<K,V> f; int n, i, fh; // 因为是懒创建。所以判断 table 为 null 或长度为0，要创建 table if (tab == null || (n = tab.length) == 0) // 初始化 table 使用了 cas, 无需 synchronized 创建成功, 进入下一轮循环 tab = initTable(); // 链表头节点为 null（自己这个下标没有冲突），cas null->当前节点 作为头节点 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 添加链表头使用了 cas（前值为null，改为当前要）, 无需 synchronized if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
// cas 成功，break。如果 cas 失败，会进行下一次循环 break;
} // 如果头节点是 ForwardingNode(hash是MOVED-1)，帮忙扩容。直到扩容完毕，才会 put
else if ((fh = f.hash) == MOVED) // 帮忙之后, 进入下一轮循环
tab = helpTransfer(tab, f);
// 更新链表中相同的key，或把新key添加到链表尾 else { V oldVal = null; // 锁住当前bin所在链表头节点即可
synchronized (f) { // 再次确认链表头节点没有被移动 if (tabAt(tab, i) == f) { // hash >= 0是链表普通节点。小于0：-1正在扩容；-2红黑树Treebin if (fh >= 0) { binCount = 1; // 遍历同一 hash 所在的链表 for (Node<K,V> e = f;; ++binCount) { K ek; // 如果这个 Key 之前已经有了，则更新val 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; // 已经是最后的节点了还没退出循环, 说明之前没有这个key，新增 Node, 追加至链表尾 if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } // hash 小于0。判断是否红黑树 else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; // putTreeVal 会看 key 是否已经在树中, 是, 则返回对应的 TreeNode 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) // 如果链表长度 >= 树化阈值(8), 进行链表转为红黑树 treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } // 增加 size 计数 addCount(1L, binCount); return null; }
initTable 方法（CAS 设置 sizeCtl 为 -1 保证只有一个线程初始化）
懒惰初始化，得保证只有一个线程能把 table 创建出来（CAS）
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; // 如果没有被创建，进入循环不断尝试
while ((tab = table) == null || tab.length == 0) {
// cas 设置 sizeCtl 从 初始容量->-1 失败的，会在下一次循环来到这里满足这个条件 if ((sc = sizeCtl) < 0)
// 让出CPU使用权 Thread.yield(); // cas 尝试将 sizeCtl 从 sc即初始容量 设置为 -1（sizeCtl 如果没有显示指定，默认是0。-1表示正在初始化table） else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 获得锁, 创建 table, 这时其它线程会在 while() 循环中 yield 直至 table 创建 try { if ((tab = table) == null || tab.length == 0) {
// 初始容量取 sc，sc没有显示指定，默认是0。那么容量取默认的 16 int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 其实就是创建了一个 node 数组，容量为 n Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt;
// init 完成。重新计算 sc, 代表下次扩容时的阈值 sc = n - (n >>> 2); } } finally {
// 将计算出的下次扩容阈值(正数)赋值给 sizeCtl（本来是-1）。
// 其它在死循环等待的线程终于又进入了 else if 然后 cas
// sizeCtl 不一样了，cas 会失败，然后再次 while 循环，判断 table 已经不为 null 了，就会退出 while 循环
sizeCtl = sc; } break; } } return tab; }
addCount 增加计数（累加单元，达阈值触发扩容）
put 成功后要增加计数。采取了 LongAdder 类似的累加单元方法，提高性能 addCount 时，如果链表长度大于阈值，还会去进行扩容
addCount(1L, binCount);
addCount 时，如果元素个数大于下次扩容的阈值（sizeCtl），还会在这里触发扩容
// check 是之前 binCount 的个数 private final void addCount(long x, int check) { CounterCell[] as; long b, s;
if ( // 已经有了 counterCells, 向 cell 累加 (as = counterCells) != null || // 还没有, 向 baseCount 累加 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x) ) {
CounterCell a; long v; int m; boolean uncontended = true;
if ( // 还没有 counterCells 累加单元数组，进入 fullAddCount 创建 as == null || (m = as.length - 1) < 0 || // 还没有 cell 累加单元，进入 fullAddCount 创建 (a = as[ThreadLocalRandom.getProbe() & m]) == null || // 前两个条件都不满足，也就是说累加单元数组和累加单元都有了。进行 cas 累加，从前值到+x
// cell cas 增加计数失败。也会进入 fullAddCount 进行累加重试（循环） !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) ) { // 创建累加单元数组和cell 或 进行累加重试 fullAddCount(x, uncontended); return; }
// bin 链表长度大于1，可能会进行扩容，要往下走 if (check <= 1) return;
// 获取元素个数 s = sumCount(); }
if (check >= 0) { Node<K,V>[] tab, nt; int n, sc;
// sizeCtl 下次扩容的阈值。大于这个阈值 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc < 0 说明正在扩容 if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break;
// 正在扩容 且 newtable 已经创建了，去帮忙扩容（可能就是进入下个 else if 且 cas 成功的线程在扩容） if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // 大于阈值sizeCtl，需要扩容，这时没有正在扩容，且 newtable 未创建。那么去扩容：先把 sc 改为 -1, 再 transfer else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } } }
Size 计算流程（计数不是完全准确）
size 计算实际发生在 put，remove 改变集合元素的操作之中，以及 size() 方法
- 没有竞争发生，向 baseCount 累加计数
- 有竞争发生，新建 counterCells，向其中的一个 cell 累加计数
- counterCells 初始有两个 cell
- 如果计数竞争比较激烈，会创建新的 cell 来累加计数
public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } final long sumCount() { CounterCell[] as = counterCells; CounterCell a; // 将 baseCount 计数与所有 cell 计数累加 long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }
transfer 流程（锁bin链表头，）
扩容时以每个 bin 链表为粒度加锁，处理完这个链表后，释放锁
高位链表 和 低位链表 是什么？
比如容量是 16，扩容到 32
- hash 是 9 的原来放在下标 9，到新 table 中还是在下标 9
- hash 是 20 的原来放在下标 4，到新 table 中要放到下标 20（+16）
- hash 是 65 的原来放在下标 1，到新 table 中要放到下标 1
总结：
- 低位链表，就是那些搬到新 table 后，下标不变的
- 高位链表，就是那些搬到新 table 后，下标加n（原本的）的
那怎么区分 哪些节点在低位链表 哪些节点在高位链表中呢？
我们知道，当 n 为 2 的 n 次时
- hash & (n-1) 相当于取模运算（位运算比 % 效率高，这也是为什么容量要为 2 的 n 次的原因），即求出把元素放在哪个 bin
- hash & n 为0表明是搬移后下标不变的低位链表节点。不为0表明是需要下标 +n 的高位链表节点。
————————————————————————
4&15= 4 4&31 = 4
4&16=0 （=0，低位链表节点，搬移后下标不变）
————————————————————————
20&15=4 20&31=20
20&16=16 （!=0，高位链表节点，搬移后下标+16）
————————————————————————
65&15=1 65&31=1
65&16=0 （=0，低位链表节点，搬移后下标不变）
————————————————————————
注意想一下，get 全程无锁，为什么可以保证扩容时的正确性？
- 搬移时，给bin链表头节点加了sychronized，put时也给bin链表头节点加了sychronized，保证了put和扩容不会同时修改一个链表
- 搬移每个链表的时候，原 table 的链表并没有改变，所以正在搬移这个bin链表的时候，是从原table的链表中取到的
- 链表搬移完成后，把链表头节点赋值为 ForwardingNode，赋值操作是原子且 volatile 的。所以这个链表搬移完 但其它链表还没搬完 整体扩容还没完成时，get 时是通过 ForwardingNode 从 nextTab 取到的
- 全部扩容完成后，table = nextTab，赋值操作是原子的且 table 是 volatie 的。get 就直接从新 table 中获取。老 table 等待被 gc 掉即可。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range
// 创建 nextTable if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked")
// 大小乘以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 = nextTab; transferIndex = n; } int nextn = nextTab.length; ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node<K,V> f; int fh;
//advance是遍历的确认标志，是否再往前进行遍历。 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 = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { int sc;
// 完成拷贝后，再整个赋值，原 table 等待 gc 即可 if (finishing) {
// nextTable 只是在扩容中时短暂存在了一下 nextTable = null; table = nextTab;
// sizeCtl 为下次扩容的阈值：n*2*0.75(=n*2-n*0.5) sizeCtl = (n << 1) - (n >>> 1); return; }
// cas 修改 sizeCtl if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } }
// 头节点为 null ，不用搬，直接 cas 置为 ForwardingNode else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd);
// 已经加上 ForwardingNode（可能是被其它线程加的），就会进入下一个 while(advance) 循环，处理下一个 bin 链表 else if ((fh = f.hash) == MOVED) advance = true; // already processed else {
// 扩容时以每个 bin链表 为粒度加锁 synchronized (f) { if (tabAt(tab, i) == f) { Node<K,V> ln, hn;
// 普通链表 hash 大于0(treebin是-2) if (fh >= 0) { int runBit = fh & n; Node<K,V> lastRun = f; for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } 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); }
// 低位链表仍然放到 nextTab 的 i 处 setTabAt(nextTab, i, ln);
// 高位链表放到 nextTab 的 i+n 处 setTabAt(nextTab, i + n, hn);
// 这个链表完全放完 nextTab 了。头节点设为 fwd ，表示正在扩容中，get 时去 nextTab 找 setTabAt(tab, i, fwd); advance = true; }
// treebin hash 是 -2 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; } } } } } }
put 和 transfer 两个改数据的，都是sychronized bin 链表头节点，避免同时修改