目录

一、前言

二、Hashtable 为什么被淘汰

三、JDK7中ConcurrentHashMap实现

Segment 是什么

分段锁思想

JDK7 CurrentHashMap的问题

四、JDK8中ConcurrentHashMap实现

五、put()执行流程

桶为空

桶不为空

六、链表转红黑树

八、扩容机制

九、怎么计数

一、前言

集合框架是Java开发中很常用的框架,单线程下没什么问题,但是多线程下有很大的并发问题

先看最普通的 HashMap:

Map<String, Integer> map = new HashMap<>();

map.put("A", 1);

单线程完全没问题,但多线程同时执行:

map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

可能出现:

  • 数据覆盖
  • 数据丢失
  • 扩容死循环(JDK7)

因为 HashMap 本身没有任何同步机制,多线程下会有很大的并发安全问题

二、Hashtable 为什么被淘汰

最早 JDK 提供过 Hashtable:

Hashtable<String, Integer> table = new Hashtable<>();

源码:

public synchronized V put(K key, V value)

我们可以看到直接给整个方法加 synchronized

public synchronized void put() {
    ...
}

这样虽然线程安全:

线程A put
线程B put
线程C get

但是全部排队,并发性能极差

三、JDK7中ConcurrentHashMap实现

JDK7采用:

Segment + HashEntry

结构:

ConcurrentHashMap

└── Segment[] segments 【第一层大数组,分段锁数组】

                   

                    └── Segment[i] 分段(自带一把ReentrantLock锁)

                                   

                                       └── HashEntry[] table 【第二层小数组,当前分段自己的哈希桶】                                                         

                                                   └── HashEntry 单向链表节点

示意图:

ConcurrentHashMap

├── Segment0(锁)
│      ├── Entry
│      └── Entry

├── Segment1(锁)
│      ├── Entry
│      └── Entry

├── Segment2(锁)

└── Segment3(锁)

Segment 是什么

源码:

static final class Segment<K,V> extends ReentrantLock {
    transient volatile HashEntry<K,V>[] table; // 桶数组,独立于其他 Segment
    transient int count;                        // 元素数量
    transient int modCount;                     // 结构修改次数(用于 size() 一致性检测)
    transient int threshold;                    // 扩容阈值(= 容量 * loadFactor)
    final float loadFactor;
}

可以看到Segment就是集成自ReentrantLock

Segment 本身就是 ReentrantLock

即:一个Segment   =   一把锁

分段锁思想

假设:16个Segment

那么:

线程A 操作 Segment0
线程B 操作 Segment5
线程C 操作 Segment10

互不影响,同时执行

这就是:Lock Striping(锁分离),可以大大提高并发能力

JDK7 CurrentHashMap的问题

1、锁粒度仍然偏大

JDK7 的结构如下:

ConcurrentHashMap
│
├── Segment0(锁)
│    └── HashEntry[]
│
├── Segment1(锁)
│    └── HashEntry[]
│
└── Segment2(锁)
     └── HashEntry[]

每个 Segment 本质上就是一把独立的锁

假设两个线程分别执行:

map.put("A", 1);
map.put("B", 2);

经过 Hash 计算后:

A -> Segment0 -> table[1]

B -> Segment0 -> table[100]

虽然它们落在不同桶中:table[1] 、table[100]

但由于同属于 Segment0,因此仍然需要竞争同一把锁:segment.lock();

例如:

线程A 修改 table[1]

线程B 修改 table[100]

实际上:

线程B 必须等待线程A释放锁

理论上可以并发执行的操作,却被串行化了

2、并发度受 Segment 数量限制

JDK7 默认配置:

concurrencyLevel = 16

意味着默认情况下只有:

16 个 Segment
16 把锁

因此默认下理论最大并发度约为:16

假设服务器拥有:

64 核 CPU
100 个并发线程

但 ConcurrentHashMap 只有:

16 个 Segment

那么大量线程仍然会竞争同一个 Segment 锁

结果就是:

CPU 很多
线程很多
但锁不够用

无法充分发挥多核机器的性能

3、内存占用较高

JDK7 中的 Segment 定义如下:

static final class Segment<K,V>
        extends ReentrantLock

可以看到:

Segment 本身就是 ReentrantLock

假设默认:

16 个 Segment

那么系统中至少会存在:

16 个 ReentrantLock 对象

同时每个 Segment 内部还维护:

HashEntry[]
HashEntry 链表

整体结构层级较深:

