为什么我们不使用 AVL 树来存储哈希 table 的项目？
Why don't we use AVL tree for hash table's item storage?
最近，我正在查看使用链接作为链表的散列table。我想到了使用 "chain" 作为 AVL 树的可能性。
因此，散列 table 中的每个桶都会有很少的 AVL 树的根指针。维基百科说哈希 table 的最坏情况是 O(n) (http://en.wikipedia.org/wiki/Hash_table)。但是，如果我们使用每个桶的 "chain" 作为 AVL 树，我们可以将其降低到 O(ln n).
我错过了什么吗？
据我所知，我们可以用 AVL 树替换链表。
这样的 ADT 会不会比单个 AVL 树或具有链表链接的散列 table 更好？
我在网上搜索了一下，没有找到这样的ADT。
这在您引用的维基百科文章中直接讨论：
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中，标准HashMap在桶中使用红黑树，如果桶大小超过常量8；如果 bucket 变得小于 6 个条目，它们将被线性化回单链表；显然，现实世界的测试表明，由于这种数据结构的一般复杂性和额外的内存占用，对于较小的存储桶管理它们，因为树损失更多（因为树条目应该至少包含 2 个对其他条目的引用，单链接条目只包含一个引用） ，而不是从理论上更好的渐近复杂性中获益。
我还要补充一点，为了获得最佳性能，散列 table 应该配置为大多数桶只有一个条目（即它们甚至不是列表，只是唯一的条目），稍微少一点应该包含两个条目并且偶尔只有特殊的桶应该有 3 个或更多条目。因此，与简单的链表相比，在树中保留 1-3 个条目完全没有意义。
最近，我正在查看使用链接作为链表的散列table。我想到了使用 "chain" 作为 AVL 树的可能性。 因此，散列 table 中的每个桶都会有很少的 AVL 树的根指针。维基百科说哈希 table 的最坏情况是 O(n) (http://en.wikipedia.org/wiki/Hash_table)。但是，如果我们使用每个桶的 "chain" 作为 AVL 树，我们可以将其降低到 O(ln n).
我错过了什么吗？ 据我所知，我们可以用 AVL 树替换链表。 这样的 ADT 会不会比单个 AVL 树或具有链表链接的散列 table 更好？
我在网上搜索了一下，没有找到这样的ADT。
这在您引用的维基百科文章中直接讨论：
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中，标准HashMap在桶中使用红黑树，如果桶大小超过常量8；如果 bucket 变得小于 6 个条目，它们将被线性化回单链表；显然，现实世界的测试表明，由于这种数据结构的一般复杂性和额外的内存占用，对于较小的存储桶管理它们，因为树损失更多（因为树条目应该至少包含 2 个对其他条目的引用，单链接条目只包含一个引用） ，而不是从理论上更好的渐近复杂性中获益。
我还要补充一点，为了获得最佳性能，散列 table 应该配置为大多数桶只有一个条目（即它们甚至不是列表，只是唯一的条目），稍微少一点应该包含两个条目并且偶尔只有特殊的桶应该有 3 个或更多条目。因此，与简单的链表相比，在树中保留 1-3 个条目完全没有意义。