hash - 如何评估哈希生成算法

Question

除了生成大量值并查看值的分布之外，您还知道哪些方法可以评估哈希函数的效率？效率是指散列函数生成的密钥分布均匀。有没有办法在不实际测试实际值的情况下证明这一点？

Answer 1

散列函数甚至仅在被散列的数据的上下文中

考虑两个数据集：

设置 1

1, 3, 6, 2, 7, 9, 5, 8, 4

设置 2

65355, 96424664, 86463624, 133, 643564,  24232, 88677, 865747, 2224

一个集合的良好散列函数（即集合 1 的 mod 10）不会产生冲突，并且可以被视为该数据集的完美散列

但是将其应用于第二组，到处都有碰撞

Hash = (x * 37) mod 256

第二组要好得多，但可能不太适合第一组……尤其是在为少量桶划分散列时。

您可以做的是针对您“期望”您的函数必须处理的随机数据评估散列......但这是在做出假设......

过早的优化是在你有足够的真实数据来评估之前寻找完美的哈希函数。

您应该在重新散列的成本变得无法更改散列函数之前获得足够的数据

更新

假设我们正在寻找一个生成输入数据的 8 位散列的散列函数。让我们进一步假设散列函数应该采用不同长度的字节流。

如果我们假设字节流中的字节是均匀分布的，我们可以对不同的散列函数进行一些评估。

int hash = 0;
for (byte b in datastream) hash = hash xor b;

该函数将为指定的数据集生成均匀分布的散列值，因此在这种情况下将是一个很好的散列函数。如果您不明白为什么会这样，那么您可能还有其他问题。

int hash = 37;
for (byte b in datastream hash = (31 * hash + b) mod 256;

该函数将为指定的数据集生成均匀分布的散列值，因此在这种情况下将是一个很好的散列函数。

现在让我们将数据集从 0 到 255 范围内的可变长度随机数字符串更改为包含编码为 US-ASCII 的英文句子的可变长度字符串。

然后 XOR 是一个糟糕的哈希，因为输入数据从来没有设置第 8 位，因此只生成 0-127 范围内的哈希，而且由于英文中的字母频率，一些“热”值的可能性更高单词和 XOR 的取消效果。

这对素数作为散列函数仍然相当不错，因为它使用整个输出范围，并且素数初始偏移量加上不同的素数乘数往往会分散值。但是由于英语语言的结构，碰撞仍然很弱......只有使用真实数据进行测试才能显示的东西。