hashmap

请设计一个线程安全的 HashMap。

先回顾一下普通的哈希表(HashMap)是怎么写出来的，再讨论如何做到线程安全。HashMap 的核心在于如何解决哈希冲突，主流思路有两种，

开地址法(Open addressing). 即所有元素在一个一维数组里，遇到冲突则按照一定规则向后跳，假设元素 x 原本在位置hash(x)%m（m 表示数组长度），那么第 i 次冲突时位置变为Hi = [hash(x) + di] % m，其中di表示第 i 次冲突时人为加上去的偏移量。偏移量di一般有如下 3 种计算方法，
1. 线性探测法(Linear Probing)。非常简单，发现位子已经被占了，则向后移动 1 位，即$$d_i = i$$, i=1,2,3,…
  该算法最大的优点在于计算速度快，对 CPU 高速缓存友好；其缺点也非常明显，假设 3 个元素 x1，x2，x3 的哈希值都相同，记为 p, x1 先来，查看位置 p，是空，则 x1 被映射到位置 p，x2 后到达，查看位置 p，发生第一次冲突，向后探测一下，即 p+1，该位置为空，于是 x2 映射到 p+1, 同理，计算 x3 的位置需要探测位置 p, p+1, p+2，也就是说对于发生冲突的所有元素，在探测过程中会扎堆，导致效率低下，这种现象被称为 clustering。
2. 二次探测法(Quadratic Probing)。$$d_i=ai^2+bi+c$$, 其中 a,b,c 为系数，$$d_i$$是 i 的二次函数，所以称为二次探测法。该算法的性能介于线性探测和双哈希之间。
3. 双哈希法(Double Hashing)。偏移量 di 由另一个哈希函数计算而来，设为hash2(x)，则di=(hash2(x) % (m-1) + 1) * i
拉链法(Chaining)。开一个定长数组，每个格子指向一个桶(Bucket, 可以用单链表或双向链表表示)，对每个元素计算出哈希并取模，找到对应的桶，并插入该桶。发生冲突的元素会处于同一个桶中。

JDK7 和 JDK8 里java.util.HashMap采取了拉链法。

如何将基于拉链法的 HashMap 改造为线程安全的呢？有以下几个思路，

将所有 public 方法都加上 synchronized. 相当于设置了一把全局锁，所有操作都需要先获取锁，java.util.HashTable就是这么做的，性能很低
由于每个桶在逻辑上是相互独立的，将每个桶都加一把锁，如果两个线程各自访问不同的桶，就不需要争抢同一把锁了。这个方案的并发性比单个全局锁的性能要好，不过锁的个数太多，也有很大的开销。
锁分离(Lock Stripping)技术。第 2 个方法把锁的压力分散到了多个桶，理论上是可行的的，但是假设有 1 万个桶，就要新建 1 万个ReentrantLock实例，开销很大。可以将所有的桶均匀的划分为 16 个部分，每一部分成为一个段(Segment)，每个段上有一把锁，这样锁的数量就降低到了 16 个。JDK 7 里的java.util.concurrent.ConcurrentHashMap就是这个思路。
在 JDK8 里，ConcurrentHashMap 的实现又有了很大变化，它在锁分离的基础上，大量利用了了 CAS 指令。并且底层存储有一个小优化，当链表长度太长（默认超过 8）时，链表就转换为红黑树。链表太长时，增删查改的效率比较低，改为红黑树可以提高性能。JDK8 里的 ConcurrentHashMap 有 6000 多行代码，JDK7 才 1500 多行。

方案 1: JDK7 版本，锁分离

TODO

方案 2: JDK8 版本，锁分离+CAS+红黑树

TODO

参考资料

最近更新于 0001-01-01