27

一般的问题： 我有一个很大的二维点空间，点点稀疏。把它想象成一块洒满黑点的白色大画布。我必须遍历并搜索这些点很多。Canvas（点空间）可以很大，接近 int 的限制，并且在其中设置点之前它的大小是未知的。

这让我想到了散列：

理想： 我需要一个采用 2D 点的散列函数，返回一个唯一的 uint32。这样就不会发生碰撞。您可以假设 Canvas 上的点数可以通过 uint32 轻松计算。

重要提示：不可能事先知道画布的大小（甚至可能会改变），所以像

画布宽度 * y + x

可悲的是，这是不可能的。

我也试过很幼稚

绝对（x）+绝对（y）

但这会产生太多的碰撞。

妥协： 一种散列函数，为键提供非常低的冲突概率。

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

最好的问候，安德烈亚斯 T。

编辑：我必须更改问题文本中的某些内容：我将假设“能够使用 uint32 计算画布的点数”更改为“能够计算画布上的点数（或要存储的坐标对数”） by uint32. 我最初的问题没有多大意义，因为我会有一个 sqrt(max(uint32))xsqrt(max(uint32)) 大小的画布，它可以通过 16 位移位和 OR 来唯一地表示。

我希望这没问题，因为所有答案对于更新的假设仍然最有意义

对此感到抱歉。

4

11 回答 11

36

康托对数的枚举 

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

可能很有趣，因为它最接近您原来的 canvaswidth * y + x 但适用于任何 x 或 y。但是对于现实世界的 int32 散列，而不是整数对到整数的映射，您可能最好进行一些操作，例如 Bob Jenkin 的混合并用 x,y 和盐调用它。

于 2009-03-25T17:28:43.970 回答
18

保证无冲突的哈希函数不是哈希函数:)

您可以考虑使用二进制空间分区树 (BSP) 或 XY 树（密切相关），而不是使用散列函数。

如果要将两个 uint32 散列到一个 uint32 中，请不要使用 Y & 0xFFFF 之类的东西，因为这会丢弃一半的位。做类似的事情

(x * 0x1f1f1f1f) ^ y

（您需要先转换其中一个变量以确保散列函数不可交换）

于 2009-03-25T16:57:00.553 回答
6

x与 Emil 类似，但以产生更少冲突的方式处理 16 位溢出，并且需要更少的指令来计算：

hash = ( y << 16 ) ^ x;
于 2009-03-25T16:56:12.410 回答
3

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

Gustavo Niemeyer 于 2008 年发明了他的 Geohash 地理编码系统。

亚马逊的开源地理库计算任何经纬度坐标的哈希值。生成的 Geohash 值为 63 位数字。冲突的概率取决于散列的分辨率：如果两个对象比固有分辨率更接近，则计算出的散列将是相同的。

在此处输入图像描述

阅读更多：

https://en.wikipedia.org/wiki/Geohash https://aws.amazon.com/fr/blogs/mobile/geo-library-for-amazon-dynamodb-part-1-table-structure/ https:// /github.com/awslabs/dynamodb-geo

于 2017-09-09T04:24:39.827 回答
2

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

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

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

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

通常，您应该始终设计数据结构来处理冲突。（除非您的哈希非常长（至少 128 位），非常好（使用加密哈希函数），并且您感觉很幸运）。

于 2009-03-25T18:38:02.073 回答
1

也许？

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

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

于 2009-03-25T16:53:33.477 回答
1

如果你能做到 = ((y & 0xffff) << 16) | (x & 0xffff) 然后您可以将可逆的 32 位混合应用于 a，例如 Thomas Wang 的

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

这样你就得到了一个看起来随机的结果，而不是一个维度的高位和另一个维度的低位。

于 2010-08-05T04:59:01.840 回答
1

你可以做

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

取自这里。

这适用于正平面上的点。如果您的坐标也可以在负轴上，那么您将不得不这样做：

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

如果您希望输出严格uint用于未知范围的输入，那么根据该范围会有合理数量的冲突。我建议的是有一个可以溢出但未经检查的功能。Emil 的解决方案很棒，在 C# 中：

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

请参阅将两个整数映射为一个，以独特且确定的方式获取大量选项。

于 2012-12-27T08:37:11.277 回答
1

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

于 2014-08-29T10:18:16.097 回答
0

如果您已经在使用所有对象（甚至像整数这样的原始对象）都已实现内置哈希函数的语言或平台（Java 平台语言，如 Java，.NET 平台语言，如 C#。以及其他如 Python、Ruby 等）。您可以使用内置的散列值作为构建块，并将您的“散列风味”添加到组合中。像：

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

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

}

并且还有像“预定义的百万点集”这样的测试用例针对不同方面的每个可能的哈希生成算法进行比较，比如计算时间、所需内存、键冲突计数和边缘情况（太大或太小值）可能很方便。

于 2012-11-04T08:18:05.997 回答
0

斐波那契散列非常适合整数对

乘数 0x9E3779B9

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

a1 + a2*乘数

这将为靠近的对提供非常不同的值

我不知道所有对的结果

于 2013-08-26T18:07:00.483 回答