哈希映射条目冲突

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调试器中这种差异背后的原因是什么呢？这是日食问题吗？或者哈希问题.对于2个键,哈希码是不同的.

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

由于length是HashMap的初始容量(默认为16),因此两个键都得到4:

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

因此,这两个条目存储在一个链表中的地图的同一桶(索引4的的table阵列,因为你可以在调试器看到).调试器只显示其中一个这一事实并不意味着另一个被覆盖.这意味着您可以看到链接列表的第一个条目的键,并且每个新条目都会添加到列表的开头.