对于均匀分布的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个值.