通过哈希比较长字符串

Question

试图改进比较字符串的函数的性能我决定通过比较它们的哈希值来比较它们.那么,如果2个非常长的字符串的散列彼此相等,那么字符串也相互相等吗？

Answer 1

虽然保证2个相同的字符串会给你相等的哈希值,但另一种方法却不是这样:对于给定的哈希值,总会有几个可能的字符串产生相同的哈希值.由于PigeonHole原则,这是事实.

话虽这么说,产生相同散列的2个不同字符串的机会可以是无穷小的,被认为等同于null.

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

Answer 2

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

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

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