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

Question

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

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 的抵消效果。

这对素数作为哈希函数仍然相当不错，因为它使用完整的输出范围，并且素数初始偏移加上不同的素数乘法器往往会将值分散开。但由于英语的结构，它的冲突能力仍然很弱......只有用真实数据进行测试才能显示这一点。