8

拥有 3D 统一网格，为了在大型模型中节省内存，不需要保存空单元格（不与任何对象重叠的单元格）。为此，我在 c# 中使用字典。尽管性能已经下降，但这仍然比创建 3D 网格时出现异常要好。现在我的问题是找到一个快速散列函数，将网格的 3d 整数坐标映射到唯一数字。

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

4

2 回答 2

5

一方面，您将目标写为“节省内存”，而另一方面您要求“将网格的 3d 整数坐标映射到唯一数字的快速哈希函数”。这两个不是很兼容。

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

或者——这更有可能——你只希望哈希冲突很少发生。然后你可以有一个哈希映射，它大约是实际存储对象数量的两倍。但在这种情况下，您不必完全避免哈希冲突，您只需使它们足够罕见。

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

如果有疑问，您可以随时进行测试：给定三个素数（例如哈希 137x+149y+163z）和一些实际设置（即使用的坐标和生成的哈希图大小），您可以简单地将哈希应用于所有坐标，修改为哈希图大小并计算唯一值的数量。对各种三元组做同样的事情，然后选择一个使这个数字最大化的。但我怀疑这种优化水平是否真的值得付出努力。

于 2014-09-05T09:48:38.450 回答
3

与其尝试就已经很好地涵盖的主题写一篇新文章，不如查看关于散列函数的维基百科文章。特别是第一张图片清楚地显示了多个输入如何散列到相同的值。

基本上，您的三元组被散列到 [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。

哈希的力量（以及平均情况为 O(1) 的原因）通过注意为了从哈希表（例如 (1,1,1)）中检索输入值而发生以下步骤而变得清晰。

  1. 计算并应用输入值的哈希hash = hash % n，因此 (1,1,1) -> 2。
  2. 执行直接 O(1) 查找，即hash_function[2] = (1,1,1) + additional data stored with this particular input value.
  3. 完毕！

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

当关系变成一对一的函数（双射）时，就会出现完美的散列。这提供了最佳性能，但很少见。正如我之前所说，幸运的是，在重复项很少的情况下，很容易生成几乎完美的哈希。本质上使您的哈希函数尽可能随机。

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

这也回答了这个问题。请注意，素数可以是任何素数，但在实践中通常使用较小的值，例如 31,37 等。

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

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

于 2014-09-05T08:08:17.307 回答