HashMap原理解析

2021-10-30 本文已影响0人嗷嗷待哺丶

一、hashmap的数据结构

底层数组+单向链表，jdk1.8后，链表长度大于8，并且数组长度大于64，将转为用红黑树存储

二、hashmap用了hash为什么还要equals

因为hash也会重复，hash重复但是值不一定相等，所以要使用equals进行判断

三、hashmap中put方法的过程

计算hash值， key.hashCode()>>>16，用高16位和低16位进行异或运算（二进制按位比较，如果相同则为 0，不同则为 1）。
然后根据hash值计算出数组下标（跟数组长度进行与运算），将元素放入数组中，如果没有出现哈希冲突，则直接放入数组，如果出现哈希冲突，则以链表的方式放在链表最后（jdk1.7使用头插法，也就是放在链表最前面，jdk1.8使用了尾插法，放在了链表最后面）。
如果链表的长度超过8，并且数组长度大于64，就把链表转成红黑树，如果链表长度低于6，就把红黑树转回链表；
如果数组中键值对的总量超过了阈值（负载因子0.75），会进行动态扩容。

四、负载因子是什么

负载因子用来实现hashmap动态扩容，默认0.75是在时间和空间上折中的一个选择。

扩容阈值计算公式：threshold = capacity * loadFactor （capacity是数组容量，初始化默认16，loadFactor是负载因子，初始化默认0.75）

负载因子对hashmap的影响

负载因子越大，意味着容器中元素存得越满，虽然节省了空间，但是也增加了元素哈希冲突的概率
负载因子越小，容器中空余的位置越多，虽然减少了元素哈希冲突的概率，但也造成了大量的空间浪费

默认的负载因子 DEFAULT_LOAD_FACTOR = 0.75，这是 jdk 设置的一个比较合适的负载因子，一般情况下不推荐去修改它。特殊情况下：

对内存空间要求比较苛刻，而对元素查找速度要求不高，可以把负载因子调高（时间换空间）
对程序运行速度要求苛刻，而内存空间充足的情况，可以把负载因子调低（空间换时间）

五、hash冲突有什么解决方式

开放定址法：当冲突发生时，使用某种探查（探测）技术再散列表中形成一个探查（探测）序列。沿此序列逐个单元的查找，直到找到给定的关键字，或者碰到一个开放的地址（地址单元为空）为止。
- 线性探查法
- 线性补偿探测法
- 随机探测
链地址法（拉链法）：将所有冲突的值，都存到同一个链表里。（HashMap就是用的这种方式）
再哈希法：当发生冲突时，使用第二个、第三个......等哈希函数计算地址，一直到不冲突为止。
公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，都记录到溢出表。

六、hashmap为什么在jdk1.8后引入了红黑树？为什么不一直使用？

之所以引入红黑树是为了解决二分查找树的缺陷，二分查找树在特殊情况下会变成一条线性结构（这就跟原来的链表结构一样了，造成很深的问题），遍历查询会非常慢。

而红黑树在插入新数据后会通过左旋、右旋、变色这些操作来保持平衡，引入红黑树就是为了查询数据快，解决链表查询深度的问题，红黑树属于平衡二叉树，但是为了保持“平衡”是要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

七、为什么hashmap的容量必须是2的n次幂

数组大小必须为 2 的 n 次幂，也就是 16、32、64….不能为其他值。因为如果不是 2 的 n 次幂，那么经过计算的数组下标会增大碰撞的几率。

如果hash值的二进制是：
10000（十进制16）
10001（十进制17）
10010（十进制18）

和10100做&运算后（与运算，二进制按位比较，都为1结果才为1，否则为0），结果都是10000，也就是都被映射到数组16这个下标上。这三个值会以链表的形式存储在数组16下标的位置。这显然不是我们想要的结果。

但如果数组长度n为2的n次幂，2进制的数值为10，100，1000，10000……n-1后对应二进制为1，11，111，1111……这样和hash值低位&后，会保留原来hash值的低位数值，那么只要hash值的低位不一样，就不会发生碰撞。

