hash - 使用哈希检查字符串匹配，而不是仔细检查整个字符串

Question

我正在尝试尽快检查两个字符串是否相同。我可以在不比较整个字符串的情况下保护自己免受哈希冲突吗？

我有一个由字符串键入的项目缓存。我存储字符串的哈希值、字符串的长度和字符串本身。（我目前正在使用djb2来生成哈希。）

为了检查输入字符串是否与缓存中的项目匹配，我计算输入的哈希值，并将其与存储的哈希值进行比较。如果匹配，我将输入的长度（作为计算哈希的副作用得到）与存储的长度进行比较。最后，如果匹配，我会对输入和存储的字符串进行完整的字符串比较。

是否有必要进行完整的字符串比较？例如，是否有一种字符串散列算法可以在数学上保证没有两个相同长度的字符串会生成相同的散列？如果不是，如果前 N 个字符中的任何一个不同，算法是否可以保证两个相同长度的不同字符串将生成不同的哈希码？

基本上，任何在字符串不同时提供 O(1) 性能但在匹配时优于 O(n) 性能的字符串比较方案将比我现在所做的有所改进。

Answer 1

如果您使用现代散列函数（例如安全散列算法 (SHA)变体之一），您应该可以避免冲突。

Answer 2

例如，是否有一种字符串散列算法可以在数学上保证没有两个相同长度的字符串会生成相同的散列？

不，也不可能。想一想：散列的长度是有限的，但字符串没有。为了论证的缘故，说散列是 32 位的。你能创建超过 20 亿个长度相同的唯一字符串吗？当然可以——您可以创建无限数量的唯一字符串，因此比较哈希值不足以保证唯一性。这个论点扩展到更长的哈希值。

如果不是，如果前 N 个字符中的任何一个不同，算法是否可以保证两个相同长度的不同字符串将生成不同的哈希码？

嗯，是的，只要哈希中的位数与字符串中的位数一样多，但这可能不是您要寻找的答案。

用于循环冗余检查的一些算法具有保证，例如如果恰好有一个位不同，那么 CRC 保证在一定的位运行长度上是不同的，但这仅适用于相对较短的运行。