HashMap
HashMap 在jdk 1.7和1.8有大的改动，我们知道HashMap是线程不安全的，但是jdk 1.7的HashMap在多线程中有一个致命的问题：在rehash时可能链表成环，导致查询死循环。1.8修补了这个bug。
JDK 1.7
数据结构
采用 （数组+链表）的结构存储数据。数组是槽，链表存储数据节点。
在HashMap中有一个加载因子loadFactor 表示当HashMap中的数据达到总空间的多大比例时进行扩容，默认是0.75。这个是空间换时间的一个手段。
致命Bug：查询死循环
bug现象：若两个线程同时执行HashMap扩容，可能会导致某个槽的链表是如下图所示，进而导致get(key)方法死循环。
原因：
bug出现的根源在 transfer() 方法，以下是简化了的 ：
void resize(int newCapacity) {
//注意：每个线程创建一个新table,即槽数组
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
}
void transfer(Entry[] newTable, boolean rehash) {
// 1. 遍历数组,每个元素是个链表(就是常说的槽)
for (Entry<K,V> e : table) {
// 2. 遍历槽
while(null != e) {
Entry<K,V> next = e.next; //2.1. 拿到下个节点
e.next = newTable[i]; //2.2. e.next = 新槽的头
newTable[i] = e; // 2.3. 将e设置成新槽的头
e = next; // 2.4. 把next节点设置为待挪的节点
}
}
}
2.2，2.3是将一个节点挪到新槽的头。
首先我们要知道一个结论: 槽中的两个节点在扩容后可能会被分到同一个新槽。
假设扩容前的某个槽如下图包含A,B两个节点, 在扩容后，这两个节点仍然分到同一个新槽，有两个线程t1, t2同时执行 transfer 方法:
（1）t1 首次执行到步骤//2.1 时，拿到了这个槽的A和B
（2）t1 让出 cpu；
（3）t2 执行完//2：首先把A挪到新槽，然后B也挪到了这个槽，新槽如下图
（4）t1 继续执行2.2、2.3，此时A成为新槽的头，A.next指向Null。
（5）t1 执行2.4，e是B，继续循环：2.1 next为A；2.2、2.3挪B为头
（6）t1 执行2.4，e是A，继续循环：2.1 next为null； 2.2、2.3挪A为头
（7）跳出循环。这样循环链表就出现了。
若有key=C，hash(C)也落在这个新槽，当get(C)时会产生死循环。
JDK1.8
数据结构
jdk1.8的HashMap存储数据的结构与1.7有区别：
- jdk 1.7：数组 + 链表
- jdk 1.8：数组 + 链表/红黑树
在JAVA 8中，当链表中的元素超过8个之后，且空间超过64时，会将链表转换为红黑树，在这些位置进行查找的时候可降低时间复杂度 为O(logn)。
有统计，当特别大时，设置成红黑树才会比1.7的链表效率提升5%-15%，当数据量少时，反而并不一定提升，甚至还不如链表。
【面试题】链表转红黑树，为什么数量要定成8？
因为根据泊松分布（重点答这个名称，记不住就说“从概率学的角度”）分析，当链表达到8时，概率是0.00000006（记不住可以说非常低） * length，当数组长度很大时，出现的概率才会大些。所以设置成8。
解决1.7的问题
我们知道，扩容会将数组长度翻倍。在jdk 1.8中并没有rehash。
HashMap扩容有个特性：扩容后，节点要么落在原槽号，要么落在原槽号+oldCap上。
这个规律首先是由于槽都是2的指数次幂，且扩容是翻倍；其次是计算落槽算法：hashcode & length，当扩容后，hashcode & (length*2)，要么与原值相同，要么就是加上length。
譬如
3 & 8 = 3; 13 & 8 = 5
3 & 16 = 3; 13 & 16 = 13
举个例子：原table有8个槽，A节点在第3槽，扩容到16个槽后，A要么落在第3槽，要么落在3+8=11槽。
在这个例子中，我们把前8个槽称为++低槽++，把后8个槽称为++高槽++。
jdk1.8利用上面的这个特性，重写了 resize() 方法：遍历槽节点前，先创建两个列表：低槽列表，高槽列表。然后将这个槽的节点按规律分到各自的列表，最后将这两个列表整体替换到新table中。
resize()方法部分代码：
//遍历槽数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> loHead = null, loTail = null; // loHead、loTail 表示低槽列表
Node<K,V> hiHead = null, hiTail = null; // hiHead、hiTail 表示高槽列表
Node<K,V> next;
//遍历节点
do {
next = e.next;
if ((e.hash & oldCap) == 0) {// 重点之一：高低槽的计算方法，精辟。
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//重点之二：把两个列表替换到新table中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
所以1.8避免了列表成环的问题。
