HashMap 的冲突处理
Java HashMap 用链表处理散列冲突的实现思路。
发布 2019年3月18日 标签
#data-structures
#java
~/posts/hashmap-collisions $ cat post.md
背景
哈希表的基本原理大家都知道。剖析某语言哈希表实现的文章也很多。前段时间面试被问到过：
如果散列值重复了怎么办？
我答：存在同一个 slot 里面，之后访问时逐个比较。然后被追问：
用什么结构存的？
答链表。又被追问链表里每个节点的形状。这篇就把这个点写下来。
散列冲突的处理
直接看 Java 的实现思路（源码省略）：
Java HashMap 底层是一个数组，每个槽位里存的是 Entry 类的实例。Entry 包含 key、value、hash，同时也作为链表节点使用——它自己持有一个指向下一个 Entry 的指针。
- 散列值不冲突时，对应
Entry直接落到该槽位。 - 散列值冲突时，新元素替换原槽位的
Entry，并把它的next指针指向之前那个Entry。
这种实现的好处是：链表的处理逻辑不需要区分 “是不是第一个元素”。即便某个槽位只有一个唯一散列值，那个 Entry 的 next 也只是指向 null，写入新元素的逻辑完全一致。