我试着尽快检查两个字符串是否完全相同。我可以在不比较整个字符串的情况下保护自己免受哈希冲突的影响吗?
我有一个由字符串键控制的项的缓存。我存储字符串的散列、字符串的长度以及字符串本身。(我目前正在使用djb2来生成哈希。)
为了检查输入字符串是否与缓存中的项匹配,我计算输入的散列,并将其与存储的哈希进行比较。如果匹配,我将输入的长度(作为计算哈希的副作用)与存储的长度进行比较。最后,如果匹配,我将对输入和存储的字符串做一个完整的字符串比较。
有必要进行全字符串比较吗?例如,是否有一个字符串散列算法可以从数学上保证没有两个长度相同的字符串会产生相同的散列?如果不是,如果第一个N个字符中的任何一个不同,算法能否保证两个长度相同的不同字符串生成不同的哈希码?
基本上,在字符串不同时提供O(1)性能的任何字符串比较方案,在它们匹配时都会比O(n)性能好,这将是对我现在所做的工作的改进。
发布于 2010-11-08 19:30:00
例如,是否有一个字符串散列算法可以从数学上保证没有两个长度相同的字符串会产生相同的散列?
不,不可能。想想看:散列有一个有限的长度,但是字符串没有。为了论证起见,可以说哈希是32位。您能创建超过20亿个相同长度的唯一字符串吗?当然,您可以-您可以创建无限数量的唯一字符串,所以比较散列不足以保证唯一性。这个论点的范围是较长的哈希。
如果不是,如果第一个N个字符中的任何一个不同,算法能否保证两个长度相同的不同字符串生成不同的哈希码?
是的,只要哈希中的位数和字符串中的位数一样大,但这可能不是您想要的答案。
一些用于循环冗余检查的算法有保证,例如,如果有一点不同,则保证在特定的位长上CRC是不同的,但这只适用于相对较短的运行。
发布于 2010-11-08 19:06:26
如果使用现代哈希函数(如安全哈希算法(SHA)变体之一),则应该避免碰撞。
https://stackoverflow.com/questions/4127005
复制相似问题