最近，我在查看使用鏈接作爲鏈表的散列表。我來到了使用「鏈」作爲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個條目絕對沒有意義。