管理进化

hashmap为什么用红黑树


hashmap使用红黑树的原因是:这样可以利用链表对内存的使用率以及红黑树的高效检索,是一种很有效率的数据结构。AVL树是一种高度平衡的二叉树,所以查找的非常高,但是,有利就有弊,AVL树为了维持这种高度的平衡,就要付出更多代价。每次插入、删除都要做调整,复杂、耗时。所以,hashmap用红黑树。

一、红黑树回顾

红黑树的英文是“Red-Black Tree",简称R-B Tree。它是一种不严格的平衡二叉查找树,前面说了,它的定义是不严格符合平衡二叉查找树的定义的。那红黑树空间是怎么定义的呢?

顾名思义,红黑树中的节点,一类被标记为黑色,一类被标记为红色除此之外,一棵红黑树还需要满足这样几个要求:

根节点是黑色的;

每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;

任何相邻的节点都不能同时为红色,红色节点是被黑色节点隔开的;

每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

二、红黑树的优势

红黑树是”近似平衡“的。

红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡有时候代价较大,所以效率不如红黑树,在现在很多地方都是底层都是红黑树的天下啦。

红黑树的高度只比高度平衡的AVL树的高度(log2n)仅仅大了一倍,在性能上却好很多。

HashMap在里面就是链表加上红黑树的一种结构,这样利用了链表对内存的使用率以及红黑树的高效检索,是一种很happy的数据结构。

AVL树是一种高度平衡的二叉树,所以查找的非常高,但是,有利就有弊,AVL树为了维持这种高度的平衡,就要付出更多代价。每次插入、删除都要做调整,就比较复杂、耗时。所以,对于有频繁的插入、删除操作的数据集合,使用AVL树的代价就有点高了。

红黑树只是做到了近似平衡,并不严格的平衡,所以在维护的成本上,要比AVL树要低。

所以,红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种性能稳定的平衡二叉查找树。

三、总结

java8不是用红黑树来管理hashmap,而是在hash值相同的情况下(且重复数量大于8),用红黑树来管理数据。 红黑树相当于排序数据,可以自动的使用二分法进行定位,性能较高。一般情况下,hash值做的比较好的话基本上用不到红黑树。

红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。

AVL树用于自平衡的计算牺牲了插入删除性能,但是因为最多只有一层的高度差,查询效率会高一些。

智齿客服