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)
            integers.add(i);
    Set integers2 = new HashSet<>();
    for (int i = 400; i >= 0; i--)
        if ((hash(i) & 0x1f) == 0)
            integers2.add(i);
    System.out.println(integers);
    System.out.println(integers2);

}

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

this prints:

[373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]
[0, 34, 68, 102, 137, 171, 205, 239, 275, 305, 343, 373]

The entries as in the reverse order they were added as the HashMap is acting as a linked list, placing all entries into the same bucket.

Solutions?

A simple solution is to have a bucket turn into a tree instead of a linked list.  In Java 8, it will do this for String keys, but this could be done for all Comparable types AFAIK.

Another approach is to allow custom hashing strategies to allow the developer to avoid such problems, or to randomize the mutation on a per collection basis, amortizing the cost to the application.

Other notes

I would favour supporting 64-bit hash codes, esp for complex objects.  This has a very low chance of collision in the hash code itself and supports very large data structures well. e.g. into the billions.
 

Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

Leave a Reply


eight × = 24



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books