尝试的缺点
Disadvantages of tries
我一直在研究尝试并检查它们的优点和缺点。它们在许多实际应用中非常有用，如字典、拼写检查器等，因为它们具有恒定的 O(m) 查找（其中 m 是字符串的长度）和其他优势，如提供字符串的有序检索和获取通用前缀。所以，优点对我来说很清楚，但局限性有点令人困惑。
我正在关注这个 link : https://en.wikipedia.org/wiki/Trie
这里列出的缺点是：
- 在某些情况下，尝试查找数据的速度可能比散列 tables 慢，尤其是当数据直接在硬盘驱动器或随机访问时间短的其他辅助存储设备上访问时与主内存相比高。
后续问题 - 为什么会有涉及二级存储的场景？不尝试也应该存储在主内存中。如果它们存储在辅助存储中，那么无论如何都没有使用 trie，因为磁盘访问总是会导致更多时间。
- 一些尝试可能需要比哈希 table 更多的 space，因为可能会为搜索字符串中的每个字符分配内存，而不是为整个条目分配单个内存块，因为在大多数哈希 table 中。
后续问题 : 是不是因为tries会包含更多references/pointers来连接每个字符到下一个字符，这样会消耗更多字节而不是作为一个完整的字符串存储？ （我从这里的一个答案中得到了这个原因）。谁也能详细说明一下吗？
非常感谢您的帮助。谢谢
首先，"constant O(m) look-ups"没有意义。 trie 中的查找时间为 O(m)：这取决于您要查找的字符串的长度。
构造良好的散列 table（即良好的散列函数和合理的加载因子）的查找时间为 O(1)。
假设结构合理，在散列中查找字符串 table 比在 trie 中查找要快得多。
尝试和散列 table 用于不同的事情。如果你想要的只是查找单词的能力，那么散列 table 会更快。如果你想找到共同的前缀、有序检索或做类似的事情，那么你需要一个 trie。
哈希 table 可以非常快速地查找单个字符串。它就像一匹纯种赛马。这是它可以做到的 all。另一方面，特里树是可以做很多事情的主力。它在查找方面永远不会像散列 table 那样快，但它可以做很多散列 table 不能做的事情。
例如，查找所有以 "pre" 开头的单词将花费 O(n) 的字典时间，因为您必须搜索所有单词。使用 trie，需要三个探针才能找到包含所有这些单词的子树，然后您要做的就是遍历该子树。当然，最坏的情况是 O(n)，但前提是你的 trie 中的所有单词都以 "pre".
开头
虽然转到磁盘确实比整个 trie 都在内存中要慢，但是说基于磁盘的 trie 没有比其他选择有优势的说法是错误的。如果数据不适合内存，那么无论您使用什么数据结构，您都需要一些外部（即非内存）存储。数据在磁盘上时访问速度变慢这一事实并没有从根本上改变 trie 与 hash table 的优点或缺点。例如，在查找具有特定前缀的所有单词时，基于磁盘的 trie 仍然比基于磁盘的哈希更快 table。
哈希 table 的开销通常是它包含的单词数的常数倍。也就是说，除了存储字符串所需的内存外，还有每个字符串的开销来存储哈希码和字符串之间的映射。
trie 的内存有点复杂。在最坏的情况下，每个 个字符 有一个节点。所有这些小节点分配开始加起来。想象一本包含 200,000 个单词的字典，平均单词长度为五个字符。那是一百万个节点的开销。
幸运的是，有很多方法可以大大压缩 trie，而不会损失太多（如果有的话）性能。由此产生的数据结构比简单构造的 trie 更小，对缓存更友好。
自问到这个问题已经有一段时间了，但我想补充一点，如果有人想知道，一个好的散列函数对于固定内存值（例如原始类型或 fixed-length 基本类型列表。相同的逻辑运算通常应用于所有要散列的值（逻辑左移和右移、按位运算等）。无论使用什么值，这些操作都需要相同的时间。这使得散列 tables 在存储耗尽 predictable 数量 space 的值时更快，并且相对可靠。如果您遍历底层字符数组并且仅每隔一段时间挑选字符以确保您始终对相同数量的内存进行哈希处理，则也可以在 O(1) 时间内完成字符串哈希处理。
例如，对于长度为 10 的字符串，您可以对底层字符数组中的 10 个字符进行哈希处理，而对于长度为 100 的字符串，您可以每隔 10 个字符进行哈希处理。
所以，要回答你的问题，散列通常在常数时间内完成，而从 trie 中插入或检索是 O(n) 时间，其中 n 是要插入或检索的值的长度。即使实践中差别不大，constant 也有 predictable 的优势。哈希 table 上的所有操作每次都将花费相同的时间，给予或接受。但是使用 trie（代表威尔士地名字典），搜索 Llanfairpwllgwyngyllgogerychwyrndrobwlllllantysiliogogogoch 并更改末尾的一个字符将比搜索 "a" 花费更多的时间。系统会在意识到它不在字典中之前吃掉整个字符串。 Google 和其他科技公司往往更喜欢漂亮的预测table（但均匀分布）哈希以避免安全问题。
我一直在研究尝试并检查它们的优点和缺点。它们在许多实际应用中非常有用，如字典、拼写检查器等，因为它们具有恒定的 O(m) 查找（其中 m 是字符串的长度）和其他优势，如提供字符串的有序检索和获取通用前缀。所以，优点对我来说很清楚，但局限性有点令人困惑。
我正在关注这个 link : https://en.wikipedia.org/wiki/Trie
这里列出的缺点是：
- 在某些情况下，尝试查找数据的速度可能比散列 tables 慢，尤其是当数据直接在硬盘驱动器或随机访问时间短的其他辅助存储设备上访问时与主内存相比高。
后续问题 - 为什么会有涉及二级存储的场景？不尝试也应该存储在主内存中。如果它们存储在辅助存储中，那么无论如何都没有使用 trie，因为磁盘访问总是会导致更多时间。
- 一些尝试可能需要比哈希 table 更多的 space，因为可能会为搜索字符串中的每个字符分配内存，而不是为整个条目分配单个内存块，因为在大多数哈希 table 中。
后续问题 : 是不是因为tries会包含更多references/pointers来连接每个字符到下一个字符，这样会消耗更多字节而不是作为一个完整的字符串存储？ （我从这里的一个答案中得到了这个原因）。谁也能详细说明一下吗？
非常感谢您的帮助。谢谢
首先，"constant O(m) look-ups"没有意义。 trie 中的查找时间为 O(m)：这取决于您要查找的字符串的长度。
构造良好的散列 table（即良好的散列函数和合理的加载因子）的查找时间为 O(1)。
假设结构合理，在散列中查找字符串 table 比在 trie 中查找要快得多。
尝试和散列 table 用于不同的事情。如果你想要的只是查找单词的能力，那么散列 table 会更快。如果你想找到共同的前缀、有序检索或做类似的事情，那么你需要一个 trie。
哈希 table 可以非常快速地查找单个字符串。它就像一匹纯种赛马。这是它可以做到的 all。另一方面，特里树是可以做很多事情的主力。它在查找方面永远不会像散列 table 那样快，但它可以做很多散列 table 不能做的事情。
例如，查找所有以 "pre" 开头的单词将花费 O(n) 的字典时间，因为您必须搜索所有单词。使用 trie，需要三个探针才能找到包含所有这些单词的子树，然后您要做的就是遍历该子树。当然，最坏的情况是 O(n)，但前提是你的 trie 中的所有单词都以 "pre".
开头虽然转到磁盘确实比整个 trie 都在内存中要慢，但是说基于磁盘的 trie 没有比其他选择有优势的说法是错误的。如果数据不适合内存，那么无论您使用什么数据结构，您都需要一些外部（即非内存）存储。数据在磁盘上时访问速度变慢这一事实并没有从根本上改变 trie 与 hash table 的优点或缺点。例如，在查找具有特定前缀的所有单词时，基于磁盘的 trie 仍然比基于磁盘的哈希更快 table。
哈希 table 的开销通常是它包含的单词数的常数倍。也就是说，除了存储字符串所需的内存外，还有每个字符串的开销来存储哈希码和字符串之间的映射。
trie 的内存有点复杂。在最坏的情况下，每个 个字符 有一个节点。所有这些小节点分配开始加起来。想象一本包含 200,000 个单词的字典，平均单词长度为五个字符。那是一百万个节点的开销。
幸运的是，有很多方法可以大大压缩 trie，而不会损失太多（如果有的话）性能。由此产生的数据结构比简单构造的 trie 更小，对缓存更友好。
自问到这个问题已经有一段时间了，但我想补充一点，如果有人想知道，一个好的散列函数对于固定内存值（例如原始类型或 fixed-length 基本类型列表。相同的逻辑运算通常应用于所有要散列的值（逻辑左移和右移、按位运算等）。无论使用什么值，这些操作都需要相同的时间。这使得散列 tables 在存储耗尽 predictable 数量 space 的值时更快，并且相对可靠。如果您遍历底层字符数组并且仅每隔一段时间挑选字符以确保您始终对相同数量的内存进行哈希处理，则也可以在 O(1) 时间内完成字符串哈希处理。
例如，对于长度为 10 的字符串，您可以对底层字符数组中的 10 个字符进行哈希处理，而对于长度为 100 的字符串，您可以每隔 10 个字符进行哈希处理。
所以，要回答你的问题，散列通常在常数时间内完成，而从 trie 中插入或检索是 O(n) 时间，其中 n 是要插入或检索的值的长度。即使实践中差别不大，constant 也有 predictable 的优势。哈希 table 上的所有操作每次都将花费相同的时间，给予或接受。但是使用 trie（代表威尔士地名字典），搜索 Llanfairpwllgwyngyllgogerychwyrndrobwlllllantysiliogogogoch 并更改末尾的一个字符将比搜索 "a" 花费更多的时间。系统会在意识到它不在字典中之前吃掉整个字符串。 Google 和其他科技公司往往更喜欢漂亮的预测table（但均匀分布）哈希以避免安全问题。