如果两个不同的对象具有相同的哈希码，会发生什么？

Question

我理解两个不相等的对象可以有相同的哈希码。在 Java 的 HashMap 中，当添加或检索时，这将如何处理？

- Joey

---

顺便提一下：您可以轻松地创建许多具有相同哈希码的Long值来尝试此操作。 对于n >= 0，所有new Long(n * 0x100000001L)都具有哈希码0。 - Peter Lawrey

Answer 1

它们将被添加到同一个桶中，并使用equals()方法来区分它们。每个桶可以包含具有相同哈希码的对象列表。

理论上，你可以为给定类的任何对象返回相同的整数作为哈希码，但这意味着你失去了哈希映射的所有性能优势，实际上将在列表中存储对象。

- Alex Gitelman

---

默认情况下，HashMap是否应用了补充哈希来防止发生这种情况，并引入一些分布？ - Ajay

关于性能的额外说明，在Java8中，当我们有太多不相等的键产生相同的哈希码（索引）时 - 当哈希桶中的项目数量超过某个阈值（TREEIFY_THRESHOLD = 8）时，该桶的内容从使用Entry对象的链表切换到平衡树。这在理论上将最坏情况下的性能从O（n）提高到O（log n）。 - Sampath Kumar Madala

Answer 2

在HashMap中，键和它们关联的值被存储在桶(bucket)中的链表节点中，并且在hashmap中使用equals()方法而不是hashcode()方法对键进行比较。

hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209 
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.

• 如果a.equals(b)返回true，则bValue将替换aValue并返回bValue。
• 如果a.equals(b)返回false，则在桶列表中将创建另一个节点，因此当调用get("b")时，您将获得bValue，因为a.equals(b)为false。

- Yash

---

如果哈希码相同，我如何检索a的值？它会给我bValue，但我想要aValue。这可能吗？ - Sanket

@Sanket，如果a.equals(b)为真，则意味着键a、b相等。因此，即使它们具有相同的哈希码，由于键相等，旧的(aValue)值将被新的(bValue)值替换。因此，您无法检索aValue。希望这能帮助未来有同样疑问的人消除困惑。 - Brooklyn99

Answer 3

HashMap工作原理是基于哈希和索引的概念。 在内部，HashMap将值存储在节点数组中。 每个节点都像链表一样运作。

链表的每个节点有4个值：

1. int hash 2. K key 3. V value 4. Node next

HashMap的内部结构如下：

在向HashMap中插入值时，首先会生成Key的哈希码，然后根据某个算法计算索引。

因此，我们的值将存储在具有哈希码、键、值和下一个元素地址的特定索引中。

在从HashMap中检索值时，首先会生成哈希码，然后生成索引（与插入时相同）。在从索引获取值时，首先会检查哈希码，如果哈希码匹配，则使用equals方法从节点中检查键。

如果键匹配，则返回该值，否则它将检查具有相同哈希码的下一个节点。

- Gaurav Lal

Answer 4

当两个不相等的对象具有相同的哈希值时，这会在哈希表中引起冲突，因为这两个对象都想在同一个插槽（有时称为桶）中。哈希算法必须解决这种冲突。回忆起我大学算法课程的模糊记忆，我记得有三种基本方法：

1. 在哈希表中查找下一个空插槽，并将对象放置在那里。优点：易于实现，缺点：可能导致对象聚集并降低性能，容量可能超过限制
2. 在发生冲突时使用第二个哈希函数：优点：通常很快，缺点：必须编写第二个哈希函数，仍可能发生冲突，容量可能超过限制
3. 从哈希表的冲突插槽中创建对象的链接列表。优点/缺点：对于良好的哈希函数和负载因子通常很快，但在最坏情况下可能会退化为线性搜索。

我认为Java哈希类使用第三种方法，但它们可能会使用组合方法。好的哈希关键在于确保哈希表具有足够大的容量并编写良好的哈希函数。只有与其持有的对象一样多的桶的哈希表可能会发生冲突。通常，您希望哈希表的大小约为存储的对象数量的两倍。Java的HashMap将根据需要增长，但如果需要，您可以给它一个起始容量和负载因子。

哈希函数取决于程序员。您可以为所有对象返回0，但这意味着哈希（存储和检索）将变为O（n），而不是O（1）...或者用通俗的话说，它将非常慢。

参考资料：http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects

- supernova

Answer 5

在这种情况下，您可以使用IdentityHashMap，在这里具有相同哈希的不同对象根据其身份被视为不同。

- kenmar