为所有字母表生成相同的唯一哈希代码

Question

最近，我参加了一次面试，遇到了一个关于哈希碰撞的很好的问题。

问题：给出一个字符串列表，把字谜一起打印出来。

示例:

I/P： 、 、 、 、 、 、 、 、 、 、 、 、 {行为，上帝，动物，狗，猫}

O/P：               演戏，猫，狗，上帝

我要创建hashmap并将单词作为键，将值作为字母表列表

为了避免冲突，我想为字母表生成唯一的哈希代码，而不是排序并使用排序后的单词作为键。

我正在寻找哈希算法，照顾冲突，而不是使用链接。我想要算法为act和CAT生成相同的哈希代码...以便将下一个单词添加到值列表中

有谁能提出一个好的算法吗？

Answer 1

使用排序字符串进行散列是非常好的，我可能会这样做，但它确实可能会很慢而且很麻烦。这里有另一个想法，不确定它是否有效-选择一组素数，你喜欢的小，大小和你的字符集一样，并建立一个快速映射函数，从你的字符到它。然后，对于给定的单词，将每个字符映射到匹配的素数中，然后相乘。最后，使用结果进行哈希。

这与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次，以此类推。你不能得到任何你没有明确使用的新素数，素数意味着你不能通过任何其他素数的乘法得到它。

这带来了另一个可能的改进--如果可以构造字符串，只需要标记填充散列时看到的排列。由于这些排列可以按词典的顺序排列，所以您可以用一个数字来替换每一个。这将节省在哈希中存储实际字符串的空间，但需要更多的计算，因此不一定是一个好的设计选择。不过，这让采访的原始问题变得复杂了：）