algorithm - 对于均匀分布的 4 位值的非均匀序列的良好哈希函数？

Question

我有一个非常具体的问题:

我在 15x50 网格上分布了均匀的随机值，我想要散列的样本对应于以任何可能的网格位置为中心的 5x5 单元格正方形。

因此，样本数量可以从 25(远离边界，大多数情况)到 20、15(靠近边界)到最少 9(在角落)不等。

因此，即使单元格值是随机的，位置也会在序列长度中引入确定性变化。

哈希表大小是一个很小的数字，通常在 50 到 20 之间。

该函数将在大量随机生成的网格(数百/数千)上运行，并且每个网格可能被调用数千次。网格上的位置可以认为是随机的。

我想要一个可以尽可能均匀地分布 15x50 可能样本的函数。

我试过以下伪代码:

int32 hash = 0;
int i = 0; // I guess i could take any initial value and even be left uninitialized, but fixing one makes the function deterministic
foreach (value in block)
{
    hash ^= (value << (i%28))
    i++
}
hash %= table_size

但结果虽然没有严重失衡，但对我来说似乎并不顺利。也许是因为样本太小了，但这种情况使得很难在更大的样本上运行代码，如果一些精通计算机的人已经为我准备好了答案，我宁愿不必编写完整的测试工具 :).

我不确定将值两两配对并使用通用字节哈希策略是否是最佳解决方案，尤其是因为值的数量可能是奇数。

我不得不使用第 17 个值来表示离网单元格，但这似乎引入了偏差(来自边界附近单元格的序列将有很多“离网”值)。

我也不确定什么是测试各种解决方案效率的最佳方法(例如，我应该生成多少个网格才能了解性能)。

Answer 1

http://www.partow.net/programming/hashfunctions/

这里有一些来自各个领域专家的不同哈希函数。函数专为 8 位值而设计，但我相信您可以针对您的情况进行扩展。我不知道该提出什么建议，但我认为它们中的任何一个都应该比您当前的想法更有效。

您提出的当前方法的问题是，字段 2^n 中的值是循环的，例如，如果您在末尾进行 mod 64，您将丢失大部分值，最终结果中只保留最后 3 个值。