字符串散列算法

Question

我遇到了一种情况，我不得不计算字符串中每个字的出现次数。我决定哈希将是最好的方式（找到每个遇到的单词的哈希值，并在由哈希值索引的位置增加计数 - 假设我使用了一个数组）。我可以使用什么散列算法来确保为每个字符串生成的散列值是唯一的？

这导致了一个更大的问题。如何做到语言库（Java为例）实现HashMap一样生成在字符串的情况下，唯一的散列值的数据结构？

我想知道在这种算法的实现背后涉及的数学结构。

Answer 1

我可以使用什么哈希算法来确保为每个字符串生成的哈希值是唯一的？

没有这样的功能。字符串的空间是无限的，但目标空间是有限的（比如你使用的是32位整数）。你不能用无穷空间映射到有限空间;必须有碰撞。

语言库（例如Java）如何实现像hashmap这样的数据结构，以便在字符串的情况下生成唯一的哈希值？

他们不;上述每个字符串都没有唯一的哈希函数。

我遇到了一种情况，我不得不计算字符串中每个单词的出现次数。我决定哈希将是最好的方式（找到每个遇到的单词的哈希值，并在由哈希值索引的位置增加计数 - 假设我使用了一个数组）。

你有正确的想法。只需使用字典映射string s到int。例如，在C＃中，我们将使用Dictionary<string, int>。大多数现代语言都存在类似的东西。让语言/框架处理碰撞问题以及不适合你的问题，只关注在该语言/框架下表达你的想法。

Answer 2

你不能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); 

Answer 3

你不能有保证唯一性散列算法;这是pigeonhole principle。为什么不使用二叉树？

Answer 4

从理论上说，你可以不哈希保证唯一性 - 除非你的散列的长度总是长或更长的原始字符串，这是一种适得其反。

有关此方面的全面说明，请参阅Tom Archer的“Are Hash Codes Unique?”。

Answer 5

在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防弹（大部分）。

Answer 6

散列不能成为一个对一个功能，它为每输入一个唯一的输出，只是因为，通常情况下，的函数的值域比域小，所以你问是不可能的。

当然，如果字符串的长度是有限的，并且所有可能的字符串的集合都低于精确的绑定，那么您可以使用所谓的完美的哈希函数。

您可以只搜索一个具有低碰撞概率的良好散列函数，只需从here开始，玩得开心！

备注：如果我没有错Java Hashtable不使用开放寻址。无论何时发现碰撞，元素都通过一个列表放置在相同的，已被占用的单元格中。所以这绝对是你想的正好相反.. implmentations不设法保证唯一性，他们转而选择，最大限度地减少某些方面

Answer 7

源代码胜过千言万语一个很好的冲突解决策略...

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

Answer 8

我认为你要找的是Substring Index或字符串搜索。我错过了什么吗？