问HashMap底层原理？

HashMap是基于数组+链表+红黑树的哈希表。用于存储键值对。

1.哈希计算和扰动处理，也就是Hash方法

每一个Object都有一个 .hashCode 方法。

1. (哈希计算)在对hashmap进行插入和查询时，先调用key键的key.hashCode()方法获取一个未处理的int哈希值，在底层代码中该值被复制给变量h。
2. (扰动处理)通过异或运算，也就是一位一位比较，如果不同就是1，如果相同就是0。h^(h>>>16)，>>> 是无符号右移操作符，它会将 h 的二进制表示向右移动 16 位，高位用 0 填充，这样就可以将高位的信息混入低位，让哈希值在低位也均匀分布，减少碰撞。

2.索引定位

在原来手动计算的时候，我们是通过取模运算来确定的。在底层是通过(n-1)&hash计算哈希桶bucket下标，效率比取模更高。（原理）

为什么用这个公式？

1. n-1，在进行了2^n-1后，低位全是1，高位全是0。变成了低位全1的掩码。
2. 取模运算是算数运算，位运算是底层硬件级操作。且hash&(n-1)与hash%n结果完全一样
3. 20%16=4,20=00010100,20&15=00000100=4

​ 00001111

3.冲突处理

1. 如果桶的位置为空直接放入新大街店
2. 如果存在节点，就逐个比较，如果equals()相等就覆盖value，否则追加到链表尾部
3. 当单个桶中的节点数查过8且数组容量>=64,链表会转换成红黑树来降低最坏复杂度O(log n)

4.扩容机制

• 默认初始数组长度是16，负载因子是0.75
• 当元素超过阈值，数组扩容两倍，并重新分配节点位置
• 扩容后的新下标计算不是不是重新算hashCode，而是用(node.hash&oldCap)判断要留在原位置还是移动到原位置+oldCap。如果端出来的数值是0就放到相应原位置，否则放到原数组长度+目前索引的位置。(原理)
• （注）HashMap扩容时，node.hash & oldCap的作用是快速确定节点在新数组中的位置。由于oldCap是2的幂次方，其二进制只有一位为1，其余全为0，因此按位与运算的结果仅由节点哈希值中与该位对应的那一位决定——若该位为0，结果为0，节点在新数组中的位置与原位置相同；若该位为1，结果等于oldCap，节点新位置则为原位置加上oldCap。这种设计的巧妙之处在于，每次扩容都以2倍增长（保持2的幂次方），使得oldCap的二进制独有的1位会左移一位，刚好对应新容量比旧容量多出的判断位，通过一次简单的位运算就能完成节点分流，大幅提升扩容效率。

if((node.hash&oldCap)==0)-->放到newTable[i]
else 						放到newTable[i+oldCap]