How to generate a hash code from three longs

Question

I have a HashMap with coordinates as keys.

Coordinates have 3 longs holding the x, y and z coordinate. (Coordinate is and needs to be a custom class, the coordinates need to be longs).

Now i want to be able to access e.g. the field [5, 10, 4] by doing: hashMap.get(new Coordinate(5, 10, 4)).

I have implemented the equals method but that is not enough since apparently i need to provide an implementation for hashCode as well. So my question is how do i generate an unique hashCode from three longs?.

Additional: Using a hash generator from an external library is not option.

Revisory

Answer 1

Joshua Bloch tells you how to write equals and hashCode for your Coordinate class in chapter 3 of his "Effective Java".

Like this:

public class Coordinate
{
    private long x;
    private long y;
    private long z;

    @Override
    public boolean equals(Object o)
    {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Coordinate that = (Coordinate) o;

        if (x != that.x) return false;
        if (y != that.y) return false;
        if (z != that.z) return false;

        return true;
    }

    @Override
    public int hashCode()
    {
        int result = (int) (x ^ (x >>> 32));
        result = 31 * result + (int) (y ^ (y >>> 32));
        result = 31 * result + (int) (z ^ (z >>> 32));
        return result;
    }
}

Instead

+1 for the interesting link, just that if i calculate it that way, the integer has a good chance of flowing over, is that the way it's used to be? – Revisory

Now, it won't flow over. You'll return a meaningful int. – Instead

But i take long1 = Integer.MAX_VALUE, long2 = 5 and long3 = 10, the the result will at some point flow over no? at least when i do result * 37? I'm just trying to fully understand it, excuse me if i'm being stubborn – Revisory

@Samuel, a hashcode is intended to be evenly distibuted and pseudo-random. It is a hash function and is not intended to be unique. ;) – Amusing

Okay thank you a lot, i'll probably use the book for more than just this :) – Revisory

Answer 2

This is an old question, but if anyone bumps into it, now there is an easier way to do it:

@Override 
public int hashCode() {
    return Objects.hash(x, y, z);
}

Rocky

@Carlos: A standard language feature, that is being used by millions of programs, is always easier and safer than writing your own :) – Rocky

Your proposal (x + y + z) will lead to collisions for (0 + 0 + 1) or (1 + 0 + 0) or (0 + 1 + 0). Using a standard feature of a language, which has been developed, verified, tested, and retested millions of times, is always safer. – Rocky

Answer 3

In Java, the standard hashCode() method returns int, which is 32 bits.

The long datatype is 64 bits. Therefore, three longs means 192 bits of information, which of course cannot be uniquely mapped into just 32 bits of hash value by any hash function.

However, a HashMap will not require unique hashing, it will simply handle the collisions when they occur.

A naive way would be to build the string, i.e. "x,y,z", then hash the string.

You could also try just XOR:ing the values together:

int hashCode()
{
  return (int) (x ^ y ^ z);
}

Almondeyed

Answer 4

how do i generate an unique hashCode from three longs?

You don't need to. Hash codes are not required to be unique.

Elata

Answer 5

You should realize there is a difference between a hashcode and the unique key to be used in a HashMap.

The hashcode for your Coordinate class does not have to be unique at all...

A good solution for the hashcode would be:

(int)(x ^ (x >> 32) ^ y ^ (y >> 32) ^ z ^ (z >> 32));

Wich is the XOR of the two halves of each of the longs XOR-ed together.

Jodhpur