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

红黑树适用于大量插入和删除；因为它是非严格的平衡树；只要从根节点到叶子节点的最长路径不超过最短路径的2倍，就不用进行平衡调节

AVL 树是严格的平衡树，上述的最短路径与最长路径的差不能超过 1，AVL 允许的差值小；在进行大量插入和删除操作时，会频繁地进行平衡调整，严重降低效率；

红黑树虽然不是严格的平衡树，但是其依旧是平衡树；查找效率是 O(logn)；

AVL也是 O(logn)；

红黑树舍去了严格的平衡，使其插入，删除，查找的效率稳定在 O(logn)

反观 AVL 树，查找没问题 O(logn)，但是为了保证高度平衡，动态插入和删除的代价也随之增加，综合效率肯定达不到 O(logn)

所以在进行大量插入，删除操作时，红黑树更优一些

HashMap 用到数据结构有（JDK 1.8）：数组，链表，红黑树

在没有地址冲突时，效率 O(1)

有少量地址冲突，在冲突的地址拉链(建链表)，效率在 O(1) ~ O(logn) 之间

有大量地址冲突，在冲突的地址建红黑树，效率 O(logn)

巴特西