没有合适的资源?快使用搜索试试~ 我知道了~
首页(001)HashMap之链表转红黑树-treefyBin方法.docx
详细解读了HashMap中链表转红黑树的treefyBin方法,该方法中涉及到的诸如:replacementTreeNode方法、treeify方法、comparableClassFor方法、compareComparables方法、tieBreakOrder方法、balanceInsertion方法、moveRootToFront 方法、rotateLeft方法、rotateRight方法、checkInvariants 方法均有详细解读
资源详情
资源评论
资源推荐
之链表转红黑树树化 方法
方法概述:先将链表节点转为树节点,再将都是红黑树节点的链表转为红黑树
分析 的 方法的源码时发现,当 中某个链表上存储的元素个数达到
树化阈值 个时,会调用 方法尝试将该链表转换成红黑树。
为什么说是尝试,而不是直接转呢?因为,在做转换之前,还会对 的链表数组存
储的元素个数进行判断,当 存储的总元素个数达到 !"##"树化最小
容量, 存储的元素总个数$% 时,才会进行链表到红黑树的转换;否则,只进行扩
容。
概括起来,将链表转为红黑树主要有以下处理:
判断链表中存储的元素个数是否到达树化阈值 ,没达到不往下处理
判断 中链表数组的长度是否达到树化最小容量 $%,没达到则扩容,而非转红黑
树
将需要树化的链表中的所有节点替换成树节点。
将所有节点已经是红黑树节点的链表转为红黑树
具体,详见下述的源码解析:
的 方法中调用 的源码
方法概述:链表长度达到树化阈值时,开始调用 尝试转红黑树
&''("&'')*'*'++("&',
'''''''''''-.''//',
''''''''''''-.''0!&12'32'4/2'//*
'''''''''''''("&'5''6'7'88'67'&'7
当链表中存储的元素个数达到
等于
树
化阈值
时,开始链表转红黑树的处理
''''''''''''''''(2'*
开始尝试将链表结构转成红黑树结构,但还保留有链表的顺序结构
具
体方法源码详见第
2
点
''''''''''''(3*
''''''''9
'''''''''-'''::
''''''''''''3''-3''3';;'3'<'//'::'3-=/3
''''''''''''(3*
''''''''''*
''''9
的 方法的源码
方法概述: 数组长度达到树化最小容量,开始树化操作:先将链表中的节点都替换成
树节点,再将树节点组成的链表转为红黑树
8>>>'/?'//'/31'&1''(''1.'&'@4''/'(/''&&'A//2''0?'
?'B'1-
将给定
索引的桶中的所有链表节点替换掉
,
除非数组太小的话,就用扩容
方法替代。
>8
''''''!&1CD2E5FG'(2''',
'''''''''2'1.*'!&1CD2E5'*
'''''''''(''';;'''(-/@'C'MIN_TREEIFY_CAPACITY
当
存储链表头节点的数组
为
或其长度达不到
小于等于
树化最小容量
时,则进行扩容而非树化操作。
''''''''''''B*
调用扩容方法
''''''''''''(F1.'''6'7':'G'<'',
指定的数组索引位置的头节点不为空才继续
''''''''''''!&1CD2E5'1''2'/''*
代表处理过程中需要被转成红黑树的链表的头节
,
代表处理过程中需要被转为红黑树节点的链表的实时最新当前尾节点
''''''''''''',
''''''''''''''''!&1CD2E5'''/?A!&12'*
将链表类型
的节点转成树类型
的节点,
具体方法源码详见第
3
点
。
'''''''''''''''''/''
尾节点为
,说明还没开始第一次处理
注:每次有一个链表头节点走进
!
循环体,
只会在第一次的时候为
,因为后续会将非
的
"#
非
赋给了
,这样可以保证只有链表头节点才会赋给
)
''''''''''''''''''''1''*
把头节点赋给
''''''''''''''''',
Dylanu
- 粉丝: 43
- 资源: 9
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0