通过它们的哈希值来比较长字符串 [英] Comparing long strings by their hashes

问题描述

试图提高比较字符串的函数的性能我决定通过比较它们的哈希值来比较它们。
所以有一个保证，如果2个非常长的字符串的哈希是相等的，那么字符串也是彼此相等？

Trying to improve the performance of a function that compares strings I decided to compare them by comparing their hashes. So is there a guarantee if the hash of 2 very long strings are equal to each other then the strings are also equal to each other?

推荐答案

虽然它保证2个相同的字符串将给你相等的哈希，反之亦然不是真的：对于给定的哈希，总是有几个可能的字符串产生相同的哈希。
由于 PigeonHole原则，这是真的。

While it's guaranteed that 2 identical strings will give you equal hashes, the other way round is not true : for a given hash, there are always several possible strings which produce the same hash. This is true due to the PigeonHole principle.

也就是说，产生相同散列的2个不同字符串的机会可以做成无穷小，到被认为等同于null。

That being said, the chances of 2 different strings producing the same hash can be made infinitesimal, to the point of being considered equivalent to null.

一个相当古典的例子的此类哈希是 MD5 ，具有接近完美的128位分配。这意味着你有一个机会在2 ^ 128两个不同的字符串产生相同的哈希。好吧，基本上，几乎一样不可能。

A fairly classical example of such hash is MD5, which has a near perfect 128 bits distribution. Which means that you have one chance in 2^128 that 2 different strings produce the same hash. Well, basically, almost the same as impossible.

这篇关于通过它们的哈希值来比较长字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！