哈希表条目冲突

Question

我正在尝试这段代码片段

Map headers=new HashMap();
headers.put("X-Capillary-Relay","abcd");
headers.put("Message-ID","abcd");

现在，当我对任一密钥执行get时，它都可以正常工作。但是，在Eclipse调试器中，我看到了一个奇怪的现象。当我调试并进入变量并检查table条目时，首先会看到这个。

->table
--->[4]
------>key:X-Capillary-Relay
...........

然而，在调试第二行之后，我得到了以下信息。

->table
--->[4]
------>key:Message-ID
...........

与创建新条目不同，它会覆盖现有的键。对于任何其他键，这种覆盖不会发生。地图的大小显示为2，并且get适用于两个键。那么在eclipse调试器中出现差异的原因是什么呢？是eclipse问题还是哈希问题？这两个键的哈希码是不同的。

- Abhiroop Sarkar

---

只要它能工作，就没有问题了，或者说有问题吗？地图不会为每个哈希值分配单独的存储桶，因此如果两个值最终落入同一个存储桶中也没有问题。而且我相信会创建一个新条目——否则你怎么能从地图中检索到这两个值呢？ - Axel

如果代码能够正常运行且哈希值不同，但Eclipse调试器显示地图内容不正确，则可能是调试器存在问题。 - slarge

我建议将HashMap视为一个黑盒子 - 只要你理解它的作用，就不需要了解它是如何实现的。(但是，如果您使用对象作为键，请务必实现hashCode()和equals()方法。) - NickJ

Answer 1

键的hashCode不是直接使用。

它要经过两次转换（至少基于Java 6代码）：

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

并且

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

由于长度是HashMap的初始容量（默认为16），因此两个键都会得到4：

System.out.println (hash("X-Capillary-Relay".hashCode ())&(16-1));
System.out.println (hash("Message-ID".hashCode ())&(16-1));

因此，两个条目都存储在映射表的同一桶中的链接列表中（如您在调试器中看到的那样，在 table 数组的索引 4 中）。调试器只显示其中一个并不意味着另一个被覆盖。这意味着您看到链接列表的第一个 Entry 的键，并且每个新的 Entry 都添加到列表的头部。

- Eran