0

我知道这已被问过很多次，但我找不到我的问题的确切答案。

在 Effective Java 的第 3 章中，有一个场景展示并解释了为什么哈希码应该与 equals 方法一起被覆盖。我得到了它的大部分内容，但其中有一部分我无法理解。

那里有一个给定的类，它覆盖了 equals 方法而不是 hashCode 方法。该对象被作为键放在地图中

Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny");

我知道如果我们get使用另一个相等的对象（m.get(new PhoneNumber(707, 867, 5309))），它将返回 null 仅仅是因为它们的哈希码没有被覆盖以返回相等对象的相等值（因为它会因为不同的哈希码而在另一个桶中搜索对象）。

但是根据我的理解，在那种情况下，不能保证两个对象的哈希码总是会返回不同的。如果它们碰巧返回相同的哈希码怎么办？

我认为这在这部分解释

即使两个实例碰巧散列到同一个桶，get 方法几乎肯定会返回 null，因为 HashMap 有一个优化，可以缓存与每个条目关联的散列码，并且如果散列码不检查对象相等性，则不会打扰不匹配。

我只是没有得到缓存的东西。有人可以详细解释一下吗？

另外，我已经完成了我的家庭作业，并找到了一个相关的问题

将与每个条目关联的哈希码缓存到其 get 方法的 HashMap 优化的影响

但是我对接受的答案并不满意，而且，回答者在评论中说

哈希码可以是任意整数，因此每个哈希码不能有自己的桶。因此，一些具有不同哈希码的对象最终会在同一个桶中。

我完全不同意。据我了解，不同的哈希码永远不会出现在同一个存储桶中。

4

2 回答 2

2

看一下 java.util.HashMap 是如何通过 hashCode 计算一个键的桶号的：

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

如果哈希表长度 = 16，那么 128 和 256 都将进入桶 #0。Hashtable 是一个条目数组：

   Entry<K,V>[] table
   ...
   class Entry<K,V> {
           K key;
           V value;
           Entry<K,V> next;
           int hash;
    ...

条目可以形成一个链 ( LinkedList)。如果桶#0 ( table[0]) 为空( null) 则新条目将直接放在那里，否则HashMap 将找到链中的最后一个条目并设置最后一个条目的next = new entry。

于 2013-04-19T03:54:38.627 回答
0

当说“即使两个实例碰巧散列到同一个桶”时，这并不意味着它们具有相同的散列码。甚至不同的哈希码也可以映射到同一个桶[阅读关于哈希]。

因此，即使密钥散列到同一个桶，也可能不会为相关元素调用 .equals （由于缓存优化）（因为甚至散列码都不匹配）。因此，即使相关元素位于同一个桶中，它也可能永远不会通过 .equals 进行比较，因此不会“找到”。

于 2013-04-19T03:46:40.627 回答