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

Question

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

假设我们有两个对象 Obj1 和 Obj2 具有与 1212 相同的哈希码。现在当我们运行“==”并等于它时 returns false.

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

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

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

Answer 1

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

所以搜索方法首先提取查询键的hashCode，然后遍历相应的列表，直到equals方法成功。在 HashSet 的情况下，它意味着找到 key，在 HashMap 的情况下，它 returns 元组的另一边：值。

HashMap 的内存工作方式如下：

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

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

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

存储在一起

您注意到，迭代（链接）列表是一项昂贵的操作。但是 HashMap 的要点是，人们希望 哈希冲突 的数量使用正确的术语（共享同一桶的键数）非常低。通常，人们可能期望每个桶有两个或三个元素。 性能提升是通过在恒定时间内选择正确的桶来实现的，但是搜索桶需要线性时间（或者如果键的顺序是完整的，可以实现一个（平衡）二叉树以对数时间搜索）。然而，在最坏的情况下，HashMap 可以实现与条目的 ArrayList/LinkedList 相同的性能，但考虑到 hash 函数具有设计得体，几率很低。

Answer 2

You can always look at the code.

 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;
 }

因此它首先获取给定密钥的哈希值。
使用该散列找到 table（在其他答案中称为桶）。
对于存储桶中的每个条目，它都会测试键 equals 是否为 table 条目键，如果是，它会找到正确的项。

通过散列将键分区到桶中可以减少使用 equals 比较的线性搜索的大小。所以你可以看到return一个固定值的哈希码是多么有害。请参阅 this 了解有关良好哈希码计算的提示。

Answer 3

HashMap 的工作原理是根据键的哈希值将其内容分成桶。每个桶依次包含一个条目列表，一个条目由键和值组成。

假设我们要在地图中查找 x。我们计算 x.hashCode() 并选择合适的桶。然后我们遍历存储桶的列表并选择条目 e，其中 e.key 等于 x。然后我们returne.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 4

hashcode() 方法被调用并计算哈希码。此hashcode用于查找存储Entry对象的数组索引。

indexFor(hash,table.length)用于计算table数组中存放Entry对象的准确索引。

两个关键对象具有相同的hashcode（称为碰撞）

在hash map中，bucket使用简单的链表来存储对象。

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

hashmap 中存储了两个具有相同 hashcode 的键时如何检索值对象？ 使用 hashcode wo 转到正确的 bucket 并使用 equals 我们在 bucket 中找到正确的元素然后 return 它。

HashMap get()函数

如果 key 不为 null then ，它将在 key 对象上调用 hashfunction。

int hash = hash(hashValue)

hashvalue用于查找存储Entry对象的bucket位置。条目对象像这样 (hash,key,value,bucketindex) 存储在存储桶中。

详细阅读here and here

Answer 5

用 == 比较两个对象不是一个好主意，因为它会检查两个对象是否实际上链接到内存中的相同对象。

Wikipedia 上有关于哈希表的很好的 article。 java 中的 Hashmap 在 "buckets" 的数组中。

当你放置一对新的<key, value>（或者在你的情况下<obj1, valueObj1>）时，桶数是根据obj1.hashcode()计算的。该对被添加到选定的存储桶中，该存储桶是一个 LinkedList 内部存储实际对 <key, value>。

当您尝试使用键对象 obj1 搜索 valueObj1 时，hashmap 会计算该对所在的存储桶编号，并遍历所有 LinkedList 的元素进行比较equals() 键。如果瞬间equals()returnstrue，说明我们要找的元素找到了。

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

How HashMap retrieves different values if Key's hashcode is same but equals method return false

java

collections

hashmap