0

How do you in a general (and performant) way implement hashcode while minimizing collisions for objects with 2 or more integers?

update: as many stated, you cant ofcource eliminate colisions entierly (honestly didnt think about it). So my question should be how do you minimize collisions in a proper way, edited to reflect that.

Using NetBeans' autogeneration fails; for example:

public class HashCodeTest {
    @Test
    public void testHashCode() {
        int loopCount = 0;
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (int outer = 0; outer < 18; outer++) {
            for (int inner = 0; inner < 2; inner++) {
                loopCount++;
                hashSet.add(new SimpleClass(inner, outer).hashCode());
            }
        }
        org.junit.Assert.assertEquals(loopCount, hashSet.size());
    }

    private class SimpleClass {
        int int1;
        int int2;

        public SimpleClass(int int1, int int2) {
            this.int1 = int1;
            this.int2 = int2;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 17 * hash + this.int1;
            hash = 17 * hash + this.int2;
            return hash;
        }
    }
}
2
  • Why do you need to eliminate collisions? Usually minimizing collisions is sufficient, and this code does a pretty good job of that.
    – Michael Myers
    Apr 5, 2012 at 18:59
  • yes you are ofcource right, i updated my question. and im not sure i agree it does a good job when it fails for such a small subset (although optimized abit to fail) Apr 5, 2012 at 19:02

5 Answers 5

1

Can you in a general (and performant) way implement hashcode without colisions for objects with 2 or more integers.

It is technically impossible to have zero collision when hashing to 32 bits (one integer) something made of more than 32 bits (like 2 or more integers).

1

This is what eclipse auto-generates:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + getOuterType().hashCode();
    result = prime * result + int1;
    result = prime * result + int2;
    return result;
}

And with this code your testcase passes...

PS: And don't forget to implement equals()!

0

There is no way to eliminate hash collisions entirely. Your approach is basically the preferred one to minimize collisions.

0

Creating a hash method with zero collisions is impossible. The idea of a hash method is you're taking a large set of objects and mapping it to a smaller set of integers. The best you can do is minimize the number of collisions you get within a subset of your objects.

0

As others have said, it's more important to minimize collisions that to eliminate them -- especially since you didn't say how many buckets you're aiming for. It's going to be much easier to have zero collisions with 5 items in 1000 buckets than if you have 5 items in 2 buckets! And even if there are plenty of buckets, your collisions could look very different with 1000 buckets vs 1001.

Another thing to note is that there's a good chance that the hash you provide won't even be the one the HashMap eventually uses. If you take a look at the OpenJDK HashMap code, for instance, you'll see that your keys' hashCodes are put through a private hash method (line 264 in that link) which re-hashes them. So, if you're going through the trouble of creating a carefully constructed custom hash function to reduce collisions (rather than just a simple, auto-generated one), make sure you also understand who's going to use it, and how.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.