c++ - 字典的数据结构？

Question

存储字典的最佳数据结构是什么？哈希表还是树？考虑以后可以将更多单词添加到字典中的可能性。

Answer 1

std::unordered_map或将std::map是字典的最佳数据结构。std::unordered_map是哈希表的 C++11 等价物。Whilestd::map是常规的关联容器。

Answer 2

这些数据结构中的任何一个都不比另一个“更好”。这完全取决于您的需求。

如果您主要对回答“字符串 X 是否存在于我的哈希表中？”这个问题感兴趣，则字符串的哈希表是很好的选择。它支持（通常）快速查找并且内存占用少；每个字符串只存储一次。然而，它依赖于一个好的散列函数的存在，容易受到病态输入的散列冲突的影响，并且不允许您进行诸如“哪个字符串最接近我的字符串？”之类的搜索。

trie 是一种用于存储字符串的良好数据结构，可提供良好的最坏情况查找（您只需查看输入字符串的每个字符一次）。它还有一个优点是可以紧凑地存储具有相似前缀的字符串。此外，trie 允许您搜索具有给定前缀的字符串，或有效地进行正则表达式搜索，或有效地查找附近的单词。它的缺点是，由于存储的指针数量，trie 的内存使用量往往比哈希表高得多。

除了这些之外，您还可以考虑其他数据结构。Radix Trys 和 Patricia Trees 给出了更简洁的 try 表示，但有一些额外的编程复杂性。 如果您主要对有效地查找“接近”某个初始字符串的所有字符串感兴趣，则可以使用BK-trees 。

简而言之，如果内存非常宝贵，或者您不需要进行“关闭字符串”搜索，那么哈希表是一个不错的选择。如果您需要查找附近的字符串或进行其他字符串操作，trie 可能是更好的选择。

希望这可以帮助！