我正在尝试找出什么数据结构可以快速支持以下操作:
- 添加一个字符串(如果不存在，则添加它，如果存在，则增加该单词的计数器)
- 对给定的字符串进行计数(按字符串查找，然后读取计数器)
我正在争论哈希表还是特里树。根据我的理解，只要避免冲突，哈希表的查找和添加速度就很快。如果我事先不知道我的输入，trie 会是更好的方法吗？
最佳答案
这实际上取决于您要用作“键”的字符串类型。如果您使用高度可变的字符串，而且您的字符串没有良好的哈希算法，那么 trie 的性能可能会优于哈希。
但是，如果有一个好的散列，查找将比在 trie 中更快。 (如果哈希值非常糟糕，则情况恰恰相反。)如果您不知道自己的输入，但确实有一个不错的哈希算法，我个人更喜欢使用哈希值。
此外，大多数现代语言/框架都具有非常好的哈希算法，因此您很可能能够使用哈希来实现良好的查找，只需很少的工作，这将表现得非常好。
关于data-structures - 添加/查找/保留字符串计数的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1586282/