HashMap为什么不用B+树来替换红黑树?

来源：千锋教育

发布人：xqq

时间： 2023-10-14 17:05:16

一、HashMap不用B+树来替换红黑树的原因

1、算法实现复杂

Java中已经实现了红黑树，而B+树的实现还需要从头开始，复杂度会更高。

2、底层不符合

HashMap的底层是哈希，但红黑树不是。并且HashMap的节点使用链表或数字（有些实现使用二次哈希），是为了解决哈希冲突（不同的的Key哈希到相同的位置了）。

3、修改效率较低

HashMap的元素是动态修改的，红黑树修改元素，不用移动元素的位置，因为直接修改左右父指针的值就好了，但是B+树的同一个块内的元素，没有指针这个东西，所以修改元素就需要移动元素，这个开销就很大了，也会触发频繁内存分配和回收。B+树之所以运用于磁盘存储结构，因为磁盘的数据一般都是比较冷的数据，否则一般都会因为淘汰策略常驻内存。因为冷所以可以使用静态的数据结构，同时，因为没有更多的指针，存储空间占用也会少。所以总结起来，热数据用红黑树组织，冷数据用B+树组织。红黑树相对于B+树就好比链表相对于数组。

4、可维护性差

B+树的维护相较于红黑树需要更多更复杂的操作，因此难以维护。

二、HashMap简介

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。在Java编程语言中，加载因子默认值为0.75，默认哈希表元为101。但是此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

三、B+树简介

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

B+树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

B+背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。

B+ 树的创造者Rudolf Bayer没有解释B代表什么。最常见的观点是B代表平衡（balanced），因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音（Boeing），因为他曾经工作于波音科学研究实验室。

四、红黑树简介

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 。由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

结点是红色或黑色根结点是黑色所有叶子都是黑色（叶子是NIL结点）每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操作与普通二叉查找树相同。

延伸阅读1：红黑树数据结构简述

它的统计性能要好于平衡二叉树（有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树），因此，红黑树在很多地方都有应用。目前，基于拥有上述特性，红黑树已广泛应用Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。其他平衡树还有：AVL，SBT，伸展树，TREAP等等。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。