math - 3d 整数坐标的哈希函数

Question

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

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

Answer 1

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

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

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

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

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