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

Question

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

我将不断地将新实例与所有以前存在的实例进行比较，因此编写一个好的哈希函数以最大程度地减少比较次数非常重要。

您建议我如何对它们进行哈希处理？

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