Good hash function for list of 2-d positions?

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?

the point of choosing 31 as your prime is being able to multiply using a bit shift and a subtract.

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 = ((hash + x) << 5) - (hash + x);
        hash = ((hash + y) << 5) - (hash + y);
        return hash;
    }
}

The point of choosing 31 as your prime is being able to multiply using a bit shift and a single subtract operation. Note that bitshifting by 5 is equivalent to multiplying by 32, and the subtraction makes this equivalent to multiplying by 31. These two operations are much more effecient than a single, true multiplication.

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;int tmp = 0;
        for (Point p : points)
        {
            tmp = (hash + p.hashCode());
            hash = (tmp << 5) - tmp;
        }
        return hash;
    }
}

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.

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.