更多 Java 集合类方面的文章，请参见文集《Java 集合类》
线程安全的 Map
在 JDK 1.5 之前，多线程的并发程序中可以使用：
- Hashtable
- Collections.synchronizedMap()
存在的问题：这两种方式都是对整个 hash 表结构做锁定操作的，这样在锁表的期间，别的线程（无论是读还是写）就需要等待了，性能不高。
ConcurrentHashMap
所在包：java.util.concurrent
基本特性：
- 线程安全
- 比 Hashtable 和 Collections.synchronizedMap() 性能要好
- 运行并发的读和线程安全的写。在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设置为 16），及任意数量线程的读操作。
- 不允许 key 为 null
ConcurrentHashMap （CHM）的实现原理
private static final int DEFAULT_CAPACITY = 16; // 同 HashMap 一致
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 默认并发级别
private static final float LOAD_FACTOR = 0.75f; // 同 HashMap 一致
Java 7中的 ConcurrentHashMap 的底层数据结构仍然是数组和链表。与 HashMap 不同的是，ConcurrentHashMap 最外层不是一个大的数组，而是一个 Segment 的数组。每个Segment包含一个与HashMap 数据结构差不多的链表数组。整体数据结构如下图所示：
CHM 引入了分割，整个结构默认被分割为 16 个部分，并且由不同的锁控制，因此同时最多可以有 16 个写线程操作 Map。每个 Segment 又包含若干个散列表的桶，每个桶是由 HashEntry 链接起来的一个链表。如果 key 能够均匀散列，每个 Segment 大约守护整个散列表桶总数的 1/16。
每一个 Segment 类似于于一个 HashMap 的结构，即 HashEntry 构成的数组 + 链表，如图：
Segment 的类定义为 static final class Segment<K,V> extends ReentrantLock implements Serializable。
其继承于 ReentrantLock 类，从而使得 Segment 对象可以充当锁的角色。
寻址方式
在读写某个 Key 时，先取该 Key 的哈希值。并将哈希值的高 N 位对 Segment 个数取模从而得到该 Key 应该属于哪个 Segment，接着如同操作 HashMap 一样操作这个Segment。
同步方式
Segment继承自 ReentrantLock，所以我们可以很方便的对每一个 Segment 上锁。
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
写操作
加锁操作是针对的 hash 值对应的某个 Segment，而不是整个 ConcurrentHashMap。因为 put 操作只是在这个 Segment 中完成，所以并不需要对整个 ConcurrentHashMap 加锁。
所以，此时，其他的线程也可以对另外的 Segment 进行 put 操作。同时，读线程并不会因为本线程的加锁而阻塞。
获取锁时，并不直接使用 lock 来获取，因为该方法获取锁失败时会挂起。事实上，它使用了 自旋锁，如果 tryLock 获取锁失败，说明锁被其它线程占用，此时通过循环再次以 tryLock 的方式申请锁。如果在循环过程中该 Key 所对应的链表头被修改，则重置 retry 次数。如果 retry 次数超过一定值，则使用 lock 方法申请锁。
这里使用自旋锁是因为自旋锁的效率比较高，但是它消耗CPU资源比较多，因此在自旋次数超过阈值时切换为互斥锁。
读操作
无需加锁，可以任意多个线程去读 ConcurrentHashMap。
如果保证数据对多个线程的可见性？
依靠 Java 内存模型，使用 Volatile 变量： transient volatile Node<K,V>[] table;
size 操作
put、remove 和 get 操作只需要关心一个 Segment，而 size 操作需要遍历所有的 Segment 才能算出整个 Map 的大小。一个简单的方案是，先锁住所有 Sgment，计算完后再解锁。但这样做，在做 size 操作时，不仅无法对Map进行写操作，同时也无法进行读操作，不利于对Map的并行操作。
为更好支持并发操作，ConcurrentHashMap 会在不上锁的前提逐个 Segment 计算 3 次 size，如果某相邻两次计算获取的所有 Segment 的更新次数（每个 Segment 都与 HashMap 一样通过 modCount 跟踪自己的修改次数，Segment 每修改一次其 modCount 加一）相等，说明这两次计算过程中无更新操作，则这两次计算出的总size相等，可直接作为最终结果返回。如果这三次计算过程中 Map 有更新，则对所有 Segment 加锁重新计算 Size。
遍历 ConcurrentHashMap （CHM）
迭代遍历 ConcurrentHashMap 时，iterator 是弱一致和 fail-safe的，可能不会反映最近的修改。并且在遍历过程中，如果 Map 的结构发生了变化，不会抛出 ConcurrentModificationException。
具体参见 Java 集合 Fail-Fast 机制 VS Fail-Safe 机制
何时使用 ConcurrentHashMap （CHM）
- 如果 读线程数目 大于 写线程数目，使用 ConcurrentHashMap
- 如果 读线程数目 小于 写线程数目，使用 Hashtable 或者 Collections.synchronizedMap() 。
关于并发级别
- 并发级别过高，导致时间和空间的浪费
- 并发级别过低，导致过度的竞争
Java 8基于 CAS 的 ConcurrentHashMap
Java 7为实现并行访问，引入了 Segment 这一结构，实现了分段锁，理论上最大并发度与 Segment 个数相等。
Java 8 为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(long(N))）。其数据结构如下图所示：
寻址方式
Java 8 的 ConcurrentHashMap 同样是通过 Key 的哈希值与数组长度取模确定该 Key 在数组中的索引。同样为了避免不太好的 Key 的 hashCode 设计，它通过如下方法计算得到Key的最终哈希值。不同的是，Java 8的 ConcurrentHashMap 作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，所以作者并未在哈希值的计算上做过多设计，只是将 Key 的 hashCode 值与其高 16 位作异或并保证最高位为0（从而保证最终结果为正整数）。
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
同步方式
对于 put 操作，如果 Key 对应的数组元素为 null，则通过CAS操作将其设置为当前值。如果 Key 对应的数组元素（也即链表表头或者树的根元素）不为 null，则对该元素使用 synchronized 关键字申请锁，然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。
对于读操作，由于数组被 volatile 关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个 Node 实例（Java 7中每个元素是一个HashEntry），它的 Key 值和 hash 值都由 final 修饰，不可变更，无须关心它们被修改后的可见性问题。而其 Value 及对下一个元素的引用由 volatile 修饰，可见性也有保障。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
size 操作
put 方法和 remove 方法都会通过 addCount 方法维护 Map 的 size。size方法通过 sumCount 获取由addCount 方法维护的 Map 的 size。
引用：
ConcurrentHashMap 的实现原理
Java进阶（六）从ConcurrentHashMap的演进看Java多线程核心技术
