为所有字谜生成相同的唯一哈希码
最近，我参加了一次面试，遇到了一个很好的关于散列碰撞的问题。
问题:给出一个字符串列表，一起打印出字谜。
例子：
i/p :等价物、产品等。
o/p :产品价格、商品价格、商品价格等
我想要创建hashmap，并将单词作为键和值作为字谜列表。
为了避免冲突，我希望为字谜生成唯一的哈希码，而不是排序和使用排序的单词作为键。
我正在寻找哈希算法，它处理冲突，而不是使用链接。我想要算法为行为和猫生成相同的哈希码.以便将下一个单词添加到值列表中。
有人能提出一个好的算法吗？
回答 8
Stack Overflow用户
发布于 2013-09-13 11:45:16
使用排序字符串进行散列是非常好的，我可能已经这样做了，但它确实可能是缓慢和繁琐的。这里有另一个想法，不确定它是否有效-选择一组素数，像你喜欢的那么小，和你的字符集一样大小，然后构建一个从你的字符到那个的快速映射函数。然后，对于给定的单词，将每个字符映射到匹配的素数中，然后进行乘法。最后，使用结果进行散列。
这与Heuster的建议非常相似，只有较少的碰撞(实际上，考虑到任何数的素数分解的唯一性，我相信不会出现假碰撞)。
简单例如-
int primes[] = {2, 3, 5, 7, ...} // can be auto generated with a simple code
inline int prime_map(char c) {
// check c is in legal char set bounds
return primes[c - first_char];
}
...
char* word = get_next_word();
char* ptr = word;
int key = 1;
while (*ptr != NULL) {
key *= prime_map(*ptr);
ptr++;
}
hash[key].add_to_list(word); 编辑
关于惟一性的几个词--任何整数都有一个简单的素数乘数，因此在散列中给定一个整数键，您实际上可以重新构造所有可能的字符串，这些字符串将对它进行散列，并且只有这些单词。进入素数，p1^n1*p2^n2*.并将每个质数转换为匹配的字符。p1的字符将出现n1时间，等等。你不能得到你没有明确使用的任何新的素数，作为素数意味着你不能通过其他素数的任何乘法得到它。
这带来了另一个可能的改进--如果可以构造字符串，则只需标记填充哈希时看到的排列。因为排列可以按字典顺序排列，所以你可以用一个数字代替每一个排列。这将节省将实际字符串存储在散列中的空间，但需要更多的计算，因此它不一定是一个好的设计选择。尽管如此，它还是使面试的原始问题变得很复杂:)
Stack Overflow用户
发布于 2013-09-14 06:19:43
散列函数:为每个字符分配主编号。在计算哈希码时，获取分配给该字符的素数，并将所有的字谜都与现有的value.Now相乘产生相同的哈希值。
例:a-2，c-3t-7
散列值cat = 3*2*7 =42个散列值( act = 2*3*7 = 42 )打印所有具有相同散列值的字符串(字谜将具有相同的哈希值)
Stack Overflow用户
发布于 2016-03-30 13:48:27
其他海报建议将字符转换为素数，并将它们相乘。如果你做这个模一个大素数，你会得到一个好的哈希函数，不会溢出。我在大多数英语单词的Unix单词列表中测试了下面的Ruby代码，没有发现彼此不是字谜的单词之间的散列冲突。(在MAC OS X上，这个文件位于这里:/usr/share/dict/word。)
我的word_hash函数接受每个字符mod 32的序号值。这将确保大写字母和小写字母具有相同的代码。我使用的大素数是2^58 - 27。任何大素数只要小于2^64 /A，其中A是我的字母表大小即可。我使用32作为我的字母表大小，所以这意味着我不能使用一个大于2^59-1的数字。因为ruby使用一个位作为符号，而另一个位用来表示这个值是一个数字还是一个对象，所以我比其他语言少了一点。
def word_hash(w)
# 32 prime numbers so we can use x.ord % 32. Doing this, 'A' and 'a' get the same hash value, 'B' matches 'b', etc for all the upper and lower cased characters.
# Punctuation gets assigned values that overlap the letters, but we don't care about that much.
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131]
# Use a large prime number as modulus. It must be small enough so that it will not overflow if multiplied by 32 (2^5). 2^64 / 2^5 equals 2^59, so we go a little lower.
prime_modulus = (1 << 58) - 27
h = w.chars.reduce(1) { |memo,letter| memo * primes[letter.ord % 32] % prime_modulus; }
end
words = (IO.readlines "/usr/share/dict/words").map{|word| word.downcase.chomp}.uniq
wordcount = words.size
anagramcount = words.map { |w| w.chars.sort.join }.uniq.count
whash = {}
inverse_hash = {}
words.each do |w|
h = word_hash(w)
whash[w] = h
x = inverse_hash[h]
if x && x.each_char.sort.join != w.each_char.sort.join
puts "Collision between #{w} and #{x}"
else
inverse_hash[h] = w
end
end
hashcount = whash.values.uniq.size
puts "Unique words (ignoring capitalization) = #{wordcount}. Unique anagrams = #{anagramcount}. Unique hash values = #{hashcount}."https://stackoverflow.com/questions/18781106
复制相似问题
腾讯云开发者
