带线性探测的字符串散列

首先将所有字母按字母顺序排列,然后使用任何哈希算法(crc32,md5sum,sha1,count the hyterms,anything…)对结果进行哈希运算。虽然计算元音会导致一个效率较低的解决方案),并将单词存储为该哈希项的叶节点(显然,在链接列表中),但对哈希结果执行mod(x)操作,以将存储桶限制为2^x。

然后,当你去寻找一个变位词时,在你的 测试 单词:按字母顺序排列,然后通过相同的哈希函数运行它。然后,对于每个叶节点,将按字母顺序排列的字母列表与保存的单词按字母顺序排列的列表进行比较。每一个匹配都是一个变位词。

(我通常不喜欢做家庭作业,但这个太诱人了。现在我有点想去写一个有趣的小程序,在给定的字典中找到所有的变位词。)

当您使用的哈希函数与某些输入字符串发生冲突时,使用线性探测。在这种情况下,您将按顺序搜索哈希表,直到找到搜索键。

这种方法的缺点是,如果发生一次碰撞,将会有更多的碰撞。

一种方法是你可以使用 Separate Chaining 并使用平衡树作为桶来改进查找。

如果只想提高性能,请确保没有冲突(在这种情况下,查找完全是O(1)),如果有,请增加哈希表的大小。

如果您正在搜索输入词的每个排列,这就是问题的根源。一个词的字母排列数目可能会很大。

相反,选择一个哈希函数,它对于单词的任何排列(变位词)都是相同的。例如,一个基于单词中字符的字符代码总和。

您是否试图创建给定字符串的变位词?在这种情况下,只需在获取字符串作为输入时创建一个变位词。散列这些字符串有什么意义?

编辑:首先,我建议您获取给定字符串的所有排列,然后遍历包含所有单词的字典文件。这样做的好处是你不需要把所有的单词都记在记忆中。如果要进一步优化,请根据字符串长度按升序或降序对整个文件进行排序,并继续检查字典文件中的字符串,直到<=到下一个字符串的长度为止。