最近，我在查看使用链接作为链表的散列表。我来到了使用“链”作为AVL树的可能性。 因此，散列表中的每个桶都将具有很少的AVL树的根指针。维基百科说哈希表的最坏情况是O（n）（http://en.wikipedia.org/wiki/Hash_table）。但是，如果我们使用每个桶的“链”作为AVL树，我们可以将其降至O（ln n）。为什么我们不用哈希表的项目存储AVL树？
我错过了什么吗？ 据我所知，我们可以用AVL树替换链表。 这样的ADT不会比带链接列表链接的单个AVL树或哈希表更好吗？
我搜索了互联网，无法找到这样的ADT。
这是维基百科的文章中讨论了直接引用的：
与其它结构
而不是列表分离链，可以使用支持所需操作的任何其他数据结构。例如，通过使用自平衡树，可以将常见哈希表操作（插入，删除，查找）的理论最坏情况时间降低到O（log n）而不是O（n）。但是，如果必须不惜一切代价（例如，在实时应用程序中）避免长时间延迟，或者如果必须防止散列到同一时隙的许多条目，则此方法仅值得麻烦和额外的内存成本（例如if一个预计分布极不均匀，或者对于易受恶意密钥分发请求影响的网站或其他可公开访问的服务）。
在Java中，标准HashMap如果存储桶大小超过常量8，则在存储桶中使用红黑树;如果桶变得小于6个条目，它们被线性化回到单链表;显然现实世界的测试表明，由于这种数据结构和额外的内存足迹的一般复杂性（因为树条目应该至少保存2个对其他条目的引用，所以单链接条目仅保存一个引用） ，而不是从理论上获得更好的渐近复杂度。
为了获得最佳性能，应该配置哈希表以便大多数桶只有一个入口（即它们不是偶数列表，只有唯一的入口），而且偶尔少于两个入口并且偶尔只有特殊的桶应该有3个或更多的条目。因此，与简单链表相比，在树中保持1-3个条目绝对没有意义。