Good hash function for list of 2-d positions?

Question

Hi!

I have a series of objects whose only different internal state is a fixed-length list(or whatever) of 2-d positions (2 integers). That is, they all have the same number of elements, with (potentially) different 2-d values.

I'm going to be constantly comparing new instances against all previously existent, so it's very important that I write a good hashing function to minimize the number of comparisons.

How would you recommend I hash them?

Answer 1

Well depending on the size of your integers, you may want to multiply the first coordinate by the max possible coordinate and add the second. For example, if X and Y are positive and have a limit of 256, you can try X*256+Y for your hash function. If X and Y can be negative as well, you may want to offset them first to make them non-negative. Also, if multiplying X by the max overflows the integer, you may want a multi-int hash value or perhaps mod or bitwise-and the result with UINT_MAX.

Answer 2

Let's say that this is a Point class:

class Point {
    public final int x;
    public final int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;
        hash = 31*hash + x;
        hash = 31*hash + y;
        return hash;
    }
}

And your object is then:

class TheObject
{
    private final java.util.List<Point> points;

    public TheObject(List<Point> points)
    {
        this.points = points;
    }

    @Override
    public int hashCode()
    {
        int hash = 17;
        for (Point p : points)
        {
            hash = 31 * hash + p.hashCode();
        }
        return hash;
    }
}

Answer 3

Uhm, how about something along the lines of a binary search tree?

To put comparison in pseudocode:

position1 > position2 := 
   (position1.x > position2.x) || 
   ((position1.x == position2.x) && (position1.y > position2.y))

list1.x > list2.x := {
    for (i in 0...n) 
        if (list1[i] > list2[i]) return true;
        else if (list1[i] > list2[i]) return false;
    return false;
}

where n of course is the length of the lists.

I'm not much of a java-pro and I really don't know the standard library, but I suppose, you could just write the tree yourself. Implement a getID-method, that'll try to find this list or insert it otherwise and along with it a unique id, which you can obtain by simply incrementing a counter.

That way, you get an ID (instead of a hash), that has no collisions, whatsoever. In worst case comparing 2 lists is O(n), thus a find/insert is O(n) * O(log(m)) (supposing the tree is balanced) where m is the overall number of all lists.

Determining an ID is thus more expensive than hashing, in worst case, but as said, the result is guaranteed to be unique.

I can say little about average, since you give no numbers. Actually I am surprised you do not want to make a direct comparison, since I'd expect the probability for 2 positions to be equal is less than 1%, thus a list comparison is about O(1), since the probability that you need to compare 5 entries is really small.

Also, it is not clear, whether the lists are mutable or not, since if they are immutable, the cost should be of little importance.