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

Question

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

Answer 1

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

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