HashMap是如何工作的

迈不过友情╰ 2022-02-20 02:23 383阅读 0赞

![1240][]

一、HashMap在JAVA中的怎么工作的？

基于Hash的原理

二、什么是哈希？

最简单形式的hash，是一种在对任何变量/对象的属性应用任何公式/算法后， 为其分配唯一代码的方法。

一个真正的hash方法必须遵循下面的原则

哈希函数每次在相同或相等的对象上应用哈希函数时, 应每次返回相同的哈希码。换句话说, 两个相等的对象必须一致地生成相同的哈希码。

Java 中所有的对象都有Hash方法。

Java中的所有对象都继承 Object 类中定义的 hashCode() 函数的默认实现。 此函数通常通过将对象的内部地址转换为整数来生成哈希码，从而为所有不同的对象生成不同的哈希码。

三、HashMap 中的 Node 类

Map的定义是： 将键映射到值的对象。

因此，HashMap 中必须有一些机制来存储这个键值对。 答案是肯的。 HashMap 有一个内部类 Node，如下所示：

![1240 1][]

当然，Node 类具有存储为属性的键和值的映射。 key 已被标记为 final，另外还有两个字段：next 和 hash。

在下面中， 我们将会理解这些属性的必须性。

四、键值对在 HashMap中是如何存储的

键值对在 HashMap 中是以 Node 内部类的数组存放的，如下所示：

transient Node[] table;

哈希码计算出来之后， 会转换成该数组的下标， 在该下标中存储对应哈希码的键值对， 在此先不详细讲解hash碰撞的情况。

该数组的长度始终是2的次幂， 通过以下的函数实现该过程

![1240 2][]

其原理是将传入参数 (cap) 的低二进制全部变为1，最后加1即可获得对应的大于 cap 的 2 的次幂作为数组长度。

为什么要使用2的次幂作为数组的容量呢？

在此有涉及到 HashMap 的 hash 函数及数组下标的计算， 键(key)所计算出来的哈希码有可能是大于数组的容量的，那怎么办？ 可以通过简单的求余运算来获得，但此方法效率太低。HashMap中通过以下的方法保证 hash 的值计算后都小于数组的容量。

(n - 1) & hash

这也正好解释了为什么需要2的次幂作为数组的容量。由于n是2的次幂，因此，n-1类似于一个低位掩码。通过与操作，高位的hash值全部归零，保证低位才有效 从而保证获得的值都小于n。

同时，在下一次 resize() 操作时， 重新计算每个 Node 的数组下标将会因此变得很简单，具体的后文讲解。以默认的初始值16为例

01010011 00100101 01010100 00100101
    
    & 00000000 00000000 00000000 00001111
    
    ----------------------------------
    
    00000000 00000000 00000000 00000101 //高位全部归零，只保留末四位
    
    // 保证了计算出的值小于数组的长度 n

但是，使用了该功能之后，由于只取了低位，因此 hash 碰撞会也会相应的变得很严重。这时候就需要使用「扰动函数」

static final int hash(Object key) {
    
    int h;
    
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    
    }

该函数通过将哈希码的高16位的右移后与原哈希码进行异或而得到，以上面的例子为例

![1240 3][]

此方法保证了高16位不变， 低16位根据异或后的结果改变。计算后的数组下标将会从原先的5变为0。

使用了 「扰动函数」 之后， hash 碰撞的概率将会下降。 有人专门做过类似的测试， 虽然使用该 「扰动函数」 并没有获得最大概率的避免 hash 碰撞，但考虑其计算性能和碰撞的概率， JDK 中使用了该方法，且只hash一次。

五、哈希碰撞及其处理

在理想的情况下， 哈希函数将每一个 key 都映射到一个唯一的 bucket， 然而， 这是不可能的。哪怕是设计在良好的哈希函数，也会产生哈希冲突。

前人研究了很多哈希冲突的解决方法，在维基百科中，总结出了四大类

![1240 4][]

