Question

为什么HashMap使用红黑树而不使用AVL树?

两者平均查找效率，为何会选择红黑树呢？

Answer 1

红黑树适用于大量插入和删除；因为它是非严格的平衡树；只要从根节点到叶子节点的最长路径不超过最短路径的2倍，就不进行平衡调节
AVL树是严格的平衡树，上述的最短路径与最长路径的差不能超过|1|，AVL允许的差值小；在进行大量插入和删除操作时，频繁地进行平衡调整会严重降低效率；
红黑树虽然不是严格的平衡树，但是其依旧是平衡树；查找效率是logn；
AVL也是logn；
红黑树舍去了严格的平衡，使其插入，删除，查找的效率稳定在O(logn)
反观AVL树，查找没问题O(logn)，但是为了保证高度平衡，动态插入和删除的代价也随之增加，综合效率肯定达不到O(logn)
所以在进行大量插入，删除操作时，红黑树更优一些
Hashmap用到数据结构有
数组，链表，红黑树
在没有地址冲突时，效率O(1)
有少量地址冲突，在冲突的地址拉链(建链表)，效率在O(1)~O(logn)之间
有大量地址冲突，在冲突的地址建红黑树，效率O(logn)