为所有字谜生成相同的唯一哈希码

Question

最近,我参加了一次采访,并面临一个关于哈希冲突的好问题.

问题:给定一个字符串列表,一起打印出字谜.

例如:

i/p:{act,god,animal,dog,cat}

o/p:act,cat,dog,god

我想创建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*...并将每个素数转换为匹配的char.p1的char将出现n1次,依此类推.你不能得到任何你没有明确使用的新素数,素数意味着你不能通过任何其他素数的乘法得到它.

这带来了另一种可能的改进 - 如果你可以构造字符串,你只需要标记填充哈希时看到的排列.由于排列可以按字典顺序排序,因此您可以用数字替换每个排列.这样可以节省将实际字符串存储在散列中的空间,但需要更多的计算,因此它不一定是一个好的设计选择.尽管如此,它仍然是一个很好的复杂的原始问题的访谈:)

Answer 2

哈希函数：为每个字符分配主要数字。计算哈希码时，获取分配给该字符的素数并乘以现有值，现在所有字谜都产生相同的哈希值。

例如：a-2，c-3 t-7

cat的哈希值= 3 * 2 * 7 = 42 act的哈希值= 2 * 3 * 7 = 42打印所有具有相同哈希值的字符串（字谜将具有相同的哈希值）