使用散列檢查字符串匹配，而無需再次檢查整個字符串

Question

我試圖檢查兩個字符串是否儘可能相同。我是否可以保護自己免受散列衝突的影響，而無需比較整個字符串？

我有一個由字符串鍵入的項目緩存。我存儲了字符串的散列，字符串的長度和字符串本身。 （我目前使用djb2來生成哈希。）

要檢查輸入字符串是否與緩存中的項目匹配，我計算輸入的哈希，並將其與存儲的哈希進行比較。如果匹配，我將輸入的長度（作爲散列計算的副作用）與存儲的長度進行比較。最後，如果匹配，我會對輸入和存儲的字符串進行完整的字符串比較。

是否有必要做全字符串比較？例如，是否有一個字符串散列算法，可以在數學上保證沒有兩個字符串具有相同長度會生成相同的散列？如果不是，如果前N個字符中的任何字符不同，算法是否可以保證兩個相同長度的不同字符串會生成不同的哈希碼？

基本上，當琴絃不同，但比當他們比賽將是在什麼我現在做的改善O（n）性能更好，提供了O（1）性能的任何字符串比較方案。

Answer 1

例如，有一個字符串哈希算法，可以在數學上保證相同長度的沒有兩個字符串會產生相同的哈希？

不，不可能有。考慮一下：散列的長度是有限的，但字符串沒有。出於參數的緣故，散列值是32位。你能創建超過20億個具有相同長度的唯一字符串嗎？當然，你可以 - 你可以創建無限數量的唯一字符串，因此比較哈希並不足以保證唯一性。這個論點縮放到更長的哈希。

如果不是，算法可以保證兩個不同的相同長度的字符串會產生不同的哈希碼，如果前N個字符中的任何一個不同？

嗯，是的，只要散列中的位數與字符串中的位數一樣多，但這可能不是您尋找的答案。

一些用於循環冗餘校驗算法具有擔保一樣，如果有完全一個有點不同，那麼CRC是保證在位的一定運行長度不同，但只適用於相對較短的運行。

Answer 2

如果您使用現代散列函數（如Secure Hash Algorithm (SHA)變體之一），則應該避免碰撞。