Posts

Showing posts from October, 2013

Unique hashCodes is not enough to avoid collisions.

There is a common misconception that if you have unique hashCode() you won't have collisions.  While unique, or almost unique, hashCodes are good, this is not the end of the story. The problem is that the size of a HashMap is not unlimited (or at least 2^32 in size)  This means the hashCode() number has to be reduced to a smaller number of bits. The way HashMap, and thus HashSet and LinkedHashMap ,work is to mutate the bits in the following manner     h ^= (h >>> 20) ^ (h >>> 12);     return h ^ (h >>> 7) ^ (h >>> 4); and then apply a mask for the lowest bits to select a bucket.  The problem is that even with unique hashCode()s as Integer does, there will be values with different hash code map to the same bucket. You can research how Integer.hashCode() works ;) public static void main(String[] args) {     Set integers = new HashSet<>();     for (int i = 0; i <= 400; i++)         if ((hash(i) & 0x1f) == 0)