Container with xyz key

Question

I need a fast container to store objects in Java, the objects have (static) XYZ coordinates and all the objects have different coordinates. Basically a grid, but it might not be centered around 0,0,0 (and there might be missing parts in the grid).

I tried using a Map with a Integer as key and bit-shifting the coordinates so it would create a unique number for every coordinate. But this didn't work out too well when the numbers were higher then 255 (8 bits).

Also arrays don't work as key, since maps don't actually look at the value of the array, but at the reference. I could also use a String as key, but then everytime I want to access an object, I will need to (re)build a String.

Now I am using a ArrayList and looping through all the keys, but that is really slow. So what would be the fastest (and memory-efficient) way to store the objects?

Answer 1

Create a custom class, with a custom hashCode() and equals() method to use as the key.

public static class Vertex {
    public int x, y, z;
    public boolean equals(Object o){
        if(this == o) return true;
        if(!(o instanceof Vertex)) return false;
        Vertex v = (Vertex)o;
        return x == v.x && y == v.y && z == v.z;
    }

    public int hashCode(){
        //  Use whatever prime numbers you like
        return x ^ y * 137 ^ z * 11317;
    }
}

Just make sure you never, ever change the values of an instance that you're using as a key.

This isn't significantly worse than using simple integers. It's still effectively constant-time access.