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

Question

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

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

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

我的问题是HashMap如何为Obj2选择Valueobj2，为Obj1选择ValueObj1。 假设有n个这样的对象和值。即使哈希码相同但值不同，此键值关联是如何在内部工作的。

假设两个条件都未被覆盖和覆盖。

- Pawan Kumar

---

我相信这个问题在https://dev59.com/lGw15IYBdhLWcg3wntKh中没有得到解答。 - Pawan Kumar

Answer 1

HashMap/HashSet实现了每个桶(bucket)内部对键(key)的列表存储(在Map的情况下，还包括值(value))。如果多个键共享相同的hashCode值，则它们将被放置在这个列表中。

因此，搜索方法首先提取查询键的hashCode，然后迭代相应的列表，直到一个equals方法成功为止。在HashSet的情况下，这意味着找到了key，在HashMap的情况下，它返回元组的另一边：value。

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。如果添加了第二个键k14，其值为14 mod 4 = 02，因此也放置在10中的列表中。

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

您注意到，遍历(链接)列表是一个昂贵的操作。但是HashMap的重点是希望哈希碰撞的数量(共享同一桶的键数)非常低。通常情况下，每个桶可能有两个或三个元素。因此，通过在常数时间内选择正确的桶来获得性能提升，但搜索桶需要线性时间(或者如果对键进行完全排序，则可以实现(平衡)二叉树以在对数时间内搜索)。然而，在最坏情况下，HashMap可以实现与条目的ArrayList/LinkedList相同的性能，但是，如果哈希函数被合理地设计，则几率非常低。

- Willem Van Onsem

---

嗨，你的意思是键和值都存储在桶中吗？ - Pawan Kumar

你的意思是如果我们说map.get(key5)，它会从桶中选择第五个值...那么为什么要维护一个链表呢？虽然复杂度是o(5) "对于第五个值"。 - Pawan Kumar

@PawanKumar: 一般而言，由于需要维护大量的存储桶，选择正确的存储桶通常会带来极大的性能提升。但是如果哈希函数选择不当，导致所有条目都驻留在同一个存储桶中，那么HashMap的行为就像线性搜索。 - Willem Van Onsem

非常好地解釋了答案。謝謝。 - Mandar Pandit

Answer 2

您可以随时查看代码。

 public V get(Object key) {
     if (key == null)
         return getForNullKey();
     int hash = hash(key.hashCode());
     for (Entry<K,V> e = table[indexFor(hash, table.length)];
          e != null;
          e = e.next) {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
             return e.value;
     }
     return null;
 }

1. 首先，它会为给定的键获取哈希值。
2. 使用该哈希值找到表格（在其他答案中称为 bucket）。
3. 对于存储在 bucket 中的每个条目，它测试键是否与表格条目的键相等，如果相等，则找到了正确的项。

通过将键按哈希分区为 bucket，可以减小使用“equals”比较的线性搜索的大小。因此，可以看出为 hashcode 返回固定值有多么有害。请参见此处以获取有关良好的 hashcode 计算方法的提示。

- weston

---

同样的问题，你的意思是键也与值一起存储在桶中，所以可以将键与键进行比较吗？ - Pawan Kumar

@PawanKumar 是的，它们被保存在桶中的 Entry<K,V> 对象中。 - weston

这就是为什么你必须要有一个好的哈希值计算。请参考https://dev59.com/oHVD5IYBdhLWcg3wBm1g - weston

Answer 3

HashMap 通过根据键的哈希值将其内容分成桶。每个桶依次包含一个条目列表，其中条目由键和值组成。

假设我们想在映射中查找 x。我们计算 x.hashCode() 并选择相应的桶。然后我们遍历桶的列表，并选择 e.key 等于 x 的条目e。然后我们返回 e.value。

伪代码：

class Map {
    class Entry {
        Object key, value;
    }

    List<List<Entry>> buckets;

    Object get(Object key) {
        List<Entry> bucket = buckets.get(key.hashCode() % buckets.size());
        for (Entry entry : bucket) {
            if (Object.equals(key, entry.key) return entry.value;
        }
        return null;
    }
}

（免责声明：使用%计算桶索引是一种过度简化，不能直接使用；只是为了传达一般想法）

- BambooleanLogic

Answer 4

hashcode()方法被调用，计算哈希码。这个hashcode被用来找到存储Entry对象的数组的索引。

indexFor(hash,table.length)被用来计算在表格数组中存储Entry对象的确切索引。

两个具有相同hashcode的关键对象（也称为冲突）

在哈希映射中，桶使用简单的链表来存储对象。

如果两个键具有相同的hashcode，则将键值对存储在与现有键相同的桶中。

当HashMap中存储具有相同hashcode的两个键时，如何检索值对象？使用hashcode找到正确的桶，使用equals查找桶中的正确元素，然后返回它。

HashMap get()函数

如果键不为空，则会在键对象上调用哈希函数。

int hash = hash(hashValue)

hashvalue 用于查找存储 Entry 对象的桶位置。Entry 对象以以下方式存储在桶中 (hash，key，value，bucketindex)。

详细阅读请点击 这里 和 这里

- Ankur Singhal

Answer 5

使用==比较两个对象并不是一个好主意，因为它检查的是两个对象是否实际上是指向内存中相同的对象。

维基百科上有一篇很好的article关于哈希表的文章。Java中的Hashmap内部有一个“桶”数组。

当您放置一个新的键值对<key, value>（或在您的情况下<obj1, valueObj1>），桶号取决于obj1.hashcode()。这个键值对被添加到所选的桶中，该桶是一个LinkedList，用于存储实际的键值对<key, value>。

当您尝试使用键对象obj1搜索具有值对象valueObj1的哈希表时，哈希表会计算出该对位于的桶号，并迭代所有LinkedList元素，将键与equals()进行比较。如果立即返回true，则表示找到了我们要查找的元素。

- darkled