c++ - 带线性探测的字符串散列

Question

我一直在尝试弄清楚如何使用线性探测进行字符串哈希处理。

基本上，这个想法是从字典(90000 个单词)中散列每个字符串，并检索所选单词的字谜。

这是我做的:

1. 创建了一个大小为 2*90000 的哈希表

2. 使用简单的哈希函数，我对字典中的每个单词进行哈希处理，得到一个值

3. 检查该哈希表索引是否为空，如果是，则赋值，如果不是，则生成一个新的哈希值。

4. 在哈希表中的每个单词之后，我执行搜索

5. 搜索词经过散列函数后会得到一个散列值，会检查该值是否存在于散列表中。

6. 如果存在，它将使用排列比较字符串。如果匹配为真，它将输出它。如果没有，它将继续使用新的哈希值进行查找。

问题是，整个过程非常慢......它的索引很好，但搜索需要很长时间。

我不知道如何让它更快..

感谢您花时间阅读本文。

Answer 1

首先将所有字母按字母顺序排列，然后使用您喜欢的任何哈希算法对结果进行哈希处理(crc32、md5sum、sha1、计算元音，任何...虽然计算元音会导致效率较低的解决方案) ，并将单词作为叶节点存储到该哈希条目(显然在链表中)——对哈希结果执行 mod(x) 以将桶限制为 2^x。

然后，当您要查找字谜时，对您的测试 单词执行完全相同的“插入”过程:按字母顺序排列字母，然后通过相同的散列函数运行它。然后对于每个叶节点，将按字母顺序排列的字母列表与保存单词的按字母顺序排列的列表进行比较。每个匹配项都是一个字谜。

(我通常不喜欢帮助家庭作业，但这个太诱人了。现在我有点想写一个有趣的小程序来查找给定词典中的所有字谜。)