在 Java 的 HashMap 中， 采用了第一种 Separate chaining 方法(大多数翻译为拉链法)+链表和红黑树来解决冲突。

![1240 5][]

在 HashMap 中， 哈希碰撞之后会通过 Node 类内部的成员变量 Node<K,V> next; 来形成一个链表(节点小于8)或红黑树（节点大于8， 在小于6时会从新转换为链表）， 从而达到解决冲突的目的。

static final int TREEIFY_THRESHOLD = 8;
    
    static final int UNTREEIFY_THRESHOLD = 6;

六、HashMap 的初始化

public HashMap();
    
    public HashMap(int initialCapacity);
    
    public HashMap(Map m);
    
    public HashMap(int initialCapacity, float loadFactor);

HashMap 中有四个构造函数， 大多是初始化容量和负载因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 为例

![1240 6][]

通过该函数进行了容量和负载因子的初始化，如果是调用的其他的构造函数， 则相应的负载因子和容量会使用默认值（默认负载因子=0.75， 默认容量=16）。在此时， 还没有进行存储容器 table 的初始化， 该初始化要延迟到第一次使用时进行。

七、HashMap 中哈希表的初始化或动态扩容

所谓的哈希表， 指的就是下面这个类型为内部类Node的 table 变量。

transient Node\[\] table;

作为数组， 其在初始化时就需要指定长度。在实际使用过程中， 我们存储的数量可能会大于该长度，因此 HashMap 中定义了一个阈值参数(threshold)， 在存储的容量达到指定的阈值时， 需要进行扩容。

我个人认为初始化也是动态扩容的一种， 只不过其扩容是容量从 0 扩展到构造函数中的数值（默认16）。 而且不需要进行元素的重hash.

7.1 扩容发生的条件

初始化的话只要数值为空或者数组长度为 0 就会进行。 而扩容是在元素的数量大于阈值（threshold）时就会触发。

threshold = loadFactor \* capacity

比如 HashMap 中默认的 loadFactor=0.75, capacity=16, 则

threshold = loadFactor \* capacity = 0.75 \* 16 = 12

那么在元素数量大于 12 时， 就会进行扩容。 扩容后的 capacity 和 threshold 也会随之而改变。

负载因子影响触发的阈值，因此，它的值较小的时候，HashMap 中的 hash 碰撞就很少， 此时存取的性能都很高，对应的缺点是需要较多的内存；而它的值较大时，HashMap 中的 hash 碰撞就很多，此时存取的性能相对较低，对应优点是需要较少的内存；不建议更改该默认值，如果要更改，建议进行相应的测试之后确定。

7.2 再谈容量为2的整数次幂和数组索引计算

前面说过了数组的容量为 2 的整次幂， 同时， 数组的下标通过下面的代码进行计算

index = (table.length - 1) & hash

该方法除了可以很快的计算出数组的索引之外， 在扩容之后， 进行重 hash 时也会很巧妙的就可以算出新的 hash 值。 由于数组扩容之后， 容量是现在的 2 倍， 扩容之后 n-1 的有效位会比原来多一位， 而多的这一位与原容量二进制在同一个位置。 示例

![1240 7][]

这样就可以很快的计算出新的索引啦

7.3 步骤

先判断是初始化还是扩容， 两者在计算newCap和newThr时会不一样

计算扩容后的容量，临界值。

将hashMap的临界值修改为扩容后的临界值

根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。

将旧数组的元素复制到table中。在该过程中， 涉及到几种情况， 需要分开进行处理（只存有一个元素， 一般链表， 红黑树）

具体的看代码吧

![1240 8][]

![1240 9][]

![1240 10][]

7.4 注意事项

虽然 HashMap 设计的非常优秀， 但是应该尽可能少的避免 resize(), 该过程会很耗费时间。

同时， 由于 hashmap 不能自动的缩小容量 因此，如果你的 hashmap 容量很大，但执行了很多 remove操作时，容量并不会减少。如果你觉得需要减少容量，请重新创建一个 hashmap。

八、HashMap.put() 函数内部是如何工作的？

