字符串散列算法

我遇到了一種情況，我不得不計算字符串中每個字的出現次數。我決定哈希將是最好的方式（找到每個遇到的單詞的哈希值，並在由哈希值索引的位置增加計數 - 假設我使用了一個數組）。我可以使用什麼散列算法來確保爲每個字符串生成的散列值是唯一的？字符串散列算法

這導致了一個更大的問題。如何做到語言庫（Java爲例）實現HashMap一樣生成在字符串的情況下，唯一的散列值的數據結構？

我想知道在這種算法的實現背後涉及的數學結構。

來源

2010-10-17 Raj

http://code.google.com/p/gphfa/包含許多流行的字符串哈希算法。 – st0le 2010-10-17 17:59:13

我可以使用什麼哈希算法來確保爲每個字符串生成的哈希值是唯一的？

沒有這樣的功能。字符串的空間是無限的，但目標空間是有限的（比如你使用的是32位整數）。你不能用無窮空間映射到有限空間;必須有碰撞。

語言庫（例如Java）如何實現像hashmap這樣的數據結構，以便在字符串的情況下生成唯一的哈希值？

他們不;上述每個字符串都沒有唯一的哈希函數。

我遇到了一種情況，我不得不計算字符串中每個單詞的出現次數。我決定哈希將是最好的方式（找到每個遇到的單詞的哈希值，並在由哈希值索引的位置增加計數 - 假設我使用了一個數組）。

你有正確的想法。只需使用字典映射string s到int。例如，在C＃中，我們將使用Dictionary<string, int>。大多數現代語言都存在類似的東西。讓語言/框架處理碰撞問題以及不適合你的問題，只關注在該語言/框架下表達你的想法。

來源

2010-10-17 17:26:24 jason

你不能100％確定，根據定義散列可以有衝突。

您可以在grepcode看到String是如何在Java散列。基本上HashMap（和其他基於散列的結構）每次都使用hashCode()方法。

所以，如果你想算一個特定的詞的迭代次數，你應該使用Map<String, Integer>（在Java中），並從那裏計數。

例如：

Map<String, Integer> words = new HashMap<String, Integer>(); 
String word = "lol"; 

Integer count = words.get(word); 
if(count == null){ 
    count = 0; 
} 
words.put(word, count + 1);

來源

2010-10-17 17:25:37

錯誤。看[完美散列]（http://en.wikipedia.org/wiki/Perfect_Hashing）。 – SLaks 2010-10-17 17:27:33

@SLaks，很好，我不知道這篇文章。但正如它所說的那樣，它是爲了一套S的價值觀，而且將它用於「單詞」是很難的（幾乎不可能）。 – 2010-10-17 17:30:21

我明白..是否有任何標準算法來完成這一點？ – Raj 2010-10-17 17:30:46

你不能有保證唯一性散列算法;這是pigeonhole principle。爲什麼不使用二叉樹？

來源

2010-10-17 17:25:46

但是它不可能在O（1）中的二叉樹上執行插入和刪除操作，這正是我正在尋找的。 – Raj 2010-10-17 17:28:20

@ user441575：你有多少個不同的單詞？您可能會發現，對於少量單詞的二進制搜索比每隔一次計算一次散列效率要高得多。 – 2010-10-17 17:34:09

從理論上說，你可以不哈希保證唯一性 - 除非你的散列的長度總是長或更長的原始字符串，這是一種適得其反。

有關此方面的全面說明，請參閱Tom Archer的「Are Hash Codes Unique?」。

來源

2010-10-17 17:26:06 jsalonen

在Java中，哈希碼String被實現如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用INT算術，其中s [i]是字符串的第i個字符，n是串的長度，和^表示取冪。（空字符串的哈希值是零。）

來源：JavaDoc for java.lang.String

你可能要考慮使用類似的算法，使您的hashCode防彈（大部分）。

來源

2010-10-17 17:27:11 Mike

散列不能成爲一個對一個功能，它爲每輸入一個唯一的輸出，只是因爲，通常情況下，的函數的值域比域小，所以你問是不可能的。

當然，如果字符串的長度是有限的，並且所有可能的字符串的集合都低於精確的綁定，那麼您可以使用所謂的完美的哈希函數。

您可以只搜索一個具有低碰撞概率的良好散列函數，只需從here開始，玩得開心！

備註：如果我沒有錯Java Hashtable不使用開放尋址。無論何時發現碰撞，元素都通過一個列表放置在相同的，已被佔用的單元格中。所以這絕對是你想的正好相反.. implmentations不設法保證唯一性，他們轉而選擇，最大限度地減少某些方面

來源

2010-10-17 17:28:18 Jack

源代碼勝過千言萬語一個很好的衝突解決策略...

String.java，看的hashCode（）方法：http://www.google.com/codesearch/p?hl=zh-TW#ih5hvYJNSIA/src/share/classes/java/lang/String.java&q=String.java%20hashcode&sa=N&cd=1&ct=rc

HashMap.java，看看的put（）方法： http://www.google.com/codesearch/p?hl=zh-TW#ih5hvYJNSIA/src/share/classes/java/util/HashMap.java&q=hashMap.java%20%22V%20put%22&sa=N&cd=1&ct=rc

來源

2010-10-17 17:54:14 tszming

我認爲你要找的是Substring Index或字符串搜索。我錯過了什麼嗎？

來源

2010-10-21 11:11:04 yadab

字符串散列算法

回答

相關問題