HashMap 的工作原理是什么?

HashMap 是基于 hashing 的原理
我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。
当我们给 put() 方法传递键和值时,我们先对调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组 bucket 位置来储存 Node 对象。

这里关键点在于指出,HashMap 是在 bucket 中储存键对象和值对象,作为Map.Node

以下是 HashMap 初始化


以下是具体的 put 过程(JDK1.8)
1. 对 Key 求 Hash 值,然后再计算下标
2. 如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的 Hash 值相同,需要放到同一个 bucket 中)
3. 如果碰撞了,以链表的方式链接到后面
4. 如果链表长度超过阀值(TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表
5. 如果节点已经存在就替换旧值
6. 如果桶满了(容量16*负载因子0.75=12),就需要 resize(扩容2倍后重排),rehash的位置只可能在两处


关于具体的 get 过程
考虑特殊情况:如果两个键的 hashcode 相同,你如何获取值对象?

当我们调用 get() 方法,HashMap 会使用键对象的 hashcode 找到 bucket 位置,找到 bucket 位置之后,会调用 keys.equals() 方法逐一比较去找到链表中正确的节点,最终找到要找的值对象。

发布者

Jiaheng Tao

挖掘概念,创造工具

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据