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