三维整数坐标的哈希函数

Question

拥有一个3D均匀网格，在大型模型中为了节省内存不需要保存空单元格（不与任何对象重叠的单元格）。我正在使用C#中的字典来实现这个目的。虽然性能已经降低，但这仍然比在创建3D网格时出现异常要好。现在我的问题是找到一个快速的哈希函数，将网格的3D整数坐标映射到唯一的数字。

我已经尝试过((x * 73856093 + y * 19349669 + z * 83492791))% n，它并不总是生成唯一的数字。

- ali

---

如果数字可以是任意大小，那么你可以使用 x * MAXINT * MAXINT + y * MAXINT + z。如果数字必须与整数相同大小，则由于鸽笼原理，唯一性是不可能的。有2^32个可能的整数值和2^96个可能的整数三元组值。你不能将后者放入前者而不重叠。 - Kevin

x、y和z坐标的可能值是什么？ - President James K. Polk

哈希值根本不需要是唯一的。当两个不同的输入值具有相同的哈希值时，就会发生冲突。你只需要尽量减少冲突（以提高性能），这通常很容易实现，例如 hash = (x * 31) + (y * 37) + (z * 41) 就足够了。 - Floris

一个更好的哈希函数（在您的情况下没有冲突）可以是 hash = (x * 18397) + (y * 20483) + (z * 29303)，假设您的哈希值可以高达2^48。 - Floris

@Floris：避免碰撞仅在哈希映射本身具有相同大小，即2 ^ 48的情况下才有帮助。否则，在其中某个地方有一个模数步骤，因此您只推迟了碰撞。hash = x * 16777216 + y * 4096 + z也可以避免碰撞，仅使用36位（每个坐标为12位）。它可以使用位移来实现。但是，如果将其缩小为某个较小的二次幂，则性能会非常差，这在实际哈希映射中可能发生。 - MvG

Answer 1

一方面，您将目标写为“节省内存”，而另一方面，您要求“快速哈希函数将网格的三维整数坐标映射到唯一的数字”。这两者并不非常兼容。

要么您想要保证O(1)访问。在这种情况下，您必须防止哈希冲突，并且必须将输入映射到唯一的数字。但在这种情况下，您需要与可能的输入一样多的哈希图中的单元格。因此，与简单的N×N×N数组相比，您不会节省内存。

要么-这更有可能-您只希望哈希冲突很少发生。然后，您可以拥有大约两倍于实际存储对象数量的哈希图。但在这种情况下，您不必完全避免哈希冲突，您只需要使它们足够稀少即可。

选择一个好的哈希函数很大程度上取决于输入数据的可能模式。如果输入相当随机，并且知道哈希图的大小，则应该以均匀分布为目标。如果对象更可能位于相邻块中，则要确保坐标的小变化不太可能导致冲突。这是有用的地方，因为不要将因子设置为素数，因此在一个方向上的小变化不太可能与另一个方向上的变化相撞。

如果有疑问，您可以随时进行测试：给定三个素数（例如哈希137x+149y+163z）和一些真实世界的设置（即使用的坐标和结果哈希图大小），您可以将哈希应用于所有坐标，将其模减到哈希图大小，并计算唯一值的数量。对于各种三元组重复此过程，并选择最大化该数字的那个。但我怀疑这种优化水平是否真的值得努力。

- MvG

---

您希望确保坐标的微小变化不太可能导致碰撞发生。我认为只有当x、y、z坐标具有精度时才成立。 - ali

@ali：根据你的问题，我假设是整数。 - MvG

Answer 2

不要试图在一个已经被广泛报道的主题上写一篇新文章，请参阅wikipedia关于哈希函数的文章。特别是第一张图片清楚地显示了如何将多个输入散列到相同的值。基本上，您的三元组将被散列到范围为[0，2 ^ 64-1]（允许重复）的某些哈希值中。然后通过方程式hash = hash％n将该范围缩小到略大于您的输入值的数量（例如n = 5）。对于输入值[(1,1,1),(1,2,3),(2321,322,232),(3,3,3)]，得到的关系将看起来像这样：

    (1,1,1)          -> 2
    (1,2,3)          -> 0
    (2321, 322, 232) -> 0
    (3,3,3)          -> 3

正如您所看到的，没有任何输入值与1或4相关联（即哈希），而有两个输入值哈希为0。

通过注意到从哈希表中检索输入值（例如（1,1,1））需要执行以下步骤，可以清楚地看出哈希的强大之处（以及平均情况为O（1）的原因）。

1. 计算输入值的哈希并应用hash = hash％n，因此（1,1,1）-> 2。
2. 执行直接的O（1）查找，即hash_function [2] =（1,1,1）+存储在此特定输入值中的其他数据。
3. 完成！

在多个输入值映射到相同的哈希值（在我们的示例中为0）的情况下，内部算法需要对这些输入值进行搜索，通常使用红黑树进行搜索（最坏情况为O（log n））。任何查找的最坏情况也是O（log n）。

完美的哈希发生在关系变成一对一到函数（双射）时。这会提供最佳性能，但很少见。正如我之前所说，幸运的是，几乎完美的哈希很容易产生，其中重复很少。实质上，使您的哈希函数尽可能随机。

我在评论中给出的示例可能足够（也是错误的方法：），但更标准的计算方式是：hash = ((((prime1 + value1) * prime2) + value2) * prime3) + value3) * prime4

这也回答了问题。请注意，素数可以是任何素数，但通常使用31、37等较小的值。

在实践中，测试可用于检查性能，但通常不必要。

无论如何，重新阅读您的问题，我想知道为什么您不放弃整个哈希思想，而只是将点存储在简单的数组中？

- Floris

---

你能否列举一种使用红黑树进行碰撞处理的实现？Mono不支持这种功能。此外，完美哈希必须是单射的，但不一定是满射的：它并不要求哈希结果范围中的每个元素都有可能的输入。 - MvG

你是对的 - 当我提到红黑树时，我是凭记忆说的。此外，我将范围视为哈希函数的图像（这在数学中很常见），但在这种情况下没有意义。 - Floris

在大范围内使用大型模型时，由于小单元尺寸而耗尽内存以创建网格的某些单元。而类似字典的集合则提供了仅存储与三角形重叠的单元的机会。 - ali