用线性探测字符串哈希

我被困在试图弄清楚如何用线性探测字符串哈希。用线性探测字符串哈希

基本上，这个想法是散列字典（90000字）的每个字符串，并检索所选单词的字形。

这里就是我所做的：

创建一个哈希表的大小
使用一个简单的哈希函数2 * 90000，我哈希从字典中的每个字，得到一个值
检查散列表索引是否为空，如果是，则分配值，如果不是，则生成新的散列值。
后，每一个字都是在哈希表，我执行搜索
搜索词将散列函数后收到的哈希值，在哈希表中是否存在该值，将检查或不。
如果存在，它会比较使用排列的字符串。如果匹配成立，它将输出它。如果不是，它将继续使用新的哈希值查找。

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

我出如何使这个想法更快..

感谢您抽出时间阅读本。

来源

2010-01-25 tpae

您正在使用哪种数据结构来存储散列字符串？ – Naveen 2010-01-25 05:46:11

我正在使用字符串数组，因为它需要遵循线性探测。 – tpae 2010-01-25 05:55:40

先把所有的字母按字母顺序排列，然后用任何哈希算法对结果进行哈希（crc32，md5sum，sha1，计算元音，任何东西......但计算元音会导致效率较低的解决方案），并将该单词作为叶节点存储到该散列条目中（显然，在链表中） - 对散列结果执行mod（x）以将桶限制为2^x。

然后，当你去找到一个字谜，做你测试字完全相同的“插入”过程：按字母顺序排列的字母，然后通过你的相同的哈希函数运行它。然后，对于每个叶节点，将字母顺序的字母列表与保存的字母字母表列表进行比较。每场比赛都是一个字谜。（我通常不喜欢给家庭作业帮助，但这个太诱人了，现在我想写一个有趣的小程序来找到给定字典中的所有字母。）

来源

2010-01-25 06:03:03 tylerl

问题是关于线性探测 - 他应该将该单词存储在下一个打开的存储区中，而不是存储在（不存在的）叶节点中。但是，对字母排序的建议比修改散列算法本身更好。 – 2010-01-25 06:27:09

+1用于排序字母，对于字谜它确实有意义，并且您甚至可以获得所有字谜在同一个存储桶中结束的好处。 – 2010-01-25 12:31:26

-1

您是否尝试创建给定字符串的Anagrams？在这种情况下，只需创建一个字符串作为输入。对这些字符串进行散列有什么意义？

编辑：首先，我会建议你得到给定的字符串的所有排列，然后通过字典文件包含所有单词循环。这有一个好处，你不需要在内存中拥有所有的单词。如果您想进一步优化，请根据字符串长度按升序或降序对整个文件进行排序，并继续检查字典文件中的字符串，直到您将< =更改为下一个字符串的长度。

来源

2010-01-25 05:50:06 Jagannath

来搜索那个anagram是否是一个有效的单词 – sud03r 2010-01-25 05:53:29

anagrams需要来自字典。由于有90000个单词，因此使用排列依次遍历它们应该更慢。 – tpae 2010-01-25 05:53:33

线性探测用于您正在使用的散列函数为某些输入字符串提供冲突的情况。在这种情况下，您将按顺序搜索散列表，直到找到您的搜索关键字。

这种方法的缺点是，如果有一次碰撞，会有更多。

一种方法是，您可以使用Separate Chaining并使用平衡树作为存储桶以改善查找。

如果您只是想提高性能，请确保没有冲突（在这种情况下，查找完全是O（1）），如果存在，请增加散列表大小。

来源

2010-01-25 06:09:40 sud03r

对不起，但作业要求我使用线性探测.. :( – tpae 2010-01-25 07:22:59

-1

如果您正在搜索输入词的每个置换，这是问题的根源。一个单词字母的排列数量可能会相当大。

取而代之，选择一个散列函数，它对任何一个单词的排列（anagram）都是一样的。例如，基于单词中字符的字符代码总和。

来源

2010-01-25 06:21:11 ergosys

虽然这解决了即时问题，但它是一个非常糟糕的散列算法 - 将会有大量的碰撞。更好的解决方案是tylerl提出的一个更好的解决方案，它可以使用一种好的散列算法，并且仍然可以处理大量的排列 – 2010-01-25 06:25:51

我没有说散列函数是什么，只是它对于任何排列都是一样的，如果你先排序字符，这符合我的标准。犯了一个坏例子，虽然 – ergosys 2010-01-25 06:30:10

这是行不通的，因为不是所有的单词长度都是一样的 – tpae 2010-01-25 06:30:35

用线性探测字符串哈希

回答

相关问题