關於忽略字符排序的字符串散列函數的建議

我需要在C++中使用unordered_map<string, int>的散列函數。我需要根據內容對密鑰進行散列處理，但不應取決於內容的順序。關於忽略字符排序的字符串散列函數的建議

例如，在我的地圖中，鍵是字符串，我需要「ac」，「ca」來生成相同的散列值，但「bb」應該生成不同的散列值。

我試着總結字符串的內容，但我意識到在這種情況下，「ac」和「bb」會生成相同的散列值。

還有類似的問題Does a string hash exist which can ignore the order of chars in this string，但那還沒有被回答。

來源

2015-03-08 Anoop

在對它們進行散列操作之前對它們進行排序。這意味着你對'ac'和'ca'都加上'ac'，這樣它們就可以根據需要哈希到相同的值，但'bb'（大概）會散列到不同的值。 – 2015-03-08 21:15:17

^他打算說「排序字符串中的字符」。 – 2015-03-08 21:20:20

是的。排序他們現在工作。但是如果有一個線性時間散列函數而沒有任何額外的內存來完成這個任務，那將會很棒 – Anoop 2015-03-08 21:23:46

由於a * b * c等同於a * c * b，所以可以將字符相乘而不是相加。

這應該比在對每個字符串中的所有字符進行散列操作之前快很多。

來源

2015-03-08 21:21:48

我認爲這在所有情況下都不起作用。例如，如果ascii值從0開始，那麼cc => 9也是l => 9。雖然這可能並非如此，但我猜可能會發生碰撞。這將是很好，如果我能以某種方式避免碰撞。我這樣說是因爲我知道在我的要求中字符串長度限制在50左右。對不起，沒有添加此信息的問題。 – Anoop 2015-03-08 21:26:29

@Anoop：任何散列函數都可能發生衝突;這是他們的觀點。答案中提出的概念幾乎可以肯定你使用原始的ASCII值（所以'a' => 97，'b' => 98，'c' => 99等），但你仍然可能遇到問題截然不同的字符串結束生產相同的產品。如果字符串的長度不合適，那麼最終計算模數就會變成一些數字，可能是2的冪，例如2^32或2^64，但不會改變碰撞。 – 2015-03-08 21:34:52

您不能***避免***碰撞，因爲您將數百位下載到32位或僅64位。根據定義，這將導致衝突。幸運的是，哈希函數不必保證沒有碰撞，它只需要確保它們很少發生。字母的ASCII值從65開始爲大寫字母'A'，97爲小寫字母'a'，所以通過將這些數字相乘，您很可能不會碰撞到碰撞，除了您希望看到的特定類型的碰撞。（同一個字符不合要求。） – 2015-03-08 21:39:08

關於忽略字符排序的字符串散列函數的建議

回答

相關問題