concurrentHashMap 的实现

concurrentHashMap的实现：https://www.cnblogs.com/liaoweipeng/p/6343674.html

concurrentHashMap 的存在意义

目前学习到的散列表中 HashMap 是线程不安全的，HashTable 是线程安全的，但是 HashTable 的效率太低下了，所有访问 HashTable 的线程都要竞争同一个锁，当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方法时可能进入阻塞或轮询状态。如线程 A 利用 put 方法添加元素，线程 B 不但不能使用 put 方法添加元素，并且也不能使用 get 方法获取元素，所以竞争越激烈效率越低。为了弥补散列表在线程安全下的效率问题，故而有了 currentHashMap。

实现原理

concurrentHashMap 使用了被称为 segment（默认创建16个并发的segment）的分段锁技术，它既类似于 HashMap 的结构，即内部有一个 Entry 数组，数组中每个元素又是一个链表；同时又是一个 ReentranLock（segment 继承了 ReentranLock）。ConcurrentHashMap 中的 HashEntry 相对于 HashMap 中的 Entry 有一定的差异：

HashEntry 中的 value 以及 next 都被 volatile 修饰，这样可以在多线程读写中保持可见性。

使用分段锁后，所有的资源被分成了多个部分并分别锁定，这样多线程在进行不同 segment 的资源写时不用竞争同一把锁，提升了效率

一个 concurrentHashMap 主要包含三大结构：整个 Hash 表，segment（段），HashEntry（节点）。每个 segment 就相当于一个 hashTable 。每个 hashEntry 代表 hash 表中的一个节点，在其定义的结构中可以看到，除了 value 值和 next 值没有定义为 final，其余都定义为 final 型。concurrentHashMap 读不需要加锁

concurrentHashMap 的 get 方法

concurrentHashMap 在多线程上的高效不仅体现在他写的分段锁上，同时也体现在他的 get 操作上。

先来看一下他的 get 方法

public V get(Object key) {
    int hash = hash(key); // throws NullPointerException if key null
    return segmentFor(hash).get(key, hash);
}

它没有使用同步控制，先利用 segmentFor 方法找到 segment，然后直接交给 segment 去找，再看 segment 中的 get 方法

V get(Object key, int hash) {
        if (count != 0) { // read-volatile // ①
            HashEntry<K,V> e = getFirst(hash); 
            while (e != null) {
                if (e.hash == hash && key.equals(e.key)) {
                    V v = e.value;
                    if (v != null)  // ② 注意这里
                        return v;
                    return readValueUnderLock(e); // recheck
                }
                e = e.next;
            }
        }
        return null;
}

它也没有使用锁来同步，只是判断获取的 entry 的 value 是否为 null，为 null 时才使用加锁的方式再次去获取

没有锁同步的话，靠什么保证同步呢？我们来一步步分析：

第一步，先判断 count 是否等于 0，count 变量表示 segment 中 Entry 的数量，如果为 0 就不用找了

假设这个时候恰好另一个线程 put 或者 remove 了这个 segment 中的一个 entry，会不会导致两个线程看到的 count 值不一样呢？

看一下 count 变量的定义：transient volatile int count；

它使用了 volatile 来修改。Java5 之后，JMM 实现了对 volatile 的保证：对 volatile 域的写入操作 happen-before 于每一个后续对同一个域的读写操作

所以，每次判断 count 变量的时候，即使恰好其他线程改变了segment 也会体现出来

第二步，获取到该 key 所在 segment 中的索引地址，如果该地址有相同的 hash 对象，顺着链表一直比较下去找到该 entry，当找到该 entry 的时候，先做一次比较：if(v != null)

这个时候，另一个线程恰好新增/删除了 entry，或者改变了 entry 的 value，会如何？

先来看一下 HashEntry 的结构：

static final class HashEntry<K,V> {
    final K key;
    final int hash;
    volatile V value;
    final HashEntry<K,V> next;
    。。。
}

除了 value，其他成员都是 final 修饰的，也就是说 value 可以被改变，其他都不可以改变，包括指向下一个 HashEntry 的 next 也不能被改变，也就是说新增的 entry 只会出现在链表头

在 get 代码的①和②之间，另一个线程新增了一个 entry，如果另一个线程新增的这个 entry 又恰好是我们要 get 的，那么事情就比较微妙了

如果另一个线程刚好 new 这个对象时，当前线程来 get 它，因为没有同步，那么当前线程 get 到的可能是一个尚未完全构造好的对象引用

这里和 DCL 问题相同，没有锁同步的话，new 一个对象对于多线程看到这个对象的状态是没有保障的，这里同样有可能一个线程 new 这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象的引用

所以才需要判断一下：if (v != null)如果是一个不完整的对象，则使用锁的方式再 get 一次。这里也是 concurrentHashMap 为什么不接受 null 值的原因。如果加入 null 值则无法有效区分未完全加载的对象和本身为 null 的对象。

在 get 代码的 ① 和 ② 之间，另一个线程修改了 entry 的 value

value 是 volatile 修饰的，可以保证读取时获取到的是修改后的值

在 get 代码的 ① 之后，另一个线程删除了一个 entry

假设我们的链表元素是：e1-> e2 -> e3 -> e4 我们要删除 e3这个entry，因为HashEntry中next的不可变，所以我们无法直接把e2的next指向e4，而是将要删除的节点之前的节点复制一份，形成新的链表。

根据 hash 值定位 segment 时会调用 segmentfor 方法，返回相应的 segment 在数组中的下标。segment 的 get 操作实现非常简单高效