在使用多次 HashMap 之后， 大体也能说出其添加元素的原理：计算每一个key的哈希值， 通过一定的计算之后算出其在哈希表中的位置，将键值对放入该位置，如果有哈希碰撞则进行哈希碰撞处理。

而其工作时的原理如下

![1240 11][]

源码如下：

![1240 12][]

![1240 13][]

在此过程中， 会涉及到哈希碰撞的解决。

九、HashMap.get() 方法内部是如何工作的？

![1240 14][]

其最终是调用了 getNode 函数。 其逻辑如下

![1240 15][]

源码如下：

![1240 16][]

***扩展阅读***

[毕业两年半总结+19年换工作面试总结][19]

[SpringMVC工作原理][SpringMVC]

[工作少？薪资低？程序员跳槽“姿势”全攻略！][Link 1]

[HashMap？面试？我是谁？我在哪？][HashMap]

[对HashMap的思考及手写实现][HashMap 1]

来源：https://www.cnblogs.com/homejim/p/10029796.html

![70][]

[1240]: /images/20220220/ccc85e47cf3a4bc39bd850fbcf4334dc.png
[1240 1]: /images/20220220/5eb08214da9c43a38861d4321dc12b9a.png
[1240 2]: /images/20220220/8d068f037aff47f39a6f64be327a66ba.png
[1240 3]: /images/20220220/5214ce03f6c64690826fcf312cdbb771.png
[1240 4]: /images/20220220/0413b794150b44df80ef826fad946722.png
[1240 5]: /images/20220220/a8677f606aac4415a3ee929a253dd273.png
[1240 6]: /images/20220220/ce7543fb043248fdae3b75863706d238.png
[1240 7]: /images/20220220/a222796466e5443093d4d5a7117f6b95.png
[1240 8]: /images/20220220/7333e7acfe60469b8ce70c23d595d698.png
[1240 9]: /images/20220220/174de0823e984b429f674913bc69b8e6.png
[1240 10]: /images/20220220/c180fbb0f397418eba62496c346f0857.png
[1240 11]: /images/20220220/7a2bead8e7164472bd27c811dd545e8d.png
[1240 12]: /images/20220220/e3d66bead0eb4e5aa805a9bde54198e0.png
[1240 13]: /images/20220220/a37164ad3bb849deb3eba0bf1d3aa5a3.png
[1240 14]: /images/20220220/592cdc4c9423419f95aafb00029b0bcf.png
[1240 15]: /images/20220220/fcb2dc97ecdb416186a620fc0db41bfd.png
[1240 16]: /images/20220220/04ea1965024e4f23a18a2b4be0166898.png
[19]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247486321&idx=1&sn=ef25821ad80133fa8bfe4b6d88486419&chksm=fe795aa9c90ed3bf100d0c360963f16deb3580e73966caef2dc068013f883ed2e52333c54f2a&scene=21#wechat_redirect
[SpringMVC]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247486310&idx=1&sn=24652ca7d9c8662427aa03537e9c8caf&chksm=fe795abec90ed3a85093644eceded5c2eddb24e3f71049545f18adbda290de7adbf6c1f3793c&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485386&idx=1&sn=37368bd2e77c5f180bd0df64f3e57289&chksm=fe795612c90edf04ed3db4cba07c8d87e5c6640e36505366f6d3c3a593c53209a163a4d229f5&scene=21#wechat_redirect
[HashMap]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247486163&idx=1&sn=51e7c8d39f211787fa825045aa71bcfc&chksm=fe795b0bc90ed21d05ac8854b0a23000232ec5662d1fafa838c67c67c97e2cb629610222b15e&scene=21#wechat_redirect
[HashMap 1]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485145&idx=2&sn=f5a96cd16fa8b420a6e2c79d47be3fd3&chksm=fe795701c90ede17044077c9b661479db56b48828ae7ea21c3d8794b7d592318489f60e7c454&scene=21#wechat_redirect
[70]: /images/20220220/8771503b250e4ac590de5711535d4ebd.png