最近，我参加了一个面试，遇到了一个关于哈希冲突的好问题。
问题:给定一个字符串列表，一起打印出字谜。
示例:
i/p: {行为、神、动物、狗、猫
o/p : 行动、猫、狗、上帝
我想创建 HashMap 并将单词作为键，将值作为字谜列表
为了避免冲突，我想为字谜生成唯一的哈希码，而不是排序并将排序后的单词用作键。
我正在寻找除使用链接外还可以处理冲突的哈希算法。我希望算法为 act 和 cat 生成相同的哈希码...以便它将下一个单词添加到值列表
谁能推荐一个好的算法？
最佳答案
对排序后的字符串进行散列处理非常好，我可能已经这样做了，但它确实可能很慢而且很麻烦。这是另一个想法，不确定它是否有效 - 选择一组素数，尽可能小，与您的字符集大小相同，并构建一个从您的字符到它的快速映射函数。然后对于给定的单词，将每个字符映射到匹配的素数，然后相乘。最后，使用结果进行散列。
这与 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 次，依此类推。 你不能得到任何你没有明确使用的新质数，作为质数意味着你不能通过其他质数的任何乘法得到它。
这带来了另一个可能的改进——如果你可以构造字符串，你只需要标记你在填充哈希时看到的排列。由于排列可以按字典顺序排序，因此您可以用数字替换每个排列。这将节省在散列中存储实际字符串的空间，但需要更多计算，因此它不一定是一个好的设计选择。尽管如此，它还是使面试的原始问题变得很复杂 :)
关于algorithm - 为所有字谜生成相同的唯一哈希码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18781106/