更具体地说,如果使用 AVL 树而不是哈希表,是否可以更有效地执行任何操作?
最佳答案
我通常更喜欢 AVL 树而不是哈希表。我知道哈希表的预期时间 O(1) 复杂度优于 AVL 树的保证时间 O(log n) 复杂度,但在实践中常数因素使这两种数据结构通常具有竞争力,并且没有琐碎的担忧一些引发不良行为的意外数据。此外,我经常发现在程序维护期间的某个时候,在最初选择哈希表似乎正确时无法预见的情况下,我需要按排序顺序排列数据,因此我最终重写了程序以使用AVL 树而不是哈希表;这样做的次数足够多,您就会了解到您还不如从 AVL 树开始。
如果您的键是字符串,三元搜索尝试为 AVL 树或哈希表提供合理的替代方案。
关于performance - AVL 树什么时候比哈希表更好?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8839311/