为什么HashMap包含LinkedList而不是AVL树？

Question

本video中的讲师解释说，哈希映射实现通常包含一个链表，用于在发生冲突的情况下链式值。我的问题是:为什么不使用像AVL树这样的东西(插入、删除和查找需要O(log ))，而不是链表(最坏情况下查找O( n) )？

我知道哈希函数应该设计成很少会发生冲突。但是为什么不实现AVL树来优化这些罕见的情况呢？

Answer 1

这取决于实现HashMap的语言。我不认为这是一个严格的规则。

例如，在Java7之前，您的视频所说的都是真的。在Java8中，HashMap的实现被更改为一旦存储桶增长到某个点，就使用红黑树。

如果存储桶中的元素数少于8，则使用单链表。一旦它长得大于8，它就变成了一棵树。并且一旦它缩小到6，就恢复到单链表。

为什么不一直使用树呢？我猜这是内存占用和存储桶中查找复杂性之间的折衷。请记住，大多数哈希函数只会产生很少的冲突，因此为大小为3或4的存储桶维护一棵树将是非常昂贵的，这是没有充分理由的。

作为参考，这是一个HashMap的Java8实现(它实际上很好地解释了整个事情是如何工作的，以及为什么他们选择8和6作为"TREEIFY“和"UNTREEIFY”阈值)：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java?av=f

在Java7中：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/HashMap.java?av=f