hash - 我应该读取多少个字符串字符才能获得良好的哈希？

Question

这里有一个小难题：如果您使用像 CRC-64 这样的哈希算法，那么需要读取字符串中的多少字节才能计算出一个好的哈希？假设您所有的字符串至少有 2 KB 长，那么使用整个字符串来计算缓存似乎是一种浪费或资源，但是您认为多少个字符就足够了？因为它等于 64 位，所以只有 8 个 ASCII 字符就足够了吗？使用超过 8 个 ASCII 字符不会毫无意义吗？我想知道你对此的看法。

更新：对于“良好的哈希”，我的意思是通过使用更多字节来计算哈希冲突的可能性不会减少。

Answer 1

如果您使用 CRC-64 超过 8 个字节或更少，那么使用 CRC-64 没有意义：只需“按原样”使用 8 个字节。除非输入比预期输出长，否则 CRC 没有任何附加值。

作为一般规则，如果您的哈希函数具有n位的输出，那么一旦您累积了大约 2 ^{n /2 个}字符串，就会开始出现冲突。简而言之，如果您使用 64 位，那么您在前 20 亿个字符串中遇到冲突的可能性很小。如果您获得 160 位或更多的输出，那么冲突几乎是不可行的（与 CPU 着火等硬件故障相比，您遇到的冲突要少得多）。这假设哈希函数是“完美的”。如果您的散列函数从选择几个数据字节开始，那么必然是您没有选择的字节select 不会对散列输出产生任何影响，因此您最好使用“好”字节——这完全取决于您要散列的字符串类型。这里没有一般规则。

我的建议是首先尝试在整个字符串上使用通用哈希函数；我通常推荐MD4。MD4 是一个密码散列函数，已经被彻底破解了，但是对于一个不涉及安全的问题，它仍然非常擅长混合数据元素（从密码学上讲，CRC 比 MD4 坏得多）。据报道，MD4 在某些平台上实际上比 CRC-32 更快，因此您可以试一试。在一台基本的 PC（我的 2.4 GHz Core2）上，MD4 实现以大约 700 MBytes/s 的速度工作，所以我们说的是每秒 35000 个散列的 2 kB 字符串，这还不错。

Answer 2

两个不同字符串的前 8 个字母相同的可能性有多大？根据这些字符串是什么，它可能非常高，在这种情况下，您肯定会遇到哈希冲突。

哈希整个事情。几千字节不算什么。除非您实际上需要在程序中节省纳秒，否则不散列完整的字符串将是过早的优化。