AVL树何时比哈希表更好？

Question

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

- Matt

---

这个问题有点过于笼统，无法全面回答。它非常依赖于哈希表的实现方式，但是在树中查找操作很可能比哈希表快得多。此外，在任何类型的树上，具有共同前缀的多个键的查找都保证比哈希表快得多（-->处理器缓存）。插入/删除操作很可能不会更有效，因为存在高度约束和重新平衡，但是哈希表也可能需要进行非平凡的操作，甚至需要重建整个哈希表（-->实现？）。 - Damon

除非您考虑到哈希表无法支持的操作，例如保持顺序和支持重复键。不必执行这些操作正是使哈希表基本上快速的原因。 - Hans Passant

谢谢大家，这些观点正是我所寻找的。如果问题表述不清，我很抱歉。 - Matt

@HansPassant: 哈希表并不是“基本快速”的，至少不是普遍如此。它们基本上具有O(1)的复杂度（加上O(N)），但这并不保证它们在每种情况下都更快。特别是对于大型数据集，哈希表有两个保证的缓存未命中（使用开放地址技术时，负载超过一定值会导致更多未命中）。另一方面，树有很大可能大部分或所有节点都在缓存中，尤其是在查找相关键时，而且不需要最终比较。再加上O(N)的计算哈希时间。这实际上取决于实现、数据集和访问模式。 - Damon

“哈希表”是一个不完整的解决方案。期望键使用什么“适当”的哈希函数？如何处理哈希冲突？在最坏的哈希冲突情况下，有多少（或多少少）可用存储空间被利用？而AVL树则始终可以实现100%的利用率。 - sawdust

Answer 1

我一般更喜欢AVL树而不是哈希表。 我知道哈希表的预期时间复杂度为O（1），优于AVL树的保证时间复杂度O（log n），但实际上，常数因素使得这两种数据结构通常具有竞争力，并且没有什么关于某些意外数据会引起糟糕行为的困扰。 此外，在程序的维护生命周期中，我经常发现在初始选择哈希表时看起来合适的情况下，需要按排序顺序使用数据，因此我最终会重写程序以使用AVL树而不是哈希表。 不断这样做，你会发现最好直接从AVL树开始。

如果您的键是字符串，则三进制搜索尝试是AVL树或哈希表的一个合理替代品。

- user448810

Answer 2

显然，AVL树（以及其他平衡树）与哈希表的一个明显区别是：你可以拥有持久性：你可以在O(log N)的时间和空间内向树中插入/删除元素，并最终得到不仅是新树，还能保留旧树。

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

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

- Stefan

---

这并不是全部的故事。存在许多具有对数复杂度的持久哈希表结构的实现。例如，https://en.wikipedia.org/wiki/Hash_array_mapped_trie 注意这是Clojure和Scala实现其默认Map类型的方式。 - Oscar Boykin

@OscarBoykin：实际上，HAMT可以被看作是哈希表和二叉树之间的混合体。 - Stefan