HashMap中的碰撞解决方法

Question

当我们将键值对放入HashMap时，可能会出现两个键的哈希码相同的情况，那么在这种情况下如何处理键值的存储和检索。

更新：

据我所知，如果两个对象的键具有相同的哈希码，则这两个键对象将被存储在同一个桶中，当我使用get(key)方法时，将通过object.equals()确定要获取哪个元素。

- Sandeep Kumar

---

https://dev59.com/TW445IYBdhLWcg3wNXk_ - Nikolay Kuznetsov

https://dev59.com/5GnWa4cB1Zd3GeqP3rxN - Nikolay Kuznetsov

Answer 1

当你想要从哈希映射中检索某个对象并且存在多个具有相同哈希码的对象时，Java将调用equals()方法以确定正确的对象。

这就是为什么在重写hashCode()时重写equals()非常重要的原因。

- Andrew Logvinov

---

谢谢您提供简单明了的答案，但我仍然有些困惑，所以您能否请评论一下我的问题更新？ - Sandeep Kumar

是的，没错。我们将遍历存储桶中的键列表，并在每个键上调用equals()方法进行比较，直到找到匹配项为止。 - Andrew Logvinov

Answer 2

每个桶由一个链表表示，因此除了堆空间之外，每个桶中的条目数量没有限制。有比可能的hashCode结果更少的桶，因此多个hash代码映射到同一个桶，而不仅是具有相同hashCode的键。

具有许多冲突的hashCode()或者桶太少的HashMap会使一些链表变得很长。良好的性能取决于短链表，因为查找的最后阶段是对其中一个链接列表进行线性扫描。

我同意先前答案中所说的，匹配取决于equals()和hashCode()两者。

- Patricia Shanahan

---

有时候桶的数量比可能的哈希码结果要少，因此不仅具有相同哈希码的键会被映射到同一个桶中，而且多个哈希码也会被映射到同一个桶中。 - Atul