19

据我了解，两个不相等的对象可以具有相同的哈希码。从 HashMap java 添加或检索时如何处理？

4

5 回答 5

31

它们只会被添加到同一个存储桶中，equals()并将用于区分它们。每个存储桶都可以包含具有相同哈希码的对象列表。

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

于 2012-06-25T18:24:42.140 回答
10

在 HashMap 中，键及其关联值存储在桶中的链表节点中，并且键在 hashmap 中本质上是使用 equals() 方法而不是通过哈希码进行比较。

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)is false。
于 2013-06-07T01:39:30.813 回答
2

HashMap 正在研究散列和索引的概念。内部 HashMap 将值存储在节点数组中。每个节点都表现为 LinkedList。

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

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

HashMap 内部结构：

HashMap 内部结构图

在 HashMap 中插入值时，会生成 Key 的第一个哈希码，并根据某种算法计算索引。

所以我们的值将与下一个元素的哈希码、键、值和地址一起存储在特定的索引中。

从 HashMap 中检索值时，将生成第一个哈希码，然后生成索引（与插入时的方式相同）。从索引中获取值时，首先它会检查哈希码，如果哈希码匹配，那么它只会使用 equals 方法从 Node 中检查键。 如果键匹配，那么只有它会返回值，否则它将检查具有相同哈希码的下一个节点。

于 2017-08-31T08:35:51.453 回答
0

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

于 2013-11-11T11:24:22.990 回答
0

当两个不相等的对象具有相同的哈希值时，这会导致哈希表中的冲突，因为两个对象都希望位于同一个槽中（有时称为存储桶）。哈希算法必须解决此类冲突。回到我大学算法课程的褪色记忆中，我记得这样做的三种基本方法：

  1. 在哈希表中寻找下一个空槽并将对象放在那里。优点：易于实现，缺点：可能导致对象聚集并降低性能，可能会超出容量
  2. 有冲突时使用辅助哈希函数：优点：通常很快，缺点：必须编写第二个哈希函数，仍然可能发生冲突，并且可能超出容量
  3. 从哈希表的冲突槽中创建对象的链表。优点/缺点：通常对于不错的散列函数和负载因子来说很快，但在最坏的情况下会降级为线性搜索

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

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

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

于 2015-04-29T12:26:35.427 回答