8

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.

Samuel
  • 18,286
  • 18
  • 52
  • 88

5 Answers5

18

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;
    }
}
duffymo
  • 305,152
  • 44
  • 369
  • 561
  • 1
    +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? – Samuel Apr 20 '11 at 12:39
  • Now, it won't flow over. You'll return a meaningful int. – duffymo Apr 20 '11 at 12:40
  • 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 – Samuel Apr 20 '11 at 12:45
  • 1
    @Samuel, a hashcode is intended to be evenly distibuted and pseudo-random. It is a hash function and is not intended to be unique. ;) – Peter Lawrey Apr 20 '11 at 12:46
  • Okay thank you a lot, i'll probably use the book for more than just this :) – Samuel Apr 20 '11 at 12:52
5

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);
}
Andrei Volgin
  • 40,755
  • 6
  • 49
  • 58
  • @Carlos: A standard language feature, that is being used by millions of programs, is always easier and safer than writing your own :) – Andrei Volgin Oct 28 '19 at 18:55
  • 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. – Andrei Volgin Oct 29 '19 at 03:17
4

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);
}
unwind
  • 391,730
  • 64
  • 469
  • 606
2

how do i generate an unique hashCode from three longs?

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

user207421
  • 305,947
  • 44
  • 307
  • 483
1

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.

Fortega
  • 19,463
  • 14
  • 75
  • 113