如果Key的哈希码相同但等于方法return false，HashMap如何检索不同的值

Question

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

假设我们有两个对象Obj1和Obj2，它们的Hashcode都是1212。现在，当我们运行“==”和equals时，它返回false。

现在我使用ValueObj1和Valueobj2作为HashMap中的值，分别具有键Obj2和Obj3。我相信这两个值将保存在与List相同的桶中。

我的问题是HashMap如何为Obj2选择Valueobj2，为Obj选择ValueObj1。假设有n.个这样的对象和值。这把钥匙--

假设两个条件都等于不被覆盖和被覆盖。

Answer 1

< code>HashMap的工作原理是根据键的哈希值将其内容划分为多个桶。每个桶又包含一个条目列表，一个条目由键和值组成。

假设我们想在映射中查找x。我们计算x.hashCode（）并选择适当的存储桶。然后我们遍历存储桶的列表并选择条目e，其中e.key等于x。然后我们返回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;
    }
}

（免责声明：使用%来计算桶指数是一种过于简单的方法，不能按原样工作；它只是为了传达总体思想。）

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. 使用该哈希它定位表（在其他答案中称为桶）。
3. 对于存储桶中的每个条目，它会测试键是否等于表条目键，如果是，它会找到正确的项目。

使用< code>equals比较，将关键字按散列划分到桶中减少了线性搜索的规模。所以你可以看到为hashcode返回一个固定值是多么有害。关于良好的hashcode计算技巧，请参见此处。

Answer 3

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

因此，搜索方法首先提取查询关键字的＜code＞hashCode＜/code＞，然后遍历相应的列表，直到＜code＞等于＜/code＞方法成功。在＜code＞HashSet＜/code＞的情况下，这意味着找到了＜code＞键＜/code>；在＜code＜HashMap＜/code＞的情况中，它返回元组的另一端：值。

因此，HashMap 的内存工作原理如下：

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

你看到的是在四个桶的上面。每个桶都有一个列表(下面的项目)，存储键(< code>k)和值(< code>v)的元组。因为这里只有四个桶，散列算法使用模4运算，所以具有值< code>v06的关键字< code>k06将被放入桶< code>06 mod 4 = 02中，因此< code>10。如果第二个键< code>k14添加了< code>14 mod 4 = 02，即< code>10，则只需将其添加到列表中。

由于值也与它一起存储，因此可以执行快速查找操作。因此，密钥与值一起存储。

您注意到，遍历（链接）列表是一项昂贵的操作。但＜code＞HashMap＜/code＞的意义在于，人们希望使用正确术语（共享同一存储桶的密钥数）的哈希冲突次数非常少。一般来说，每个桶可能需要两到三个元素。因此，通过在恒定时间内选择正确的bucket来实现性能提升，搜索bucket需要线性时间（或者，如果键的顺序完整，可以实现（平衡）二叉树以在对数时间内搜索）。然而，最糟糕的情况是，＜code＞HashMap＜/code＞可以实现与＜code＞ArrayList＜/code＞/＜code＞LinkedList＜/code＞条目相同的性能，但考虑到哈希函数的设计得体，概率非常低。