c - Anagrams - 在 C 中使用链接和探测进行散列

Question

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

--

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

目前程序基本上是链表的链表。外部列表中的每个链接都是一组单词，它们是彼此的变位词。

该程序的配置文件显示，到目前为止，执行时间的最大部分是函数 wordLookup。这是因为它必须搜索每个节点，并且可能从文件中读入 10 万个单词，这可能需要很长时间。例如，这是用于读取 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
}

是否有针对此问题的哈希表大小可以适本地分配值，以便每组变位词在表中都有一个不同的索引？

如果那不可能，那么我应该:

• 将单词列表链接在一起(列表列表)
• 使用探测(线性或二次)解决方案
• 对于这两种情况中的任何一种，比较起来有哪些优势/劣势？

Answer 1

无法保证哈希值是唯一的。碰撞的概率可以通过生日问题来计算，最好的办法是将它最小化。

2 个组散列为相同值的概率可以近似为 1-e^((-k(k-1))/2n)，其中 k 是您拥有的组的总数(大致相同作为你的字数)，n 是你的散列的搜索空间(2^(散列的长度))。

我的词典大约有 100000 个单词，32b 哈希非常好(2% 的冲突)。但是，那么大的哈希表将使用 4GB 的 RAM。使用较小的表意味着更多的冲突。链接或探测不会在时间上产生巨大差异。

正如在对您的问题的评论中所建议的那样，一个 trie 将以一个整体较小的数据结构结束。