performance - 什么时候 AVL 树比哈希表更好？

Question

更具体地说，如果使用 AVL 树而不是哈希表，是否可以更有效地执行任何操作？

Answer 1

我通常更喜欢 AVL 树而不是哈希表。我知道哈希表的预期时间 O(1) 复杂度胜过 AVL 树的保证时间 O(log n) 复杂度，但在实践中，常数因素使这两种数据结构通常具有竞争力，并且没有任何琐碎的担忧一些引起不良行为的意外数据。此外，我经常发现在程序的维护生命周期中的某个时候，在未预见到的情况下，哈希表的初始选择似乎是正确的，我需要按排序顺序的数据，所以我最终重写程序以使用AVL 树而不是哈希表；这样做足够多的时间，你就会知道你不妨从 AVL 树开始。

如果您的键是字符串，则三元搜索尝试提供了 AVL 树或哈希表的合理替代方案。

Answer 2

当然，一个明显的区别是，使用 AVL 树（和其他平衡树），您可以具有持久性：您可以在 O(log N) 空间和时间中从树中插入/删除一个元素，最终结果不是刚出新树，老树也得保住。

使用哈希表，您通常无法在少于 O(N) 的时间和空间内完成此操作。

另一个重要的区别是键所需的操作：AVL 树需要<=键之间的比较，而哈希表需要=比较和hash函数。