一、HashMap简介：
1、数据结构
image.png
数组+链表的结构，每一对k:v都封装成一个entry，通过链表解决冲突和碰撞。
put(k, v)：首先对key哈希找到table对应的位置index，如果该位置没有entry，直接放进去，如果该位置已经有entry了，插入表头；
当table里的元素达到一定阈值的时候，通过rehash扩大table的大小(2倍)降低冲突/碰撞率；
2、HashMap存在的问题：
线程不安全
丢失数据：put进去一个元素，get却是null
死循环，CPU利用率被打满
二、一个完美的HashMap死循环是如何产生的
如何产生的：多线程，put操作导致rehash，把元素从旧table拷贝(transfer)到新table中时，可能产生死循环。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//下面这段代码的意思是：从OldTable里摘一个元素出来，然后放到NewTable中
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> 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;
}
}
}
1、正常的ReHash过程
我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table1这里了。
接下来的三个步骤是Hash表 resize成4，然后所有的 重新rehash的过程。
image.png
2、并发的rehash过程
do {
Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
假设线程1在上述代码注释处被挂起了，而我们的线程二执行完成了，于是我们有下面的这个样子：
image.png
此时线程1回来继续执行：
image.png
线程一接着工作，把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移：
image.png
环形链出现：
image.png
此时如果我们执行map.get(11)就会陷入死循环，慢慢耗尽CPU。
三、解决方案
- 用HashTable替换HashMap
- 加锁，线程同步
- 用concurrentHashMap替换HashMap
