string - 通过哈希值比较长字符串

Question

为了提高比较字符串的函数的性能，我决定通过比较它们的哈希值来比较它们。那么是否可以保证 2 个非常长的字符串的哈希值彼此相等，那么这些字符串也彼此相等？

Answer 1

虽然可以保证 2 个相同的字符串会给您相同的哈希值，但反之则不然：对于给定的哈希值，总会有几个可能的字符串产生相同的哈希值。由于PigeonHole 原理，这是正确的。

话虽如此，两个不同的字符串产生相同哈希的机会可以变得非常小，以至于被认为等同于 null。

这种散列的一个相当经典的例子是MD5，它具有近乎完美的 128 位分布。这意味着您在 2^128 中有一次机会 2 个不同的字符串产生相同的哈希值。嗯，基本上，几乎和不可能一样。

Answer 2

在比较两个长字符串以确定它们是否相同的简单常见情况下，出于两个原因，简单比较将比散列更可取。首先，正如@wildplasser 所指出的，哈希要求必须遍历两个字符串的所有字节才能计算两个哈希值，而简单比较速度很快，只需要遍历字节直到找到第一个差异，这可能远小于完整的字符串长度。其次，一个简单的比较可以保证检测到任何差异，而哈希只给出了它们相同的高概率，正如@AdamLiss 和@Cyan 所指出的那样。

然而，有几个有趣的情况可以使用哈希比较来获得很大的优势。正如@Cyan 所提到的，如果要进行多次比较，或者必须存储以供以后使用，那么散列可能会更快。其他人未提及的情况是字符串是否位于通过本地网络或 Internet 连接的不同机器上。在两台机器之间传递少量数据通常会快得多。最简单的第一个检查是比较两者的大小，如果不同，你就完成了。否则，计算散列，每个都在自己的机器上（假设你能够在远程机器上创建进程），如果不同，你就完成了。如果哈希值相同，并且您必须有绝对的确定性，那么就没有简单的捷径可以达到确定性。在两端使用无损压缩将允许传输较少的数据以进行比较。最后，如果这两个字符串按时间分隔，正如@Cyan 所暗示的那样，如果您想知道一个文件自昨天以来是否已更改，并且您已经存储了昨天版本的哈希，那么您可以将今天的哈希与它进行比较.

我希望这将有助于激发某人的一些“开箱即用”的想法。

Answer 3

我不确定，如果你的表现会有所改善。两者：构建哈希 + 比较整数和使用 equals 简单地比较字符串具有相同的复杂性，即 O(n)，其中 n 是字符数。