更具体地说,如果使用AVL树而不是哈希表,是否可以更有效地执行任何操作?
我通常更喜欢AVL树来哈希表。我知道哈希表的预期时间O(1)复杂度超过了AVL树的保证时间O(log n)复杂度,但在实践中,常数因素使这两种数据结构具有竞争性,并且没有任何令人烦恼的担忧。一些引起不良行为的意外数据。另外,我经常发现在某个程序的维护生命期间,在最初选择哈希表似乎没有预见到的情况下,我需要按排序顺序排列数据,所以我最终重写程序以使用AVL树而不是哈希表;做足够多的时间,你就会知道你也可以从AVL树开始。
如果您的密钥是字符串,则三元搜索尝试为AVL树或哈希表提供了合理的替代方法。
当然,一个明显的区别是,对于AVL树(和其他平衡树),您可以拥有持久性:您可以在O(log N)空间和时间中插入/删除树中的元素,最后不会只是新树,还要保留旧树。
使用哈希表,通常不能在小于O(N)的时间和空间中执行此操作。
另一个重要的区别是键上需要的操作:AVL tress需要键之间的<=
比较,而哈希表需要=
比较以及hash
函数。