欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap1.8之节点删除分析

程序员文章站 2022-07-11 17:03:46
HashMap之节点删除 大家一直关注的都是HashMap如何添加节点,当节点数量大于8的时候转化为红黑树,否则使用链表等等,但大家是否有看过删除节点的处理逻辑呢? 今天来看看HashMap删除节点的神来之笔 问题来源 在查看HashMap源码时,有个以下字段,在删除的时候,判断节点数量,最多在小于 ......

hashmap之节点删除

  大家一直关注的都是hashmap如何添加节点,当节点数量大于8的时候转化为红黑树,否则使用链表等等,但大家是否有看过删除节点的处理逻辑呢? 今天来看看hashmap删除节点的神来之笔

 

问题来源

  在查看hashmap源码时,有个以下字段,在删除的时候,判断节点数量,最多在小于6的时候,会untreeifying(树转化为链表),在点击这个字段时发现,只有在split()方法中使用,但split()方法在resize()方法中使用,与删除节点无关,遂去翻删除节点的代码逻辑

 

  HashMap1.8之节点删除分析

节点删除

  通过remove方法,一路进来,找到删除节点的地方。如下图:

   HashMap1.8之节点删除分析

我们进入removetreenode方法中,代码如下:

  HashMap1.8之节点删除分析

 

查看方法注释,里面介绍到:如果节点太少,就会把当前bin转换成普通bin。不理解注释没关系,我们进入这个方法中唯一有转化的地方。进入untreeify()方法查看下。代码如下:

  HashMap1.8之节点删除分析

噢,第一行看一下,if,else看一下,嗯,这个方法就是获取返回了一个列表(这些方法都是treenode类里面的方法,所以请注意,this就是当前要操作的treenode节点)。到此明白,这个方法就是把红黑树转化成链表的,那么我的就得分析分析是如何操作的了,而没有使用到定义的全局变量。

 

删除判断逻辑分析

  HashMap1.8之节点删除分析

  我们来分析分析上面这个逻辑,进入这个untreeify() 的要求是,root == null, root.right ==null, root.left==null, root.left.left==null四种情况,我们以7个节点的红黑树来分析,a为root节点。

 

  HashMap1.8之节点删除分析

  所以进入这个方法主要有以下几种情况,我们一种一种的来分析当满足要求时,节点的个数。(这里默认认为知道红黑树的5个特点,主要是黑平衡)

 

  当这四种情况都满足时,我们可以看出最多节点有如上图所示个数,可以为7个。(大于8个不考虑,因为大于8会变成红黑树)。

    1.  最多节点情况:当我们删除节点d时,只满足root.left.left==null这个条件,这棵树仍可以维持红黑树的特点,这时的最大节点数为6.

    2.  最少节点情况:当efg不存在时,在a,b,c,d中删除任意一个节点,都会满足上述四种规则中的一种。则存在最少节点情况,有3个节点。

  以上情况都是会将树转化成链表,此时的节点是 3<= nodes <=6 ,由此可以看出,当节点数在小于6时,是可能转化成链表,但不是绝对情况, 所以使用定义的变量(固定数量6)也不正确。只好通过判断去动态获取节点数。

节点数量原因分析  

  为什么在小于6的时候可能转换成链表,而在大于8的时候转化成红黑树?

    主要通过时间查询节点分析,红黑树的平均查询时间为 log(n), 而链表是o(n),平均是o(n)/2。

    当节点数为8时,红黑树查询时间2,链表查询时间是:4, 可以看出来当红黑树查询效率大于了链表。(两个函数曲线问题,当节点更多是,比红黑树需要的时间更多)

    当节点数为6时,为什么转换成链表,我认为主要时因为节点数太少,如果还是用红黑树,为了维持红黑树的特点,则需要翻转,左旋,右旋,等,更消耗性能。 

  为什么不是7是转化?

    主要是为了给一个过渡,防止频繁转化。 也如上图,7个节点可能正好是一个满二叉树。