同时 (n - 1) & hash 等价于 hash%n，那么为什么不直接用hash%n呢？这是因为按位的操作效率会更高。

1. 为什么不直接用 key 的 hashCode？

其实说到底还是为了减少碰撞的概率。我们先看看计算hash值方法中的代码做了什么事情：

h ^ (h >>> 16)

这个意思是把 h 的二进制数值向右移动 16 位。我们知道整形为 32 位，那么右移 16 位后，就是把高 16 位移到了低 16 位。而高 16 位清0了。

^为异或操作，二进制按位比较，如果相同则为 0，不同则为 1。
这行代码的意思就是把高低16位做异或。如果两个hashCode值的低16位相同，但是高位不同，经过如此计算，低16位会变得不一样了。

2. 为什么要把低位变得不一样呢？

这是由于哈希表数组长度n会是偏小的数值，那么进行 (n - 1) & hash 运算时，一直使用的是hash较低位的值。那么即使hash值不同，但如果低位相当，也会发生碰撞。而进行 h ^ (h >>> 16) 加工后的hash值，让hashCode高位的值也参与了哈希运算，因此减少了碰撞的概率。

八、红黑树特点

红黑树是一种近似平衡的二叉查找树，他并非绝对平衡，但是可以保证任何一个节点的左右子树的高度差不会超过二者中较低的那个的一倍。

每个节点要么是红色，要么是黑色。
根节点必须是黑色。叶子节点必须是黑色NULL节点。
红色节点不能连续。
对于每个节点，从该点至叶子节点的任何路径，都含有相同个数的黑色节点。
能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。

九、hashmap扩容机制

如果table == null, 则为HashMap的初始化, 生成空table返回即可;
如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1(注, 如果原oldLength已经到了上限, 则newLength = oldLength);
遍历oldTable:
1. 首节点为空, 本次循环结束;
2. 无后续节点, 重新计算hash位, 本次循环结束;
3. 当前是红黑树, 走红黑树的重定位;
4. 当前是链表, JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过 (e.hash & oldCap) == 0 来判断是否需要移位; 如果为真则在原位不动, 否则则需要移动到当前 hash槽位 + oldCap 的位置;

再来看下 e.hash & oldCap == 0为什么可以判断当前节点是否需要移位, 而不是再次计算hash;

首先我们知道 HashMap 计算 key 所对应数组下标的公式是 (length - 1) & hash，其中 length 是数组长度，hash 是 hash值，这个公式等价于 hash % length (当 length 是 2 的 n 次幂时) 。
从下图中我们可以看出，hash % length 的结果只取决于小于数组长度的部分，这个 key 的 hash 值的低四位就是当前所在数组的下标。扩容后 新数组长度 = 旧数组长度 * 2，也就是左移 1 位，而此时 hash % length 的结果只取决于 hash 值的低五位，前后两者之间的差别就差在了第五位上。

如果第五位是 0，那么只要看低四位 (也就是当前下标)；如果第五位是 1，只要把二进制数 10000+1110 ，就可以得到新数组下标。前面的部分刚好等于旧数组长度，后面的部分刚好是当前的下标。那么我们就得出来了为什么把 low 插入扩容后新数组[当前坐标] 的位置，把 high 插入扩容后新数组[当前坐标 + 旧数组长度] 的位置。
那为什么根据 (e.hash & oldCap) == 0 来做判断条件呢？是因为旧数组的长度 length 的二进制数的第五位刚好是 1 其它位全为 0，而 & 运算相同为 1 不同为 0，因此 hash & length 的目的就是为了计算 hash 值的第五位是 0 还是 1。

部分源码：

//把原链表中的元素插入到 low 和 high 链表中，依靠 (e.hash & oldCap) == 0 判断
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;
}


//把 low 的头结点插入到当前数组下标的位置，
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
//把 high 的头结点插入  新数组中 [当前数组下标 + 旧数组长度] 的位置
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}