HashMap

java.util.HashMap

一、特点
1、key 和 value 都允许为空，key 只允许有一个为 null。
2、无序（这个无序指的是遍历集合的时候取出元素的顺序基本不可能是 put 的顺序）。
3、线程不安全。

二、容量 Capacity 和负载因子 Load Factor
1 capacity 默认初始化容量为 16。
2 当 hashmap 中桶被装满的数量大于容量乘以负载因子的时候会进行 rehash。

三、put 方法
1 对 key 的哈希值做 hash，然后进行取余操作；
2 根据取余结果查找对应的桶，如果没碰撞直接插入；
3 如果碰撞，插入链表头部，当链表长度过长（默认是 8），就把链表转换成红黑树；
4 如果已经存在 key 相同的节点，就替换；
5 如果桶被装满的数量大于容量乘以负载因子，那么就会进行 rehash。

四、get 方法
1 根据 key 的哈希值做 hash，然后取余；
2 根据取余结果定位到具体的桶，然后通过 equals 方法逐个节点比较 key 是否相同直到找到节点或节点不存在。

五、hash(Object key)方法
1 key 为 null，直接返回 0；
2 根据 Object.hashCode()方法获取 key 的 hashcode；
3 然后这个 hashcode 的高 16 位不变，低 16 位和高 16 位做一个异或操作；（保证 32 位的 hashcode 都参与了后面的取余操作，降低碰撞几率）

取余操作，不是通过取余符号 %，而是通过按位与（&）运算。（位运算速度快）

六、rehash 死循环问题（JDK1.8 之前）
假设
oldTable[i]->node1->node2
rehash 为：
newTable[j]->node2->node1

e
next = e.next

e.next = newTable(i);
newTable[i] = e;

e = next

线程一执行了

e //node1
next = e.next //node2

然后失去 CPU。
线程二获得 CPU 并执行完 rehash，此时

newTable[j]->node2->node1

线程一又获得 CPU 了，因为变量 e 和 next 都是局部变量，属于线程私有，所以此时

e //node1
next = e.next //node2

执行了一个节点的插入后产生死循环

node1.next = node2;
node2.next = node1;

这样 next 变量永远不可能为 null，循环就不会停止。

七、JDK1.8 resize 方法优化
每次扩容为之前的两倍，按位与的位数加 1，加的这一位只能为 0 或 1,0 的话结果不变，1 的话原位置 + 原容量。（省去重新计算 hash 的时间）。
JDK1.8 的链表元素不会倒置，因为设置了一个尾指针。

八、HashMap 的其他线程不安全问题
1 两个线程同时往同一个桶插入节点时，并发情况下会产生覆盖。

参考：
HashMap 源码
Java HashMap 工作原理及实现
Java 8 系列之重新认识 HashMap