本文分析了HashMap的实现原理，resize可能会导致死循环、Fast-fail等线程不安全行为。 同时结合源码，从数据结构、寻址方式、同步方式、计算规模等角度分析了JDK 1.7和JDK 1.8中ConcurrentHashMap的实现原理。
线程不安全的 HashMap
众所周知，HashMap不是线程安全的。 HashMap的线程不安全性主要表现在调整大小时的死循环和使用迭代器时的fast-fail。
注：本章代码基于JDK 1.7.0_67
HashMap工作原理 HashMap数据结构
常用的底层数据结构主要包括字段和数组。 数组的存储区间连续，占用显存较多，易于寻址，插入和删除较困难。 链表的存储区间离散，占用显存少，寻址困难，易于插入和删除。
HashMap想要达到的是哈希表的疗效，并尽量实现O(1)级别的增删改查。 其具体实现同时使用了字段和数组。 可以认为最内层是一个字段，数组的每个元素是一个数组的头。
HashMap 轮询形式
对于新插入的数据或者要读取的数据，HashMap将Key的哈希值对链表的宽度取模，结果作为Entry在链表中的索引。 在计算机中，取模的成本远低于位运算的成本，因此HashMap要求链表的厚度必须是2的N次方。 此时Key的哈希值与2^N-1进行与运算，疗效相当于取模。 HashMap在指定HashMap的容量时并不要求用户传入2的N次方整数，而是会使用Integer.highestOneBit来计算小于指定整数的最大2^N值。 实现方法如下。
public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16); return i - (i >>> 1);
}
登录复制
由于Key的哈希值的分布直接决定了哈希表上所有数据的分布或者哈希冲突的可能性，为了避免Key的hashCode实现不佳（例如高位相同，只有低位不同） ）与2^N-1相同，结果相同），JDK 1.7的HashMap通过以下方式促进最终哈希值的二进制模式中的1尽可能均匀分布，以减少哈希冲突：尽可能多。
int h = hashSeed; h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
登录复制
resize无限循环传输方法
当HashMap的大小超过Capacity*loadFactor时，需要对HashMap进行扩容。 具体方法是新建一个长度为原来Capacity两倍的字段，保证新的Capacity仍然是2的N次方，从而保证上面的轮询方式仍然适用。 同时，还需要通过以下传输方法将所有原始数据重新插入（rehash）到新字段中。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry next = e.next; if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
} int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
登录复制
该方法不能保证线程安全，多个线程并发调用时可能会出现死循环。 其执行过程如下。 从步骤2可以看出，传输时数组的顺序是颠倒的。
遍历原链表中的元素
遍历数组上的每个节点：使用next获取下一个要转移的元素，将e转移到新字段的肚皮上，使用头插入插入节点
循环2直到所有数组节点都传输完毕
循环1，直到所有元素都传输完毕
单线程重新哈希
单线程情况下php取模，rehash没有问题。下图演示了单线程情况下的rehash过程
多线程并发下的Rehash
这里假设两个线程同时执行了put操作并引发了rehash，执行了传输模式，并假设线程一进入传输模式就执行next=e。 ”，此时线程2已经完成了传输模式的执行。此时的状态如下。
然后线程1被唤醒，继续执行第一轮循环的剩余部分
e.next = newTable[1] = nullnewTable[1] = e = key(5) e = next = key(9)
登录复制
结果如下图所示
然后执行下一个循环，得到的状态图如下
继续下一个循环，得到的状态图如下
此时循环数组就生成了，key(11)无法添加到线程1的新链表中，下次访问该数组时会出现死循环。
快速失败的原因
如果在迭代器的使用过程中HashMap发生了改变，就会抛出ConcurrentModificationExceptionphp取模，这就是Fast-fail策略。
当调用HashMap的iterator()方法时，它会构造并返回一个新的EntryIterator对象，并将EntryIterator的expectedModCount设置为HashMap的modCount（该变量记录HashMap被改变的次数）。
HashIterator() {
expectedModCount = modCount; if (size > 0) { // advance to first entry
Entry[] t = table; while (index < t.length && (next = t[index++]) == null)
;
}
}
登录复制
当通过Iterator的next方法访问下一个Entry时，会首先检查其expectedModCount是否等于HashMap的modCount。 如果没有，则说明HashMap发生了改变，直接抛出ConcurrentModificationException。 Iterator的remove方法也会进行类似的检测。 抛出这个异常是为了提醒用户尽早认识到线程安全问题。
线程安全解决方案
在单线程情况下，为了防止ConcurrentModificationException，需要保证数据只能通过HashMap本身或者只能通过Iterator改变，并且在使用Iterator之前数据不能被HashMap本身改变。 因为当通过Iterator删除数据时，HashMap的modCount和Iterator的expectedModCount会自动增加，不影响两者的相等性。 如果是要减少数据的话，只能通过HashMap本身来完成。 这时候如果想继续遍历数据，就需要再次调用iterator()方法重构一个新的Iterator，让新的Iterator的expectedModCount与更新后的HashMap的modCount相等。
多线程情况下，可以使用Collections.synchronizedMap方法构造同步Map，也可以直接使用线程安全的ConcurrentHashMap。
Java 7 基于段锁的ConcurrentHashMap
注：本章代码基于JDK 1.7.0_67
数据结构
Java 7中ConcurrentHashMap的底层数据结构一直是链表和数组。 与HashMap不同的是，ConcurrentHashMap的最内层并不是一个大的链表，而是一个Segment的链表。 每个Segment都包含一个类似于HashMap数据结构的数组链表。 整体数据结构如下图所示。
寻址方式
读写Key时，首先获取Key的哈希值。 并将哈希值的高N位对Segment个数取模，得到Key应该所属的Segment，然后像操作HashMap一样操作Segment。 为了保证不同的值均匀分布到不同的段，需要通过以下方式估计哈希值。
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h += (h <>> 10);
h += (h <>> 6);
h += (h << 2) + (h <>> 16);
}
登录复制
同样为了提高取模计算的效率，ssize是小于concurrencyLevel的最小2的N次方，segmentMask通过下面的估算是2^N-1。 这和上面估计链表宽度的方法是一致的。 对于某个Key的哈希值，只需要将segmentShift位右移即可得到高sshift位，然后与segmentMask进行AND运算即可得到其在Segment链表上的索引。
int sshift = 0;int ssize = 1;while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}this.segmentShift = 32 - sshift;this.segmentMask = ssize - 1;
Segment[] ss = (Segment[])new Segment[ssize];
登录复制
同步方式
Segment继承自ReentrantLock，因此我们可以轻松地锁定每个Segment。
对于读操作，在获取Key所在的Segment时，需要保证可见性（请参考多线程情况下如何保证可见性）。 具体实现中，可以使用volatile关键字，也可以使用锁。 但使用锁的成本太高，而且使用 volatile 时，每次写操作都会使所有 CPU 缓存失效，这也有一定的成本。 ConcurrentHashMap使用以下方法来保证可见性并获取最新的Segment。
Segment s = (Segment)UNSAFE.getObjectVolatile(segments, u)
登录复制
也用类似的方法获取Segment中的HashEntry
HashEntry e = (HashEntry) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)
登录复制
对于写操作，不需要同时获取所有Segment锁，因为那相当于锁定了整个Map。 它首先会获取Key-Value对所在Segment的锁。 成功获取锁后，可以像普通HashMap一样操作Segment，保证了Segment的安全性。
同时，由于尚未获取其他段的锁，因此理论上可以支持concurrencyLevel（等于段数）线程安全的并发读写。
获取锁时，不要直接使用lock来获取，因为这样获取锁失败时会挂起（参考可重入锁）。 事实上，它使用了自旋锁。 如果tryLock获取锁失败，则说明该锁被其他线程占用。 这时通过循环以tryLock的形式再次申请锁。 如果循环过程中Key对应的数组头发生改变，则重置重试次数。 如果重试次数超过一定值，则使用lock方法申请锁。
这里使用自旋锁是因为自旋锁效率更高，但消耗CPU资源较多，所以当载波数量超过阈值时切换到互斥锁。
大小运算
put、remove、get操作只需要关心一个Segment，而size操作需要遍历所有Segment来计算整个Map的大小。 一个简单的解决方案是先锁定所有Sgment，计算完毕后再解锁。 但这样做的话，在进行size操作时，不仅无法写入Map，而且也很难进行读操作，不利于Map的并行操作。
为了更好的支持并发操作，ConcurrentHashMap会在不加锁的情况下估计每个Segment的大小3次。 如果所有Segment的一定更新次数被估计两次（每个Segment像HashMap一样通过modCount跟踪自己的变化次数，modCount加1）等于每次Segment发生变化，说明该段期间没有更新操作两次估计，两次估计的总大小相等，可以直接作为最终结果返回。 如果在这3次估计过程中更新了Map，则所有Segment都会被锁定，并且重新估计Size。估计方法的代码如下
public int size() {
final Segment[] segments = this.segments; int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {for (;;) { if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false; for (int j = 0; j < segments.length; ++j) {
Segment seg = segmentAt(segments, j);if (seg != null) {
sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)segmentAt(segments, j).unlock();
}
} return overflow ? Integer.MAX_VALUE : size;
}
登录复制
区别
ConcurrentHashMap与HashMap相比有以下区别
Java 8 基于 CAS 的 ConcurrentHashMap
注：本章代码基于JDK 1.8.0_111
数据结构
为了实现并行访问，Java 7引入了Segment结构，它实现了段锁。 理论上，最大并发数等于Segments的数量。 为了进一步提高并发性，Java 8放弃了分段锁方案，而是直接使用大链表。 同时，为了提高哈希碰撞下的轮询性能，当数组宽度超过时，Java 8将数组（寻址时间复杂度O(N)）转换为红黑树（寻址时间复杂度O(N)）一定的阈值（8）。 为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以及对下一个元素的引用都是通过volatility来修改的，可见性也得到了保证。
static class Node implements Map.Entry {
final int hash; final K key;
volatile V val; volatile Node next;
}
登录复制
Key对应的数组元素的可见性是由Unsafe的getObjectVolatile方法保证的。
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
登录复制
大小运算
put方法和remove方法会通过addCount方法维护Map的大小。 size方法通过sumCount获取addCount方法维护的Map的大小。
