代码之家 › 专栏 › 技术社区 › AndreasT

从整数坐标对提供唯一uint的哈希函数

hashtable hash

AndreasT · 技术社区 · 15 年前

我有一个很大的2d点空间,稀疏地填充着点。把它想象成一块白色的大画布,上面点缀着黑点。画布(点空间)可能很大,接近极限在设置点之前,int的值及其大小未知。

理想的: 我需要一个取2D点的散列函数,返回唯一的uint32。这样就不会发生碰撞。 你可以假设画布上的点很容易被uint32计数。

事先不可能知道画布的大小 (甚至可能发生变化), 比如

画布宽度*y+x

我也试了一个很幼稚的方法

妥协: 非常碰撞概率低。

有什么想法吗?谢谢你的帮助。

安德烈亚斯T。

编辑: 我必须改变问题文本中的某些内容: 使用uint32“输入”,uint32可以计算画布上的点(或要存储的坐标对的数量)。我最初的问题没有多大意义,因为我会有一个sqrt(max(uint32))xsqrt(max(uint32))大小的画布,它是唯一可表示的通过16位移位和或。

11 回复 | 直到 15 年前

Pete Kirkham 12 年前

康托氏 enumeration of pairs

   n = ((x + y)*(x + y + 1)/2) + y

可能很有趣,因为它最接近原始画布宽度*y+x,但适用于任何x或y。但对于真实世界的int32哈希,而不是整数对到整数的映射,您可能最好使用一些操作,比如Bob Jenkin的操作 mix 用x,y和盐来称呼它。

Antti Huima 15 年前

代替使用散列函数,可以考虑使用二进制空间分区树(BSP)或XY树(密切相关)。

如果要将两个uint32散列为一个uint32,请不要使用Y&0xFFFF,因为它会丢弃一半的位。做点像

(x * 0x1f1f1f1f) ^ y

Jason Cohen 15 年前

与Emil类似,但在中处理16位溢出 x

hash = ( y << 16 ) ^ x;

user9876 15 年前

你的“理想”是不可能的。

您需要一个映射(x,y)->其中x、y和i都是32位量,保证不会生成重复的i值。

原因如下:假设有一个函数hash(),hash(x,y)给出不同的整数值。x有2^32(约40亿)个值,y有2^32个值。所以散列(x,y)有2^64(约1600万万亿)个可能的结果。但是32位整数中只有2^32个可能值,因此hash()的结果不适合32位整数。

http://en.wikipedia.org/wiki/Counting_argument

通常,您应该始终设计数据结构来处理冲突。(除非您的散列非常长(至少128位),非常好(使用加密散列函数),并且您感到幸运)。

rjobidon 7 年前

可以递归地将XY平面划分为单元,然后将这些单元划分为子单元,等等。

Gustavo Niemeyer在2008年发明了他的地理哈希地理编码系统。

亚马逊的开源计算任意经纬度坐标的哈希值。生成的Geohash值是一个63位的数字。碰撞的概率取决于散列的分辨率:如果两个对象比固有分辨率更接近,则计算的散列将是相同的。

Emil H 15 年前

可能

hash = ((y & 0xFFFF) << 16) | (x & 0xFFFF);

只要x和y可以存储为16位整数就可以工作。不过,不知道这会导致多少大整数冲突。一个想法可能是仍然使用该方案,但将其与压缩方案相结合,例如取2^16的模数。

Bob Jenkins 14 年前

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

Community CDub 7 年前

a >= b ? a * a + a + b : a + b * b

taken from here .

这适用于正平面中的点。如果坐标也可以在负轴上,则必须执行以下操作:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

但将输出限制为 uint

public uint GetHashCode(whatever a, whatever b)
{
    if (a > ushort.MaxValue || b > ushort.MaxValue || 
        a < ushort.MinValue || b < ushort.MinValue)
    {    
        throw new ArgumentOutOfRangeException();
    }

    return (uint)(a * short.MaxValue + b); //very good space/speed efficiency
    //or whatever your function is.
}

如果您希望严格控制输出 无符号整型 未经检查 . 埃米尔的解决方案很好,用C#:

return unchecked((uint)((a & 0xffff) << 16 | (b & 0xffff)));

Mapping two integers to one, in a unique and deterministic way 因为有太多的选择。。

Emre Sahin 10 年前

根据您的用例,可能会使用 Quadtree 并用分支名称字符串替换点。它实际上是点的稀疏表示,需要一个自定义四叉树结构,当您从画布上添加点时,该结构通过添加分支来扩展画布,但它避免了冲突,并且您将获得快速最近邻搜索等好处。

underscore 12 年前

您可以使用内置的散列值作为构建块,并将“散列风格”添加到混合中。比如:

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

public override int GetHashCode() {
   return ( Y.GetHashCode() << 16 ) ^ X.GetHashCode();
}

}

lkreinitz 11 年前

斐波那契散列对于整数对非常有效

乘法器0x9E3779B9

其他字号1/phi=(sqrt(5)-1)/2*2^w四舍五入到奇数

这将为紧密配对提供非常不同的值

我不知道所有配对的结果