java - 如果 Keys 哈希码相同但 equals 方法返回 false，HashMap 如何检索不同的值

Question

我无法理解 HashMap 的工作模式。请帮助理解它。

假设我们有两个对象 Obj1 和 Obj2 具有与 1212 相同的哈希码。现在，当我们运行“==”和 equals 时，它会返回 false。

现在我使用 ValueObj1 和 Valueobj2 作为 HashMap 中的值，键分别为 Obj1 和 Obj2。 我相信这两个值都将保存在与列表相同的存储桶中。

我的问题是 HashMap 如何为 Obj2 选择 V​​alueobj2 并为 Obj1 选择 V​​alueObj1。假设有 n.. 这样的对象和值。即使哈希码相同但值不同，此键--> 值关联如何在内部工作。

假设两个条件 equals 都没有被覆盖和被覆盖。

Answer 1

HashMap/HashSet 为每个桶实现一个键列表(在 Map 的情况下连同值)。如果多个键共享相同的 hashCode 值，它们将被放置在此列表中。

因此搜索方法首先提取查询键的hashCode，然后遍历相应的列表，直到equals 方法成功。在 HashSet 的情况下，这意味着找到了 key，在 HashMap 的情况下，它返回元组的另一端:值.

HashMap 的内存工作方式如下:

+--------+--------+--------+--------+
|   00   |   01   |   10   |   11   |
+--------+--------+--------+--------+
    |        |        |        |
 k00/v00     _     k06/v06     _
    |                 |
 k08/v08           k14/v14
    |                 |
 k04/v04              _
    |
    _

您看到的是在四个桶的顶部。每个桶都有一个列表(下面的项目)，用于存储键 (k) 和值 (v) 的元组。由于这里只有四个桶，哈希算法使用模 4 运算，所以一个值为 v06 的键 k06 将被放入桶 06 mod 4 = 02 因此 10。如果第二个 key k14 添加了 14 mod 4 = 02 因此 10，它只是添加到列表中。

由于值也存储在其中，因此可以执行快速查找操作。因此，键与值一起存储。

您注意到，遍历(链接的)列表是一项开销很大的操作。但是 HashMap 的要点是人们希望使用正确术语(共享同一存储桶的键数)的散列冲突的数量非常低。通常，人们可能期望每个桶有两个或三个元素。因此，性能提升是通过在恒定时间内选择正确的桶实现的，但是搜索桶需要线性时间(或者如果键的顺序是完整的，则可以实现(平衡的)二进制树以对数时间搜索)。然而，在最坏的情况下，HashMap 可以实现与条目的 ArrayList/LinkedList 相同的性能，但给定 hash-功能设计得不错，几率很低。