data-structures - 添加/查找/保留字符串计数的数据结构？

Question

我试图找出快速支持以下操作的数据结构：

• 添加一个字符串（如果不存在，则添加它，如果存在，则为单词增加一个计数器）
• 计算给定的字符串（按字符串查找，然后读取计数器）

我在哈希表或特里之间争论。据我了解，只要避免冲突，哈希表就可以快速查找和添加。如果我不提前知道我的输入，trie 会是更好的方法吗？

Answer 1

这实际上取决于您将用作“键”的字符串类型。如果您使用的是高度可变的字符串，而且您的字符串没有一个好的哈希算法，那么 trie 可以胜过哈希。

但是，给定一个良好的哈希，查找将比在 trie 中更快。（如果哈希值非常差，则相反。）如果您不知道自己的输入，但确实有一个不错的哈希算法，我个人更喜欢使用哈希值。

此外，大多数现代语言/框架都有非常好的散列算法，所以很有可能，您可以使用很少工作的散列来实现良好的查找，这将表现得非常好。

Answer 2

尝试不会给您带来太多好处；只有当前缀很重要时，它们才有意义。哈希表更简单，通常是语言标准库的一部分，如果不是语言本身的直接部分（Ruby、Python 等）。这是在 Ruby 中执行此操作的一种非常简单的方法：

strings = %w(some words that may be repeated repeated)
counts = Hash.new(0)
strings.each { |s| counts[s] += 1 }
#counts => {"words"=>1, "be"=>1, "repeated"=>2, "may"=>1, "that"=>1, "some"=>1}

附录：对于 C++，您可能可以使用Boost 的哈希实现。

Answer 3

任何一个都相当快。

没有必要完全避免碰撞。

更仔细地观察性能，通常哈希表比树快，但我怀疑现实生活中的程序是否会因为使用树而不是 HT 而运行太慢，并且某些树比某些哈希表快。

我们还能说什么，嗯，哈希表比树更常见。

复杂树的一个优点是它们具有可预测的访问时间。对于哈希表和简单的二叉树，您看到的性能取决于数据，而对于 HT，性能在很大程度上取决于实现的质量及其相对于数据集大小的配置。