Colliding entries in a hash map
I am trying to follow this piece of code
Map headers=new HashMap();
headers.put("X-Capillary-Relay","abcd");
headers.put("Message-ID","abcd");
Now when I do get
for any of these keys, it works fine. However, I see a strange phenomenon in the Eclipse debugger. When I debug and go inside the variables and check inside first table
, I see this
->table
--->[4]
------>key:X-Capillary-Relay
...........
However, after debugging on the second line, I get
->table
--->[4]
------>key:Message-ID
...........
Instead of creating a new entry, it overwrites the existing key. This overwrite does not occur for any other key. The map size is displayed 2. and get
works for both keys. So what is the reason for this inconsistency in the eclipse debugger. Is this an eclipse problem? Or hashing problem. The hash code is different for the two keys.
source to share
hashCode
keys are not used as they are.
There are two conversions applied (based on Java 6 code at least):
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);
}
and
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
Since length is the initial capacity of the HashMap (default 16), you end up with 4 for both keys:
System.out.println (hash("X-Capillary-Relay".hashCode ())&(16-1));
System.out.println (hash("Message-ID".hashCode ())&(16-1));
Therefore, both entries are stored in a linked list in the same map bucket ( 4
array index table
, as you can see in the debugger). The fact that the debugger only shows one of them does not mean that the other has been overwritten. This means that you see the key of the first entry in the linked list, and each new entry is added to the header of the list.
source to share