9

我正在寻找为一组二维点计算哈希码的最佳方法（以便我可以将多边形存储在哈希表中）。

有一些明显的方法可以做到这一点，例如连接字符串中的所有点坐标及其哈希码，但这会非常慢。

在速度/碰撞谱的另一端，例如，我还可以总结所有坐标，这会产生非常快的代码，但也会产生很多碰撞。

为一组点计算哈希码的最佳方法是什么？

如果坐标是整数（与实际坐标相比），最优解是否不同？

编辑：我使用的是 .net，所以哈希码应该是 32 位长。

4

7 回答 7

13

这项工作没有最佳方法。这完全取决于你能承受多大的哈希值。你必须在速度和扩散之间进行权衡。请记住，没有最佳解决方案（如果您不完全知道要散列的内容）在某些情况下 xor 就足够了。

以这段代码为例

unsigned int JSHash(char* str, unsigned int len)
{
    unsigned int hash = 1315423911;
    unsigned int i    = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash ^= ((hash << 5) + (*str) + (hash >> 2));
    }

    return hash;
}
/* End Of JS Hash Function */

你说聚合点在一起很慢。如果你修复了上面的代码，它不需要任何类型的聚合，只需传递 trought（与总和没有太大不同）如果你使用整数和浮点数，你可能会修复移位（<< 和 >> 是移位操作，它们一起工作就像按位旋转）以适合您的数据类型。

在此处检查其他哈希函数：http: //www.partow.net/programming/hashfunctions/

于 2009-08-16T14:06:34.933 回答
1

最佳取决于您对哈希计算的要求。

性能将以更多哈希冲突为代价。

你对任何一个都有严格的限制吗？这将归结为一个数学分析，即每个百分比的哈希冲突会在性能方面花费多少。

于 2009-08-16T13:51:24.177 回答
1

如果您的数据集可能是具有共同边但不重叠的多边形之一，则您只需对每个多边形中的三个点进行散列以避免冲突。

编辑：重新考虑这一点，想象与凹/凸边界可能发生的碰撞，你的多边形重叠也是如此。- 叹息

唉：当凸凹相遇时，总是让我陷入困境。:-P

于 2009-08-16T14:34:01.193 回答
0

看看这篇论文

拉姆丹和沃尔夫森。几何散列：一种通用且高效的基于模型的识别方案。计算机视觉。(1988)

于 2009-08-16T22:58:04.843 回答
0

或者，您可以对各个点的哈希值进行异或运算。

return p1.GetHashCode() ^ p2.GetHashCode()

无论如何，这取决于值将是什么。可能可以添加它们。

于 2009-08-16T22:59:57.023 回答
0

如果您希望顺时针和逆时针定义但其他方面相等的多边形相等，那么您必须创建一个规范化函数。给定多边形点的函数从任何点开始并以任何顺序返回这些点的顺序相同。

我能想到的一种算法是找到所有可能的点序列中的最小值：

  1. 找到最左上角点的集合（最小 x 的点和最小 y 的点），这些是起点。
  2. 对于每个起点和每个方向，在给定方向上迭代地添加连接点，并消除当前迭代中不是最左上角的所有点。当只剩下一个起点，方向对或完成n-1次迭代时停止。如果剩余多个起点和方向，请选择任何一个 - 它们都是同构的。
  3. 从找到的点开始沿找到的方向重新排序点。

对于完全退化的多边形，这是 O(n^2) 的最坏情况，但如果您的多边形没有重叠点，则这是 O(n)，具有非常小的常数因子。

使用规范化的顺序，您可以轻松地比较两个多边形是否相等，只需迭代比较点是否相等。哈希码计算也很简单，使用任何合理稳健的哈希组合方法。例如：

int result = 0;
foreach (var point in this.points) {
    result = (result * 31 + point.X.GetHashCode()) * 31 + point.Y.GetHashCode();
}
于 2009-08-17T18:32:21.450 回答
0

对于在顺时针/逆时针独立上具有所需属性的非常快速（计算）的散列，您不希望依赖于找到明确定义的点顺序。

这将您的哈希组合操作限制为通勤的操作。因此，我们希望在组合操作期间保持与方向无关的任何和所有数据分开。

这是一个简单的解决方案：

假设一个联合函数 int -> int -> int 是关联的，以下任何一个都可以开始：

public static int combine(int h, int x)
{
    return h * 31 + x;
} 

public static int combine(int h, int x)
{
    return h ^ x;
}

然后我们可以执行以下操作：

public override int GetHashCode()
{
    int x = 0;
    int y = 0;
    uint h = 0;    
    foreach (var point p in polgon)
    {
        x = combine(x, p.X);
        y = combine(y, p.Y);
        h++;
    }
    // simplified, unrolled Murmur2 hash for end stage
    const uint m = 0x5bd1e995;
    const int r = 24;
    uint h = count;
    uint k = ReinterpretInt32ToUInt32(x);
    k *= m;
    k ^= k >> r;
    k *= m;
    h *= m;
    h ^= k;
    k = ReinterpretInt32ToUInt32(y);
    k *= m;
    k ^= k >> r;
    k *= m;
    h *= m;
    h ^= k;
    // avalanche
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;
    return ReinterpretUInt32ToInt32(h);
}

依靠这个让上面的代码变得简单

public unsafe uint ReinterpretInt32ToUInt32(int i)
{
    return *((uint*) (void*) &i);
}

public unsafe int ReinterpretUInt32ToInt32(uint u)
{
    return *((int*) (void*) &u);
}

就避免碰撞而言，这不是最好的哈希，但计算起来应该非常快，您可能会发现它足以满足您的需求。

于 2009-08-20T00:19:35.730 回答