ConcurrentHashMap
    ↓
Segment[]
    ↓
HashEntry[]
    ↓
HashEntry

带来了额外的对象开销和内存消耗

4、扩容实现复杂

这是 JDK7 ConcurrentHashMap 最大的设计缺陷之一

由于每个 Segment 都维护自己独立的桶数组:因此扩容也是独立进行的

Segment0
    └── table

Segment1
    └── table

Segment2
    └── table

例如:

Segment0 已满

那么:

Segment0 扩容

Segment1 不扩容

Segment2 不扩容

这就导致:

不同 Segment 的容量不同
不同 Segment 的扩容时机不同

整个扩容逻辑变得十分复杂

四、JDK8中ConcurrentHashMap实现

JDK7中结构

ConcurrentHashMap
    ↓
Segment[]
    ↓
HashEntry[]
    ↓
HashEntry

JDK8中结构

ConcurrentHashMap
    ↓
Node[]
    ↓
Node

删除掉了:Segment、ReentrantLock

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

核心结构:

Node[]

和 HashMap 很像

table
 │
 ├── Node
 ├── Node
 ├── Node
 └── Node

节点:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

例如:

map.put("Java",1);
map.put("Spring",2);

可能形成:

table

├── [0]
├── [1]
├── [2] → Node(Java)
│                    │
│                   ▼
│            Node(Spring)

└── [3]

五、put()执行流程

源码流程大致:

put(key,value)
       │
      ▼
计算 hash
       │
      ▼
定位桶位置
       │
      ▼
table 是否初始化?
       │
       ├── 否 → initTable()
       │
      ▼
当前桶是否为空?
      │
      ├── 是
      │      │
      │     ▼
      │   CAS插入
      │
      ▼
桶不为空
      │
      ├── ForwardingNode
      │          │
      │         ▼
      │      协助扩容
      │
      └── 普通Node
                             │
                            ▼
                    synchronized
                             │
        ┌───────┴────────┐
        ▼                                       ▼
      链表                                 红黑树
         │                                        │
        ▼                                       ▼
     插入/覆盖                         插入/覆盖
                 │
                ▼
          判断是否树化
                 │
                ▼
             addCount

具体源码:

​
final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh; K fk; V fv;
            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)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent // check first node without acquiring lock
                     && fh == hash
                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                     && (fv = f.val) != null)
                return fv;
            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);
                                    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;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

​

例如:

map.put("Java", 1);

1、桶为空

table
│
├── null
├── null
├── null
└── null

对应源码这段:

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
        break;
}

已经走完前面两个判断:

  1. table 已经初始化完成(tab != null,长度 n>0)

  2. 当前桶不是扩容标记(没走到 helpTransfer 分支)

步骤 1:计算桶下标 i

f = tabAt(tab, i = (n - 1) & hash)
  1. i = (n - 1) & hash:算出当前 key 落在数组第几个桶

  2. tabAt(tab, i):底层 Unsafe.getObjectVolatile,volatile 读,保证读到其他线程最新修改的数组引用,解决可见性问题

  3. 赋值 f = 桶头节点,判断 f == null → 这个桶是空的,无任何元素

步骤 2:CAS 无锁插入新节点

casTabAt(tab, i, null, new Node<K,V>(hash, key, value))
  • casTabAt:Unsafe 提供的 CAS 操作,原子操作

  • 参数含义:在数组 tab 的下标 i 位置,预期值是 null,就把新 Node 写进去

  • 全程没有 synchronized、没有锁,纯无锁并发操作,性能极高

两种结果

情况 A:CAS 执行成功

  1. 新 Node 成功写入 tab[i]

  2. 执行 break,直接跳出最外层自旋 for(;;)

  3. 走到 addCount(1L, binCount):元素总数 +1,检查是否达到扩容阈值

  4. 方法 return null(新增元素,无旧值)

情况 B:CAS 执行失败

CAS 失败只有一种原因:并发竞争 在你读取 tab[i]==null 之后、执行 CAS 之前,其他线程抢先在这个桶插入了 Node,导致当前位置不再是 null。

2、此时不会进入任何加锁逻辑,直接回到外层 for(;;) 自旋头部,重新走一遍全流程:

  1. 重新获取最新 table

  2. 重新计算下标 i

  3. 此时桶不再为空,会进入后面加 synchronized 锁链表 / 红黑树的分支处理冲突

2、桶不为空

