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

Question

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

添加一个字符串(如果它不存在，则添加它，如果存在，则为该单词增加一个计数器)

计算给定的字符串(按字符串查找然后读取计数器)

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

Answer 1

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

然而，给定一个好的散列，查找将比在 trie 中更快。 (考虑到一个非常糟糕的散列，反之亦然。)如果你不知道你的输入，但有一个不错的散列算法，我个人更喜欢使用散列。

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