字谜 – 在C中用链接和探测进行哈希
我的标题被编辑了，所以我想确保每个人都知道这是作业。 问题只是优化程序，哈希是我的想法。
–
我正在努力优化一个C程序，它将相互字谜的单词组合在一起，然后将它们打印出来。
目前，该程序基本上是链表的链表。 外部列表中的每个链接都是一组相互字谜的单词。
程序的配置文件显示，到目前为止，执行时间的最大部分是函数wordLookup 。 这是因为它必须搜索每个节点，并且从文件读入可能的100k字，这可能需要很长时间。 例如，这里是用于读取40k字的gprof输出：
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 100.31 1.48 1.48 40000 37.12 37.12 wordLookup 0.00 1.48 0.00 78235 0.00 0.00 newnode 0.00 1.48 0.00 40000 0.00 0.00 sort_string 0.00 1.48 0.00 38235 0.00 0.00 wordInsert 0.00 1.48 0.00 1996 0.00 0.00 swap_words 0.00 1.48 0.00 1765 0.00 0.00 wordAppend
我想让它更快的想法是将数据结构更改为哈希表，该哈希表在同一个槽中链接彼此的所有字符串。
根据我教授所说的内容以及我在这里阅读的内容，我正在考虑使用哈希函数这样的东西。 （注意：素数的分布使得最常用的字母数字较少，使用最少的字母数字较大。）
sort(string) array alpha_primes = 5,71,37,29,2,53,59,19,11,83,79,31,43,13,7,67,97,23,17,3,41,73,47,89,61,101 hash(String) { hash = 1 for (char in String) { hash *= alpha_primes[char-'a']; } return hash % tablesize }
是否有针对此问题的哈希表大小，以便适当地分配值，使得每组字谜在表中具有不同的索引？
如果那是不可能的，那么我应该：
- 将单词列表链接在一起（列表列表）
- 使用探测（线性或二次）解决方案
- 对于这两种情况中的任何一种，比较时有哪些好处/缺点？
无法保证哈希值是唯一的。 碰撞的概率可以通过生日问题来计算，最好的办法是尽量减少碰撞。
2组散列到相同值的概率可近似为1-e ^（（ – k（k-1））/ 2n），其中k是您拥有的组的总数（与您的单词大致相同） count），n是哈希的搜索空间（2 ^（哈希的长度））。
我的词典大约有100000个单词，使得32b哈希非常好（2％的分类）。 但是，大的哈希表会使用4GB的RAM。 使用较小的表意味着更多的分裂。 链接或探测不会在时间上产生巨大的差异。
正如在您的问题的评论中所建议的那样，trie最终会以较小的数据结构结束。