出现背景

1 线程不安全的 HashMap

因为多线程环境下，使用 Hashmap 进行 put 操作会引起死循环（infinite loop），导致 CPU 利用率接近 100%（【Java】集合类 - HashMap 的并发问题），所以在并发情况下不能使用 HashMap。

2 效率低下的 HashTable 容器

HashTable 容器使用 synchronized 来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效率非常低下。

因为当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方法时，可能会进入阻塞或轮询状态。如线程 1 使用 put 进行添加元素，线程 2 不但不能使用 put 方法添加元素，并且也不能使用 get 方法来获取元素，所以竞争越激烈效率越低。

对于 Hashtable 而言，synchronized 是针对整张 Hash 表的，即每次锁住整张表让线程独占。相当于所有线程进行读写时都去竞争一把锁，导致效率非常低下。

3 ConcurrentHashMap 的锁分段技术

HashTable 容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问 HashTable 的线程都必须竞争同一把锁。

那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是 ConcurrentHashMap 所使用的锁分段技术。

即首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。另外，ConcurrentHashMap 可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，不用对整个 ConcurrentHashMap 加锁。

ConcurrentHashMap 的内部结构

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 继承了 ReentrantLock，所以它就是一种可重入锁（Reentrant Lock）。在 ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不用考虑锁竞争的。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁。

从上面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。

因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行加锁即可，不会影响到其他的 Segment，

这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment 上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。

JDK 1.8 中的实现改进

JDK 1.7 中 ConcurrentHashMap 最主要采用 segment，多线程竞争会先锁住 segment，在其 put 操作中会先定位 segment 位置，再定位 segment 中具体桶位置。

在 JDK 1.8 中，抛弃了 Segment 分段锁机制，利用 Node 数组 + CAS+Synchronized 来保证并发更新的安全，底层采用数组 + 链表 + 红黑树的存储结构。

Reference

站在巨人肩膀上看源码 - ConcurrentHashMap - https://segmentfault.com/a/1190000015221462
ConcurrentHashMap 实现原理及源码分析 - https://www.cnblogs.com/chengxiao/p/6842045.htmls
探索 ConcurrentHashMap 高并发性的实现机制 - https://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html

【Java】集合类 - Map - ConcurrentHashMap