前置条件:tab[i] != null,桶里已经有节点,分三大分支依次判断:

  1. 桶头是扩容标记 ForwardingNode(hash = -1) → 协助扩容

  2. putIfAbsent 且桶头 key 匹配 → 直接返回旧值(无锁快速返回)

  3. 普通冲突:锁住桶头节点,遍历链表 / 红黑树新增 / 覆盖元素

分支 1:当前桶正在扩容 fh == MOVED(-1)

else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);
  1. fForwardingNode,代表整张表正在 resize 迁移数据

  2. 调用 helpTransfer,当前线程放下插入操作,帮忙迁移其他桶的数据

  3. 迁移完成后更新局部变量 tab,回到最外层 for(;;) 自旋重新执行 put 逻辑

  4. 目的:多线程协同扩容,加快 resize 速度,避免单线程扩容阻塞

分支 2:常规哈希冲突(核心:synchronized 锁桶头)

前面条件都不满足,进入 else 块,正式处理链表 / 红黑树:

V oldVal = null;
synchronized (f) { // 锁当前桶头对象 f = tab[i]
    // 双重校验
    if (tabAt(tab, i) == f) {
2.1 双重校验 tabAt(tab, i) == f

加锁前存在并发间隙:读取桶头到上锁这段时间,其他线程可能:

  • 删除桶头节点

  • 扩容替换桶头为 ForwardingNode 如果现在 tab[i] != f,说明桶已经变了,放弃本次操作,跳出同步块回到自旋重试

2.2 子分支 A:普通单向链表 fh >= 0

普通 Node 的 hash 都是正数,代表当前桶是链表结构:

binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
    // 1. 找到相同key:覆盖value,记录oldVal
    if (e.hash == hash && ((ek = e.key) == key || key.equals(ek))) {
        oldVal = e.val;
        if (!onlyIfAbsent) e.val = value;
        break;
    }
    // 2. 走到链表末尾,尾插新节点
    Node<K,V> pred = e;
    if ((e = e.next) == null) {
        pred.next = new Node<>(hash, key, value);
        break;
    }
}

要点:

  1. binCount 统计链表节点总数,用于后续判断是否树化

  2. 遍历链表匹配 key:存在则覆盖;不存在则尾插新节点(无死循环问题)

  3. 同步块内串行执行,同一桶的其他线程阻塞在synchronized(f)

2.3 子分支 B:红黑树 f instanceof TreeBin

链表长度≥8 且数组容量≥64,桶头会变成 TreeBin 包装红黑树:

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;
    }
}
  1. 调用 putTreeVal 在红黑树中查找 / 插入节点

  2. 找到 key 则覆盖,没找到就在树上新增节点

  3. TreeBin 内部自带读写锁,配合外层 synchronized 保证树结构并发安全

同步块执行完毕后的后置逻辑

锁释放,执行树化判断:

if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if (oldVal != null)
        return oldVal;
    break;
}
  1. binCount >= 8:调用treeifyBin,内部先判断数组长度是否小于 64,不足则只扩容不树化

  2. oldVal != null = 更新旧 key,直接返回旧值,方法结束

  3. 新增节点则 break 跳出外层自旋循环

最后统一计数

addCount(1L, binCount);
return null;
  1. 全局元素数量 + 1

  2. 检查元素总数是否超过扩容阈值,达到阈值触发多线程 resize

  3. 新增元素返回 null

六、链表转红黑树

ConcurrentHashMap 某个桶中的链表长度持续增长时,查询性能会从 O(n) 逐渐退化

为避免极端情况下的性能劣化(例如哈希冲突严重),JDK8 引入了“链表转红黑树”的优化机制

1. 触发条件

树化并不是只由链表长度决定,还需要同时满足两个条件:

1. 链表长度 ≥ TREEIFY_THRESHOLD(默认 8)
2. 数组容量 ≥ MIN_TREEIFY_CAPACITY(默认 64)

 为什么有第二个条件?

因为在数组较小的情况下:

冲突的根本原因通常是“桶太少”,而不是链表结构问题

因此优先策略是:优先扩容,而不是树化

2. 树化入口:treeifyBin()

源码如下:

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n;

    if (tab != null) {

        // 条件1:数组过小 → 先扩容
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);

        // 条件2:满足树化条件 → 执行转换
        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<>(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<>(hd));
                }
            }
        }
    }
}

3. 核心流程拆解

树化过程可以分为 4 步:

第一步:判断是否需要扩容优先

if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
    tryPresize(n << 1);

