29

我正在阅读有关 hashmap 的工作原理。我正在阅读 “如果两个不同的对象具有相同的哈希码会发生什么”。

根据它，如果两个对象具有相同的哈希码，两者都将被存储，LinkedList但据我所知，如果两个哈希码，那么前一个将被新的哈希码覆盖（如果我错了，请纠正我）。

有人可以更详细地说明hashmap如何在内部使用对象作为键，如果两个对象具有相同的hashcode会发生什么以及如何获取这两个对象get()？

4

5 回答 5

40

不，第一个不会仅仅因为第二个具有相同的hashCode.

只有当它也相等时才会被覆盖（如 所说equals）。如果没有，这两个值都将保存在链表中。

获取键时，所有具有相同键的节点hashCode将与提供的键进行比较，直到一个相等，然后返回其值（使用equals方法）。

如果地图中没有相同的键，您将得到null.

如果许多对象具有相同的 hashCode（或更确切地说是相同的 hashCode 以 internal 的大小为模Entry[] table），您遇到的唯一问题是链接列表将始终被读取，这更慢（并且破坏了任何哈希表的目的）。这就是为什么在设计一种hashcode方法以确保生成的整数分布良好时很重要的原因。

于 2013-01-09T17:26:46.850 回答
6

让我解释一下 hashmap 的工作原理。

put方法的工作：

HashMap 的工作原理是散列，我们有存储put()和get()检索对象形式的 HashMap 的方法。当我们将键和值都传递put()给存储在 HashMap 上的方法时，它使用键对象hashcode()方法来计算哈希码，并且它们通过对该哈希码应用哈希来识别存储值对象的存储桶位置。在检索它时，它使用键对象 equals 方法来找出正确的键值对并返回与该键关联的值对象。HashMap 在发生冲突时使用链表，对象将存储在链表的下一个节点中。HashMap 也将 key+value 元组存储在链表的每个节点中

get方法的工作：

当我们将 Key 和 Value 对象传递给put()Java HashMap 上的方法时，HashMap 实现会调用 Key 对象上的 hashCode 方法，并将返回的 hashcode 应用到自己的哈希函数中，以找到存储 Entry 对象的桶位置，重要的一点是 Java 中的 HashMap 存储键和值对象都作为存储桶中的 Map.Entry。如果在桶中找到多个 Entry 对象，它将调用同一桶中每个节点的 ke.equals 方法。

于 2013-01-10T11:22:48.173 回答
4

假设您遵循定义hashCode和equals的规则，您描述的场景不会导致数据丢失。最多，性能会随着时间的推移而下降。

于 2013-01-09T17:28:21.827 回答
2

在 Java hashmap 中，他们可以使用多种方法来做到这一点。来自我在黑暗时代的旧 CS 201 数据结构课程：

1）哈希图中的每个桶都可以成为一个链表的头部，该链表包含所有添加的具有相同哈希值的条目。添加时发生冲突意味着您将新条目添加到链表的末尾。搜索意味着一旦你散列到桶中，你必须线性检查任何链表中的所有链表。

2）如果发生冲突并且存储在概念上是一个数组，您可以从该点开始迭代，直到找到一个空点并在那里添加新条目。对于搜索，这意味着如果您发现哈希桶被占用，那么您必须从该点线性比较数组中支持哈希映射的下一个空点。

在这两种情况下，如果有多个条目具有相同的哈希值，性能就会下降。在一般情况下，这意味着散列函数（用于生成散列码）返回少量可能的值，随着映射的填满，性能会下降。Java HashMap 利用了 50 年来对此类事物的研究，非常适合一般数据进入散列映射的一般情况。

注意@dystroy 对根据 equals() 方法在映射中不能有两个匹配项的规则发表了评论。

于 2013-01-09T17:31:08.667 回答
2

在 Java 8 中，他们彻底检查了HashMap. 现在哈希桶被组织为链表或平衡二叉树，具体取决于：

  • 哈希数组大小，和/或
  • 给定存储桶中的条目数。

这意味着在许多条目落在同一个哈希桶中的情况下，您不再会遇到灾难性的糟糕性能。

有关更多信息，请阅读此博客文章：

于 2021-11-21T08:42:56.407 回答