gau*_*ain 5 trie data-structures
我一直在研究尝试并检查它们的优点和缺点。由于它们恒定的 O(m) 查找（其中 m 是字符串的长度）和其他优点（例如提供字符串的有序检索和获取公共前缀），它们在许多实际应用中非常有用，例如字典、拼写检查器等。所以，优点对我来说很清楚，但局限性有点令人困惑。
我正在关注此链接：https : //en.wikipedia.org/wiki/Trie
这里列出的缺点是：
后续问题- 为什么会有涉及二级存储的场景？不尝试也应该存储在主内存中。如果它们存储在二级存储中，那么无论如何都没有使用特里，因为磁盘访问总是会导致更多的时间。
后续问题：是否因为尝试将包含更多用于将每个字符连接到下一个字符的引用/指针，并且与将其存储为整个字符串相比会消耗更多字节？（我从这里的一个答案中得到了这个原因）。任何人都可以详细说明这一点吗？
我真的很感激这里的一些帮助。谢谢。
首先，“不断的 O(m) 查找”是没有意义的。trie 中的查找时间为 O(m)：这取决于您要查找的字符串的长度。
一个构造良好的哈希表（即良好的哈希函数和合理的负载因子）具有 O(1) 查找时间。
假设结构合理，在哈希表中查找字符串将比在字典树中查找快得多。
尝试和哈希表用于不同的事情。如果您想要的只是查找单词的能力，那么哈希表会更快。如果你想查找常见的前缀、有序检索或做类似的事情，那么你需要一个 trie。
哈希表可以非常快速地查找单个字符串。它就像一匹纯种赛马。这就是它能做的一切。另一方面，trie 是可以做很多事情的主力。它的查找速度永远不会像哈希表那么快，但它可以做很多哈希表无法做的事情。
例如，使用字典查找所有以“pre”开头的单词将花费 O(n) 时间，因为您必须搜索所有单词。使用字典树，需要三个探针才能找到包含所有这些单词的子树，然后您所要做的就是遍历该子树。当然，最坏的情况是 O(n)，但前提是你的 trie 中的所有单词都以“pre”开头。
虽然确实，访问磁盘会比整个 trie 都在内存中慢，但说基于磁盘的 trie 与替代方案相比没有任何优势是错误的。如果内存无法容纳数据，那么无论您使用什么数据结构，都需要一些外部（即非内存）存储。事实上，当数据在磁盘上时，数据访问速度会变慢，这一事实并没有从根本上改变 trie 与哈希表的优缺点。例如，在查找具有特定前缀的所有单词时，基于磁盘的 trie 仍然比基于磁盘的哈希表更快。
哈希表的开销通常是其包含的字数的常量倍数。也就是说，除了存储字符串所需的内存之外，还需要存储每个字符串的开销来存储哈希码和字符串之间的映射。
trie 的内存涉及更多一些。在最坏的情况下，每个字符有一个节点。所有这些小节点分配开始加起来。想象一本包含 200,000 个单词的字典，平均单词长度为 5 个字符。这是一百万个节点的开销。
幸运的是，有一些方法可以大大压缩 trie，而不会损失太多（如果有的话）性能。与简单构造的 trie 相比，生成的数据结构要小得多，并且对缓存更友好。