AVL 树什么时候比哈希表更好？
更具体地说，如果使用 AVL 树而不是哈希表，是否可以更有效地执行任何操作？
More specifically, are there any operations that can be performed more efficiently if using an AVL tree rather than a hash table?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
与哈希表相比，我通常更喜欢 AVL 树。我知道哈希表的预期时间 O(1) 复杂度击败了 AVL 树的保证时间 O(log n) 复杂度，但在实践中，常数因素使这两种数据结构总体上具有竞争力，并且无需担心一些意外的数据会引发不良行为。另外，我经常发现在程序的维护生命周期中的某个时候，在无法预见的情况下，当最初选择的哈希表似乎是正确的时，我需要按排序顺序排列数据，所以我最终重写程序以使用AVL树而不是哈希表；这样做足够多次，你就会知道你不妨从 AVL 树开始。
如果您的键是字符串，三元搜索尝试提供 AVL 树或哈希表的合理替代方案。
I generally prefer AVL trees to hash tables. I know that the expected-time O(1) complexity of hash tables beats the guaranteed-time O(log n) complexity of AVL trees, but in practice constant factors make the two data structures generally competitive, and there are no niggling worries about some unexpected data that evokes bad behavior. Also, I often find that sometime during the maintenance life of a program, in a situation not foreseen when the initial choice of a hash table seemed right, that I need the data in sorted order, so I end up rewriting the program to use an AVL tree instead of a hash table; do that enough times, and you learn that you may as well just start with AVL trees.
If your keys are strings, ternary search tries offer a reasonable alternative to AVL trees or hash tables.
还想记住另外两点：
Also wanted to keep in mind two more points:
当然，一个明显的区别是，使用 AVL 树（和其他平衡树），您可以拥有持久性：您可以在 O(log N) 空间中从树中插入/删除元素，并且-时间到了，最终不仅会得到新树，还会保留旧树。
使用哈希表，通常无法在小于 O(N) 的时间和空间内完成此操作。
另一个重要的区别是键上所需的操作：AVL 树需要键之间的
<=比较，而哈希表需要=比较以及>哈希函数。An obvious difference, of course, is that with AVL trees (and other balanced trees), you can have persistency: you can insert/remove an element from the tree in O(log N) space-and-time and end up with not just the new tree, but also get to keep the old tree.
With a hash-table, you generally cannot do that in less than O(N) time-and-space.
Another important difference is the operations needed on the keys: AVL tress need a
<=comparison between keys, whereas hash-tables need an=comparison as well as ahashfunction.