如果数组太小(<64)
→ 不树化
→ 直接扩容

设计原因

小数组下:冲突 = 桶数量不足

扩容可以:降低冲突概率(更有效)

第二步:锁住当前桶

synchronized (b)

其中:

b = table[index]

桶头节点作为锁对象

作用:

保证树化过程中:

  • 不允许其他线程修改链表
  • 防止结构不一致

第三步:链表 → TreeNode 双向链表

TreeNode<K,V> hd = null, tl = null;

遍历链表:

for (Node<K,V> e = b; e != null; e = e.next)

转换逻辑:

TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null);

关键点:

这里不是直接生成红黑树,而是:

先构建 “TreeNode 双向链表”

结构变为:

Node链表
   ↓
TreeNode双向链表

双向链表连接:

if ((p.prev = tl) == null)
    hd = p;
else
    tl.next = p;

tl = p;

最终得到:

hd → TreeNode → TreeNode → TreeNode → tl

第四步:包装为红黑树 TreeBin

setTabAt(tab, index, new TreeBin<>(hd));

关键点:TreeBin 不是节点

TreeBin 是:

红黑树的“容器”

内部包含:

  • root(红黑树根节点)
  • lock(并发控制)
  • first(链表入口)

4. 转换前后对比

转换前(链表结构):查找复杂度:O(n)

table[i]
   ↓
Node → Node → Node → Node → Node → Node → Node → Node

转换后(红黑树结构):查找复杂度:O(log n)

        root
       /    \
      4      12
     / \    /  \
    2   6  10   14

5. 为什么能提升性能?

对比:

结构 查找复杂度
链表 O(n)
红黑树 O(log n)

当冲突严重时:

例如:hash冲突 → 8个元素都在同一个桶

链表:最多查 8 次

红黑树:最多查 3 次

七、计数原理

JDK8源码:(这里把扩容源码截断放在下面讲)

private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
       
    }

addCount = 计数 + 判断是否需要扩容

1. 更新元素总数(高并发计数)
2. 检查是否触发扩容

1、方法结构

addCount(x, check)
    │
    ├── ① 更新计数(baseCount / CounterCell)
    │
    └── ② 判断是否扩容(sizeCtl)

2、第一部分:并发计数

put()、remove()、get() 可能同时发生

例如:

线程A size()
线程B put()

此时数量一直变化

ConcurrentHashMap采用:

baseCount
CounterCell[]

统计元素个数

思想类似:LongAdder

多个线程分散计数,最后汇总,避免竞争

为什么不能用 size++

因为并发冲突:

线程A:+1
线程B:+1
线程C:+1
→ CAS冲突严重

3、计数流程拆解

Step 1:尝试直接 CAS baseCount

U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)

含义:直接在 baseCount 上 +x

成功:→ 直接结束

适用于:低并发

失败 → 进入分段计数

counterCells

Step 2:定位线程槽位

a = as[ThreadLocalRandom.getProbe() & m]

含义:每个线程绑定一个随机槽位

结构:

CounterCell[]
  [0] 线程A
  [1] 线程B
  [2] 线程C

Step 3:CAS更新槽位

CAS(a.value → a.value + x)

成功:更新完成

失败:进入兜底:fullAddCount(x)方法

4、计数总结

baseCount + CounterCell = 分段计数

避免热点 CAS

八、扩容机制原理

JDK8源码

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);
                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();
            }
        }

入口条件

if (check >= 0)

说明:只有 put/remove 才会触发

核心条件

s >= sizeCtl

含义:当前元素数量 >= 扩容阈值

1、sizeCtl 是什么

sizeCtl = 扩容控制器

三种状态:

-1  → 初始化中
>0  → 扩容阈值
<0  → 正在扩容(带线程数)

2、扩容流程

计算 resizeStamp

int rs = resizeStamp(n);

含义:标记当前扩容版本

情况1:已有线程在扩容

if (sc < 0)

说明:已经有人在扩容

当前线程 协同扩容

transfer(tab, nt)

作用:多线程一起扩容

情况2:第一次触发扩容

CAS(sizeCtl, rs << ... + 2)

含义:开始扩容

然后:

transfer(tab, null)

2.2、transfer 是真正扩容逻辑

流程图:

源码:

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
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                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;
            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;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                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
                }
            }
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        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);
                            }
                            setTabAt(nextTab, i, ln);
                            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;
                            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;
                        }
                    }
                }
            }
        }
    }

更多推荐