3

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

--

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

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

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

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
}

这个问题是否有一个哈希表大小可以适当地分配值，使得每组字谜在表中都有一个不同的索引？

如果那是不可能的，那么我应该：

  • 将单词列表链接在一起（列表列表）
  • 使用探测（线性或二次）解决方案
  • 对于这两种情况，比较起来有哪些优点/缺点？
4

1 回答 1

1

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

2 个组散列到相同值的概率可以近似为 1-e^((-k(k-1))/2n)，其中 k 是您拥有的组的总数（与您的单词大致相同计数），n 是哈希的搜索空间（2^（哈希长度））。

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

正如对您的问题的评论中所建议的那样，trie 最终将以较小的数据结构结束。

于 2013-04-14T00:27:12.833 回答