能具体说一下 ConcurrentHashmap 的实现吗？

能具体说一下 ConcurrentHashmap 的实现吗？#

ConcurrentHashmap 线程安全在 jdk1.7 版本是基于分段锁实现，在 jdk1.8 是基于CAS+synchronized实现。

jdk 1.7分段锁#

从结构上说，1.7 版本的 ConcurrentHashMap 采用分段锁机制，里面包含一个 Segment 数组，Segment 继承于 ReentrantLock，Segment 则包含 HashEntry 的数组，HashEntry 本身就是一个链表的结构，具有保存 key、value 的能力能指向下一个节点的指针。实际上就是相当于每个 Segment 都是一个 HashMap，默认的 Segment 长度是 16，也就是支持 16 个线程的并发写，Segment 之间相互不会受到影响。 put 流程 整个流程和 HashMap 非常类似，只不过是先定位到具体的 Segment，然后通过 ReentrantLock 去操作而已，后面的流程，就和 HashMap 基本上是一样的。

计算 hash，定位到 segment，segment 如果是空就先初始化
使用 ReentrantLock 加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
遍历 HashEntry，就是和 HashMap 一样，数组中 key 和 hash 一样就直接替换，不存在就再插入链表，链表同样操作

get 流程 get 也很简单，key 通过 hash 定位到 segment，再遍历链表定位到具体的元素上，需要注意的是 value 是 volatile 的，所以 get 是不需要加锁的。

jdk1.8 CAS+synchronized#

jdk1.8 实现线程安全不是在数据结构上下功夫，它的数据结构和 HashMap 是一样的，数组+链表+红黑树。它实现线程安全的关键点在于 put 流程。 put 流程

首先计算 hash，遍历 node 数组，如果 node 是空的话，就通过 CAS+自旋的方式初始化

1
tab = initTable();

node 数组初始化：

1
private final Node<K,V>[] initTable() {
2
    Node<K,V>[] tab; int sc;
3
    while ((tab = table) == null || tab.length == 0) {
4
        //如果正在初始化或者扩容
5
        if ((sc = sizeCtl) < 0)
6
            //等待
7
            Thread.yield(); // lost initialization race; just spin
8
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {   //CAS操作
9
            try {
10
                if ((tab = table) == null || tab.length == 0) {
11
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
12
                    @SuppressWarnings("unchecked")
13
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
14
                    table = tab = nt;
15
                    sc = n - (n >>> 2);
16
                }
17
            } finally {
18
                sizeCtl = sc;
19
            }
20
            break;
21
        }
22
    }
23
    return tab;
24
}

2.如果当前数组位置是空则直接通过 CAS 自旋写入数据

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

如果 hash==MOVED，说明需要扩容，执行扩容

1
else if ((fh = f.hash) == MOVED)
2
                tab = helpTransfer(tab, f);

1
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2
    Node<K,V>[] nextTab; int sc;
3
    if (tab != null && (f instanceof ForwardingNode) &&
4
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
5
        int rs = resizeStamp(tab.length);
6
        while (nextTab == nextTable && table == tab &&
7
               (sc = sizeCtl) < 0) {
8
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
9
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
10
                break;
11
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
12
                transfer(tab, nextTab);
13
                break;
14
            }
15
        }
16
        return nextTab;
17
    }
18
    return table;
19
}

如果都不满足，就使用 synchronized 写入数据，写入数据同样判断链表、红黑树，链表写入和 HashMap 的方式一样，key hash 一样就覆盖，反之就尾插法，链表长度超过 8 就转换成红黑树

1
synchronized (f){
2
     ……
3
 }

get 查询 get 很简单，和 HashMap 基本相同，通过 key 计算位置，table 该位置 key 相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。