为什么HashMap使用红黑树而不是AVL树或者B+树
红黑树和AVL树都是最常用的平衡二叉搜索树。
但是，两者之间有些许不同：
-
AVL树更加严格平衡，因此可以提供更快的査找效果。因此，对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务，红黑树要好一些。 通常，AVL树的旋转比红黑树的旋转更难实现和调试。
红黑树更通用，再添加删除来说表现较好，AVL虽能提升一些速度但是代价太大了。
而不用B/B+树的原因：
B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。
红黑树和AVL树都是最常用的平衡二叉搜索树。 但是，两者之间有些许不同： AVL树更加严格平衡，因此可以提供更快的査找效果。因此，对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务，红黑树要好一些。 通常，AVL树的旋转比红黑树的旋转更难实现和调试。 红黑树更通用，再添加删除来说表现较好，AVL虽能提升一些速度但是代价太大了。 而不用B/B+树的原因： B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。