二维位置列表的良好哈希函数？

Question

我有一系列对象,其唯一不同的内部状态是2-d位置(2个整数)的固定长度列表(或其他).也就是说,它们都具有相同数量的元素,具有(可能)不同的2-d值.

我将不断地将新实例与之前存在的所有实例进行比较,因此我编写一个良好的散列函数以最大限度地减少比较次数非常重要.

你会怎么推荐我哈希呢？

Answer 1

选择31作为素数的要点是能够使用位移和减法相乘.

让我们说这是一个Point类:

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;
    }
}

选择31作为素数的要点是能够使用位移和单个减法运算相乘.请注意,5位移位相当于乘以32,减法使得这相当于乘以31.这两个运算比单个真正的乘法更有效.

然后你的对象是:

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;
    }
}