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

Question

我正在寻找为一组二维点计算哈希码的最佳方法(这样我就可以在哈希表中存储多边形).

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

在速度/碰撞频谱的另一端,我还可以例如总结所有坐标,这将导致非常快的代码,但也会产生大量的碰撞.

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

如果坐标是整数(对比实际坐标),最佳解是不同的吗？

编辑:我正在使用.net,因此哈希码应该是32位长.

Answer 1

这项工作没有最佳方式.这一切都取决于你能承受多大的哈希值.你必须在速度和扩散之间进行传统.请记住,没有最佳解决方案(如果你不确切知道你要干什么)在某些情况下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 */

你说聚合点在一起就是放慢速度.如果你修复上面的代码它不需要任何类型的agregation只是通过trought(没有多少不同的总和)如果你使用integeres和浮动你可能会修复shift(<<和>>是移位操作,它们一起工作就像按位旋转)以适合您的数据类型.

在这里检查其他哈希函数:http: //www.partow.net/programming/hashfunctions/