Anagrams - C 中的链式哈希和探测

我的标题被编辑了，所以我想确保每个人都知道这是作业。问题只是优化程序，散列是我的想法。

--

我正在优化一个 C 程序，该程序将彼此不同的单词组合在一起，然后将它们打印出来。

目前的程序基本上是一个链表的链表。外部列表中的每个链接都是一组彼此不同的单词。

该程序的概要文件显示，到目前为止，执行时间的最大部分是函数wordLookup。这是因为它必须搜索每个节点，并且从文件中读取可能有 100k 个单词，这可能需要很长时间。例如，这是gprof40k 字阅读输出：

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。使用较小的表意味着更多的碰撞。链接或探测不会在时间上产生巨大的差异。

正如对您的问题的评论中所建议的那样，试验最终将得到一个较小的数据结构。