HashMap核心原理

hashMap完整的put过程

以下是对上图的详细解释：

1. 首先，要获取key的哈希值。
   如果为空，就统一是0
   否则，调用对象的.hashCode()方法，接着再与自己的右移16位进行异或，以便充分利用高位信息。
2. 接着判断内部node数组是否为空，如果是，先进行初始化扩容。默认为16。
3. 根据(n-1)&hash值，获取哈希表索引位置。 （&的性能比取余要高,具体讨论见CPU取余原理）
4. 哈希表的node数组中，存放的是每组链表的头节点。
   先检查头节点是否和自己要存放的key完全匹配 （hash值相同，key值相同，先hash再key，是因为hash的判断简单，key的equals判断可能会复杂）
   如果匹配，得到需要替换的节点。
5. 头节点和自己要放的key不匹配，则判断一下这个头节点是否是红黑树节点，如果是，说明已经升级成红黑树了，调用putTree插入到红黑树中。
6. 如果不是红黑树， 那就是遍历链表，完全匹配就得到需要替换的节点。如果到尾部了，也没匹配的，则插入新节点。
7. 如果前面找到了要替换的节点，则判断一下是否可以替换（是否没要求putIfAbsent，或者value为null），是就替换，不是就结束
8. 如果前面是插入了新节点，非替换， 则要modCount++（方便迭代器确认map是否更新）， 同时++size， 然后和扩容阈值做判断， 如果太大，就resize进行扩容

hashMap的扩容过程，java7和8扩容的区别

1. java7：

• 当resize时，新建一个数组newTable
• 遍历原table中的每个链表和节点，重新hash，找到新的位置放入
• 放入的方式是头插法，即始终插在链表的头节点。

2. java8:

• 不再每个点rehash放置，而是最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标. 避免了频繁的哈希计算和搬移过程。
• 使用尾插法在链表上插入节点
• 桶内元素超过8个，链表转成红黑树

为什么java8要改成尾插法？

A:
多线程时，java7的map-put可能造成死循环。
A线程扩容到那一半， 还处在遍历链表做头插法搬移的过程时，存了2个局部变量，当前链点now指向a， next指向b，正准备搬移（a->b->c这样的链表，a是头节点）

B线程则同时完成线程扩容，但是map里都是引用，浅拷贝，** 因为是头插法， 会导致顺序变化**， 原本a->b->c 变成了c->b->a。
因此A恢复时， 链点还是a，next还是b， 于是往下走到了b， 取bbs的next时，已经变成了a， 于是发生了a->b->a的循环
导致后续操作的next都是错误操作，引发环形指针。

java8里改成尾插法，这样做resize时，a->b->c 如果仍然哈希到同一个节点， 顺序是不会发生变化的。

虽然解决了死循环问题， 但java8的hashMap仍然是线程不安全的，为什么？

A:
因为缺乏同步，导致同节点发生哈希碰撞时，if条件的判断都可能是有问题的，导致本该插在链表头节点后面的，结果直接作为链表头覆盖到数组上了。

具体到底满足什么情况，才会resize扩容呢？

A:
　HashMap负载因子 LoadFactor，默认值为0.75f。
　衡量HashMap是否进行Resize的条件如下：
　HashMap.Size >= Capacity * LoadFactor

另一种情况。JDK1.8源码中，执行树形化之前，会先检查数组长度，如果长度小于64，则对数组进行扩容，而不是进行树形化

扩容后，capacity扩容多少倍呢？为什么

A:
哈希表每次扩容是两倍。
初始长度为2的幂次方，随后以2倍扩容的方式扩容，元素在新表中的位置要么不动，要么有规律的出现在新表中（二的幂次方偏移量），这样会使扩容的效率大大提高。
另外，hashmap采用二倍扩容还有另外一个好处：可以使元素均匀的散布hashmap中，减少hash碰撞。