二维位置列表的哈希函数是否良好?

选择31作为素数的关键是能够用移位和减法进行乘法。

假设这是一个点类:

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

嗯,沿着二进制搜索树的路线怎么样?

要在伪代码中进行比较,请执行以下操作:

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

在哪里? n 当然是列表的长度。

我不是一个JavaPro,我真的不知道标准库,但我想,你可以自己写这棵树。实现一个getid方法,该方法将尝试查找此列表或将其插入其他列表,并与一个唯一的ID一起使用,只需增加一个计数器即可获得该ID。

这样,您就得到了一个没有冲突的ID(而不是哈希)。在最坏的情况下,比较两个列表是 O(n) ,因此查找/插入是 O(n) * O(log(m)) (假设树是平衡的)其中 m 是所有列表的总数。

因此,在最坏的情况下,确定一个ID比散列更昂贵,但是如前所述,结果保证是唯一的。

我几乎不能说平均值,因为你没有给出数字。实际上,我很惊讶你不想直接比较,因为我希望两个位置相等的概率小于1%,所以列表比较大约是0(1),因为需要比较5个条目的概率非常小。

此外,还不清楚列表是否可变,因为如果它们是不可变的,那么成本就不太重要。

根据整数的大小,你可能想把第一个坐标乘以最大可能坐标,再加上第二个。例如,如果x和y为正数,并且限制为256,则可以尝试x*256+y作为散列函数。如果x和y也可以是负的,您可能希望先将它们抵消,使它们成为非负的。此外,如果x乘以max溢出整数,则可能需要一个多int散列值,或者mod或bitwise,结果为uint_max。