一文彻底搞懂 ConcurrentHashMap 原理
出现背景
1、线程不安全的 HashMap
因为多线程环境下，使用 Hashmap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，所以在并发情况下不能使用 HashMap。
2、效率低下的 HashTable 容器
HashTable 容器使用 synchronized 来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效率非常低下。因为当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方法时，可能会进入阻塞或轮询状态。如线程 1 使用 put 进行添加元素，线程 2 不但不能使用 put 方法添加元素，并且也不能使用 get 方法来获取元素，所以竞争越激烈效率越低。也就是说对于 Hashtable 而言，synchronized 是针对整张 Hash 表的，即每次锁住整张表让线程独占。相当于所有线程进行读写时都去竞争一把锁，导致效率非常低下。
3、ConcurrentHashMap 的锁分段技术
HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问 HashTable 的线程都必须竞争同一把锁。那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是 ConcurrentHashMap 所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。 另外，ConcurrentHashMap 可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，不用对整个 ConcurrentHashMap 加锁。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 是一种可重入锁 ReentrantLock，在 ConcurrentHashMap 里扮演锁的角色，HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的结构和 HashMap 类似，是一种数组和链表结构， 一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素， 每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁。
ConcurrentHashMap 的内部结构
ConcurrentHashMap 为了提高本身的并发能力，在内部采用了一个叫做 Segment 的结构，一个 Segment 其实就是一个类 Hash Table 的结构，Segment 内部维护了一个链表数组，我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构：
从上面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行加锁即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment 上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。
1、Segment
我们再来具体了解一下 Segment 的数据结构：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile int count;
transient int modCount;
transient int threshold;
transient volatile HashEntry<K,V>[] table;
final float loadFactor;
}
详细解释一下 Segment 里面的成员变量的意义：
`count：Segment中元素的数量`
`modCount：对table的大小造成影响的操作的数量（比如put或者remove操作）`
`threshold：阈值，Segment里面元素的数量超过这个值依旧就会对Segment进行扩容`
`table：链表数组，数组中的每一个元素代表了一个链表的头部`
`loadFactor：负载因子，用于确定threshold`
count 用来统计该段数据的个数，它是 volatile 变量，它用来协调修改和读取操作，以保证读取操作能够读取到几乎最新的修改。协调方式是这样的，每次修改操作做了结构上的改变，如增加 / 删除节点 (修改节点的值不算结构上的改变)，都要写 count 值，每次读取操作开始都要读取 count 的值。这利用了 Java 5 中对 volatile 语义的增强，对同一个 volatile 变量的写和读存在 happens-before 关系。modCount 统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变，在讲述跨段操作时会还会详述。threashold 用来表示需要进行 rehash 的界限值。table 数组存储段中节点，每个数组元素是个 hash 链，用 HashEntry 表示。table 也是 volatile，这使得能够读取到最新的 table 值而不需要同步。loadFactor 表示负载因子。
2、HashEntry
Segment 中的元素是以 HashEntry 的形式存放在链表数组中的，看一下 HashEntry 的结构：
1. `static final class HashEntry<K,V> {`
2. `final K key;`
3. `final int hash;`
4. `volatile V value;`
5. `final HashEntry<K,V> next;`
6. `}`
可以看到 HashEntry 的一个特点，除了 value 以外，其他的几个变量都是 final 的，这意味着不能从 hash 链的中间或尾部添加或删除节点，因为这需要修改 next 引用值，所有的节点的修改只能从头部开始。对于 put 操作，可以一律添加到 Hash 链的头部。但是对于 remove 操作，可能需要从中间删除一个节点，这就需要将要删除节点的前面所有节点整个复制一遍，最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值，将 value 设置成 volatile，这避免了加锁。
ConcurrentHashMap 的初始化
下面我们来结合源代码来具体分析一下 ConcurrentHashMap 的实现，先看下初始化方法：
1. `public ConcurrentHashMap(int initialCapacity,`
2. `float loadFactor, int concurrencyLevel) {`
3. `if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)`
4. `throw new IllegalArgumentException();`
6. `if (concurrencyLevel > MAX_SEGMENTS)`
7. `concurrencyLevel = MAX_SEGMENTS;`
9. `// Find power-of-two sizes best matching arguments`
10. `int sshift = 0;`
11. `int ssize = 1;`
12. `while (ssize < concurrencyLevel) {`
13. `++sshift;`
14. `ssize <<= 1;`
15. `}`
16. `segmentShift = 32 - sshift;`
17. `segmentMask = ssize - 1;`
18. `this.segments = Segment.newArray(ssize);`
20. `if (initialCapacity > MAXIMUM_CAPACITY)`
21. `initialCapacity = MAXIMUM_CAPACITY;`
22. `int c = initialCapacity / ssize;`
23. `if (c * ssize < initialCapacity)`
24. `++c;`
25. `int cap = 1;`
26. `while (cap < c)`
27. `cap <<= 1;`
29. `for (int i = 0; i < this.segments.length; ++i)`
30. `this.segments[i] = new Segment<K,V>(cap, loadFactor);`
31. `}`
CurrentHashMap 的初始化一共有三个参数，一个 initialCapacity，表示初始的容量，一个 loadFactor，表示负载参数，最后一个是 concurrentLevel，代表 ConcurrentHashMap 内部的 Segment 的数量，ConcurrentLevel 一经指定，不可改变，后续如果 ConcurrentHashMap 的元素数量增加导致 ConrruentHashMap 需要扩容，ConcurrentHashMap 不会增加 Segment 的数量，而只会增加 Segment 中链表数组的容量大小，这样的好处是扩容过程不需要对整个 ConcurrentHashMap 做 rehash，而只需要对 Segment 里面的元素做一次 rehash 就可以了。
整个 ConcurrentHashMap 的初始化方法还是非常简单的，先是根据 concurrentLevel 来 new 出 Segment，这里 Segment 的数量是不大于 concurrentLevel 的最大的 2 的指数，就是说 Segment 的数量永远是 2 的指数个，这样的好处是方便采用移位操作来进行 hash，加快 hash 的过程。接下来就是根据 intialCapacity 确定 Segment 的容量的大小，每一个 Segment 的容量大小也是 2 的指数，同样使为了加快 hash 的过程。
这边需要特别注意一下两个变量，分别是 segmentShift 和 segmentMask，这两个变量在后面将会起到很大的作用，假设构造函数确定了 Segment 的数量是 2 的 n 次方，那么 segmentShift 就等于 32 减去 n，而 segmentMask 就等于 2 的 n 次方减一。
ConcurrentHashMap 的 get 操作
前面提到过 ConcurrentHashMap 的 get 操作是不用加锁的，我们这里看一下其实现：
1. `1 public V get(Object key) {`
2. `2 int hash = hash(key.hashCode());`
3. `3 return segmentFor(hash).get(key, hash);`
4. `4 }`
第二行，对 hash 值进行了二次 hash，之所以要进行再哈希，其目的是为了减少哈希冲突，使元素能够均匀的分布在不同的 Segment 上，从而提高容器的存取效率。
看第三行，segmentFor 这个函数用于确定操作应该在哪一个 segment 中进行，几乎对 ConcurrentHashMap 的所有操作都需要用到这个函数，我们看下这个函数的实现：
1. `final Segment<K,V> segmentFor(int hash) {`
2. `return segments[(hash >>> segmentShift) & segmentMask];`
3. `}`
这个函数用了位操作来确定 Segment，根据传入的 hash 值向右无符号右移 segmentShift 位，然后和 segmentMask 进行与操作，结合我们之前说的 segmentShift 和 segmentMask 的值，就可以得出以下结论：假设 Segment 的数量是 2 的 n 次方，根据元素的 hash 值的高 n 位就可以确定元素到底在哪一个 Segment 中。
在确定了需要在哪一个 segment 中进行操作以后，接下来的事情就是调用对应的 Segment 的 get 方法：
1. `1 V get(Object key, int hash) {`
2. `2 if (count != 0) { // read-volatile // ①`
3. `3 HashEntry<K,V> e = getFirst(hash);`
4. `4 while (e != null) {`
5. `5 if (e.hash == hash && key.equals(e.key)) {`
6. `6 V v = e.value;`
7. `7 if (v != null) // ② 注意这里`
9. `8 return v;`
10. `9 return readValueUnderLock(e); // recheck`
11. `10 }`
12. `11 e = e.next;`
13. `12 }`
14. `13 }`
15. `14 return null;`
16. `15 }`
先看第二行代码，这里对 count 进行了一次判断，其中 count 表示 Segment 中元素的数量。我们可以来看一下 count 的定义：
1. `transient volatile int count;`
可以看到 count 是 volatile 的，实际上这里面利用了 volatile 的语义：
对 volatile 字段的写入操作 happens-before 于每一个后续的同一个字段的读操作。因为实际上 put、remove 等操作也会更新 count 的值，所以当竞争发生的时候，volatile 的语义可以保证写操作在读操作之前，也就保证了写操作对后续的读操作都是可见的，这样后面 get 的后续操作就可以拿到完整的元素内容。
然后，在第三行，调用了 getFirst() 来取得链表的头部：
1. `1 HashEntry<K,V> getFirst(int hash) {`
2. `2 HashEntry<K,V>[] tab = table;`
3. `3 return tab[hash & (tab.length - 1)];`
4. `4 }`
同样，这里也是用位操作来确定链表的头部，hash 值和 HashTable 的长度减一做与操作，最后的结果就是 hash 值的低 n 位，其中 n 是 HashTable 的长度以 2 为底的结果。
在确定了链表的头部以后，就可以对整个链表进行遍历，看第 4 行，取出 key 对应的 value 的值，如果拿出的 value 的值是 null，则可能这个 key，value 对正在 put 的过程中，如果出现这种情况，那么就加锁来保证取出的 value 是完整的，如果不是 null，则直接返回 value。
get 方法没有使用锁来同步，只是判断获取的 entry 的 value 是否为 null，为 null 时才使用加锁的方式再次去获取。
这个实现很微妙，没有锁同步的话，靠什么保证同步呢？我们一步步分析。
第一步，先判断一下 count != 0；count 变量表示 segment 中存在 entry 的个数。如果为 0 就不用找了。假设这个时候恰好另一个线程 put 或者 remove 了这个 segment 中的一个 entry，会不会导致两个线程看到的 count 值不一致呢？看一下 count 变量的定义：
1. `transient volatile int count;`
它使用了 volatile 来修改。在 Java5 之后，JMM 实现了对 volatile 的保证：对 volatile 域的写入操作 happens-before 于每一个后续对同一个域的读写操作。所以，每次判断 count 变量的时候，即使恰好其他线程改变了 segment 也会体现出来。
第二步，获取到要该 key 所在 segment 中的索引地址，如果该地址有相同的 hash 对象，顺着链表一直比较下去找到该 entry。当找到 entry 的时候，先做了一次比较： if(v != null) 我们用红色注释的地方。这是为何呢？考虑一下，如果这个时候，另一个线程恰好新增 / 删除了 entry，或者改变了 entry 的 value，会如何？
前面说过 HashEntry 类的结构，除了 value，其它成员都是 final 修饰的，也就是说 value 可以被改变，其它都不可以改变，包括指向下一个 HashEntry 的 next 也不能被改变。
（1）在 get 代码的①和②之间，另一个线程新增了一个 entry。如果另一个线程新增的这个 entry 又恰好是我们要 get 的，这事儿就比较微妙了。下图大致描述了 put 一个新的 entry 的过程。
因为每个 HashEntry 中的 next 也是 final 的，没法对链表最后一个元素增加一个后续 entry 所以新增一个 entry 的实现方式只能通过头结点来插入了。
newEntry 对象是通过 new HashEntry(K k , V v, HashEntry next) 来创建的。如果另一个线程刚好 new 这个对象时，当前线程来 get 它。因为没有同步，就可能会出现当前线程得到的 newEntry 对象是一个没有完全构造好的对象引用。没有锁同步的话，new 一个对象对于多线程看到这个对象的状态是没有保障的，这里同样有可能一个线程 new 这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象引用。所以才需要判断一下：if (v != null) 如果确实是一个不完整的对象，则使用锁的方式再次 get 一次。
有没有可能会 put 进一个 value 为 null 的 entry？ 不会的，已经做了检查，这种情况会抛出异常，所以 ②处的判断完全是出于对多线程下访问一个 new 出来的对象的状态检测。
（2）在 get 代码的①和②之间，另一个线程修改了一个 entry 的 value。value 是用 volitale 修饰的，可以保证读取时获取到的是修改后的值。
（3）在 get 代码的①之后，另一个线程删除了一个 entry。
假设我们的链表元素是：e1-> e2 -> e3 -> e4 我们要删除 e3 这个 entry，因为 HashEntry 中 next 的不可变，所以我们无法直接把 e2 的 next 指向 e4，而是将要删除的节点之前的节点复制一份，形成新的链表。它的实现大致如下图所示：
如果我们 get 的也恰巧是 e3，可能我们顺着链表刚找到 e1，这时另一个线程就执行了删除 e3 的操作，而我们线程还会继续沿着旧的链表找到 e3 返回。这里没有办法实时保证了。
我们第①处就判断了 count 变量，它保障了在 ①处能看到其他线程修改后的。①之后到②之间，如果再次发生了其他线程再删除了 entry 节点，就没法保证看到最新的了。不过这也没什么关系，即使我们返回 e3 的时候，它被其他线程删除了，暴漏出去的 e3 也不会对我们新的链表造成影响。
这其实是一种乐观设计，设计者假设 ①之后到②之间 发生被其它线程增、删、改的操作可能性很小，所以不采用同步设计，而是采用了事后（其它线程这期间也来操作，并且可能发生非安全事件）弥补的方式。而因为其他线程的“改”和“删”对我们的数据都不会造成影响，所以只有对“新增”操作进行了安全检查，就是②处的非 null 检查，如果确认不安全事件发生，则采用加锁的方式再次 get。这样做减少了使用互斥锁对并发性能的影响。可能有人怀疑 remove 操作中复制链表的方式是否代价太大，这里我没有深入比较，不过既然 Java5 中这么实现，我想 new 一个对象的代价应该已经没有早期认为的那么严重。
ConcurrentHashMap 的 put 操作
看完了 get 操作，再看下 put 操作，put 操作的前面也是确定 Segment 的过程，这里不再赘述，直接看关键的 segment 的 put 方法：
1. `1 V put(K key, int hash, V value, boolean onlyIfAbsent) {`
2. `2 lock();`
3. `3 try {`
4. `4 int c = count;`
5. `5 if (c++ > threshold) // ensure capacity`
6. `6 rehash();`
7. `7 HashEntry<K,V>[] tab = table;`
8. `8 int index = hash & (tab.length - 1);`
9. `9 HashEntry<K,V> first = tab[index];`
10. `10 HashEntry<K,V> e = first;`
11. `11 while (e != null && (e.hash != hash || !key.equals(e.key)))`
12. `12 e = e.next;`
13. `13`
14. `14 V oldValue;`
15. `15 if (e != null) {`
16. `16 oldValue = e.value;`
17. `17 if (!onlyIfAbsent)`
18. `18 e.value = value;`
19. `19 }`
20. `20 else {`
21. `21 oldValue = null;`
22. `22 ++modCount;`
23. `23 tab[index] = new HashEntry<K,V>(key, hash, first, value);`
24. `24 count = c; // write-volatile`
25. `25 }`
26. `26 return oldValue;`
27. `27 } finally {`
28. `28 unlock();`
29. `29 }`
30. `30 }`
首先对 Segment 的 put 操作是加锁完成的，然后在第五行，如果 Segment 中元素的数量超过了阈值（由构造函数中的 loadFactor 算出）这需要进行对 Segment 扩容，并且要进行 rehash，关于 rehash 的过程大家可以自己去了解，这里不详细讲了。
第 8 和第 9 行的操作就是 getFirst 的过程，确定链表头部的位置。
第 11 行这里的这个 while 循环是在链表中寻找和要 put 的元素相同 key 的元素，如果找到，就直接更新更新 key 的 value，如果没有找到，则进入 21 行这里，生成一个新的 HashEntry 并且把它加到整个 Segment 的头部，然后再更新 count 的值。
该方法也是在持有段锁 (锁定整个 segment) 的情况下执行的，这当然是为了并发的安全，修改数据是不能并发进行的，必须得有个判断是否超限的语句以确保容量不足时能够 rehash。接着是找是否存在同样一个 key 的结点，如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到 hash 链的头部，这时一定要修改 modCount 和 count 的值，同样修改 count 的值一定要放在最后一步。put 方法调用了 rehash 方法，reash 方法实现得也很精巧，主要利用了 table 的大小为 2^n，这里就不介绍了。而比较难懂的是这句 int index = hash & (tab.length - 1)，原来 segment 里面才是真正的 hashtable，即每个 segment 是一个传统意义上的 hashtable，如上图，从两者的结构就可以看出区别，这里就是找出需要的 entry 在 table 的哪一个位置，之后得到的 entry 就是这个链的第一个节点，如果 e!=null，说明找到了，这是就要替换节点的值（onlyIfAbsent == false），否则，我们需要 new 一个 entry，它的后继是 first，而让 tab[index]指向它，什么意思呢？实际上就是将这个新 entry 插入到链头，剩下的就非常容易理解了。
ConcurrentHashMap 的 remove 操作
Remove 操作的前面一部分和前面的 get 和 put 操作一样，都是定位 Segment 的过程，然后再调用 Segment 的 remove 方法：
1. `1 V remove(Object key, int hash, Object value) {`
2. `2 lock();`
3. `3 try {`
4. `4 int c = count - 1;`
5. `5 HashEntry<K,V>[] tab = table;`
6. `6 int index = hash & (tab.length - 1);`
7. `7 HashEntry<K,V> first = tab[index];`
8. `8 HashEntry<K,V> e = first;`
9. `9 while (e != null && (e.hash != hash || !key.equals(e.key)))`
10. `10 e = e.next;`
11. `11`
12. `12 V oldValue = null;`
13. `13 if (e != null) {`
14. `14 V v = e.value;`
15. `15 if (value == null || value.equals(v)) {`
16. `16 oldValue = v;`
17. `17 // All entries following removed node can stay`
18. `18 // in list, but all preceding ones need to be`
19. `19 // cloned.`
20. `20 ++modCount;`
21. `21 HashEntry<K,V> newFirst = e.next;`
22. `22 for (HashEntry<K,V> p = first; p != e; p = p.next)`
23. `23 newFirst = new HashEntry<K,V>(p.key, p.hash,`
24. `24 newFirst, p.value);`
25. `25 tab[index] = newFirst;`
26. `26 count = c; // write-volatile`
27. `27 }`
28. `28 }`
29. `29 return oldValue;`
30. `30 } finally {`
31. `31 unlock();`
32. `32 }`
33. `33 }`
首先 remove 操作也是确定需要删除的元素的位置，不过这里删除元素的方法不是简单地把待删除元素的前面的一个元素的 next 指向后面一个就完事了，我们之前已经说过 HashEntry 中的 next 是 final 的，一经赋值以后就不可修改，在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去，看一下下面这一幅图来了解这个过程：
假设链表中原来的元素如上图所示，现在要删除元素 3，那么删除元素 3 以后的链表就如下图所示：
整个操作是在持有段锁的情况下执行的，空白行之前 (第 11 行之前) 的行主要是定位到要删除的节点 e。接下来，如果不存在这个节点就直接返回 null，否则就要将 e 前面的结点复制一遍，尾结点指向 e 的下一个结点。e 后面的结点不需要复制，它们可以重用。
中间那个 for 循环是做什么用的呢？（第 22 行）从代码来看，就是将定位之后的所有 entry 克隆并拼回前面去，但有必要吗？每次删除一个元素就要将那之前的元素克隆一遍？这点其实是由 entry 的不变性来决定的，仔细观察 entry 定义，发现除了 value，其他所有属性都是用 final 来修饰的，这意味着在第一次设置了 next 域之后便不能再改变它，取而代之的是将它之前的节点全都克隆一次。至于 entry 为什么要设置为不变性，这跟不变性的访问不需要同步从而节省时间有关。
整个 remove 实现并不复杂，但是需要注意如下几点。第一，当要删除的结点存在时，删除的最后一步操作要将 count 的值减一。这必须是最后一步操作，否则读取操作可能看不到之前对段所做的结构性修改。第二，remove 执行的开始就将 table 赋给一个局部变量 tab，这是因为 table 是 volatile 变量，读写 volatile 变量的开销很大。编译器也不能对 volatile 变量的读写做任何优化，直接多次访问非 volatile 实例变量没有多大影响，编译器会做相应优化。
总结
ConcurrentHashMap 背景：出现的原因是因为我们起先使用的是 HashMap 和 HashTable，但是随着并发量的增加，HashMap 并没有使用同步，在多线程情况下使用 HashMap 的时候就会出现并发问题，而 HashTable 虽然是安全的，但是使用的是 synchronized 锁整表操作，这样在性能上将会产生很大的影响。那么如何能设计出一款即安全，在效率上又高的集合呢，这样就有了 ConcurrentHashMap 的产生。
ConcurrentHashMap 采用的是锁分段技术，内部为 Segment 数组来进行细分，而每个 Segment 又通过 HashEntry 数组来进行组装，当进行写操作的时候，只需要对这个 key 对应的 Segment 进行加锁操作，加锁同时不会对其他的 Segment 造成影响。总的 Map 包含了 16 个 Segment（默认数量），每个 Segment 内部包含 16 个 HashEntry（默认数量），这样对于这个 key 所在的 Segment 加锁的同时，其他 15 个 Segmeng 还能正常使用，在性能上有了大大的提升。
同时 ConcurrentHashMap 只是针对 put 方法进行了加锁，而对于 get 方法并没有采用加锁的操作，因为具体的值，在 Segment 的 HashEntry 里面是 volatile 的，基于 happens-before（先行发生）原则，对数据的写先行发生于对数据的读，所以再读取的时候获取到的必然是最新的结果。
因为对数组的操作，在主内存和工作内存中，load 和 use、assgin 和 store 是必然连在一起的，一旦使用（use）发生，那 load 必先行发生于 use 之前，use 前必然从主内存中加载最新的值到工作内存的变量副本里。而一旦赋值（assgin），必然先行发生于 store 将值传递给主内存，在 write 到主内存中去。所以 put 方式无需加锁也能获取到最新的结果。
size 操作是先请求 2 次的 count 数量，如果有发生变化，则对 put、remove、clean 进行加锁，在统计完之后 unlock。
学到的内容
1.HashEntry 里面的 value 值是被 volatile 修饰的，然后 HashEntry 里面除了 value 值不是 final 修饰的，其他都被 final 修饰了，所以在 HashEntry 链表里面添加 HashEntry 的时候，只能添加到头节点，不能添加到尾节点，因为 HashEntry 里面的 next 值是被 final 修饰的，不能修改
2.ConcurrentHashMap 的 get 操作时候，如果发现新增，修改，删除都是怎么考虑并发问题的
2.1 新增的时候，如果刚好 new 一个对象，然后此时对象是一个没有完全构造好的对象引用。没有锁同步的话，此时 get 的时候就有可能获取到一个 null 的对象，解决办法就是如果 HashEntry 里面的 value 是 null 的时候，在加锁去获取一次
2.2 在修改的时候，因为 HashEntry 里面的 value 值是被 volatile 修饰的，所以修改对获取数据没有影响
2.3 在删除的时候，看下面的图片，因为 HashEntry 中 next 的不可变，所以我们无法直接把 e2 的 next 指向 e4，而是将要删除的节点之前的节点复制一份，形成新的链表。所以如果我们的线程此时 get 的也恰巧是 e3，可能就会顺着链表刚找到 e1，这时另一个线程就执行了删除 e3 的操作，而我们线程还会继续沿着旧的链表找到 e3 返回。这里没有办法实时保证数据的实时性了（这是我目前的理解）
3.ConcurrentHashMap 的内部结构
3.1ConcurrentHashMap 为了提高本身的并发能力，在内部采用了一个叫做 Segment 的结构，一个 Segment 其实就是一个类 Hash Table 的结构，Segment 内部维护了一个链表数组，我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构：
3.2ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，这样好处是多个线程可以同时读写操作多个 segment，这样就降低了锁的颗粒度