data-structures - 为什么我们不使用AVL树来存储哈希表的项呢？

Question

最近，我正在研究使用链接作为链表的哈希表。我想到了使用“链”作为 AVL 树的可能性。 因此，哈希表中的每个桶都会有一点AVL树的根指针。维基百科说哈希表的最坏情况是 O(n) ( http://en.wikipedia.org/wiki/Hash_table )。然而，如果我们使用每个桶的“链”作为 AVL 树，我们可以将其降低到 O(ln n)。

我错过了什么吗？ 据我所知，我们可以用 AVL 树代替链表。 这样的 ADT 不是比单个 AVL 树或链表链接的哈希表更好吗？

我在网上搜索过，没有找到这样的ADT。

Answer 1

这在您引用的维基百科文章中直接讨论:

Separate chaining with other structures
Instead of a list, one can use any other data structure that supports the required operations. For example, by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g., in a real-time application), or if one must guard against many entries hashed to the same slot (e.g., if one expects extremely non-uniform distributions, or in the case of web sites or other publicly accessible services, which are vulnerable to malicious key distributions in requests).

在Java中，如果桶大小超过常量8，标准HashMap在桶中使用红黑树；如果桶小于 6 个条目，它们将线性化回单链表；显然，现实世界的测试表明，对于较小的存储桶来说，由于这种数据结构的一般复杂性和额外的内存占用，管理它们的树会损失更多(因为树条目应该至少保存 2 个对其他条目的引用，单链接条目仅保存一个引用) ，而不是从理论上更好的渐近复杂度中获得 yield 。

我还想补充一点，为了获得最佳性能，应该配置哈希表，以便大多数存储桶只有一个条目(即它们甚至不是列表，只是唯一的条目)，稍微少一点的应该包含两个条目，只有特殊的存储桶偶尔才应该包含有 3 个或更多条目。因此，与简单的链表相比，在树中保存 1-3 个条目绝对没有意义。