PS:由于文档是我在本地编写好之后再复制过来的,有些文本格式没能完整的体现,故提供图片,供大家阅览,以便有更好的阅读体验:
一、源码思路解读:先将链表节点转为树节点,再将都是红黑树节点的链表转为红黑树。
分析HashMap的put方法的源码时发现,当HashMap中某个链表上存储的元素个数达到TREEIFY_THRESHOLD(树化阈值)=8个时,会调用treeifyBin方法尝试将该链表转换成红黑树。
(PS:为什么说是尝试,而不是直接转呢?因为,在做转换之前,还会对HashMap的数组的长度进行判断,当HashMap数组长度达到MIN_TREEIFY_CAPACITY(树化最小容量,HashMap数组的长度)=64时,才会进行链表到红黑树的转换;否则,只进行扩容。)
(PS:为什么树化最小容量MIN_TREEIFY_CAPACITY是64呢,源码中该常量注释里有具体说明:The smallest table capacity for which bins may be treeified. (Otherwise the table is resized if too many nodes in a bin.) Should be at least 4 TREEIFY_THRESHOLD to avoid conflicts between resizing and treeification thresholds.
表(数组)被树化的最小树容量.(否则表(数组)应该被扩容如果太多节点在桶里)应该至少4倍的尝试树化阈值,以避免扩容和树化阈值之间的冲突)
*概括起来,将链表转为红黑树主要有以下处理:
- 判断链表中存储的元素个数是否到达树化阈值8,没达到不往下处理
- 判断HashMap数组长度(桶bucket个数)是否达到树化最小容量64,没达到扩容,否则转红黑树
- 将需要树化的链表中的所有节点替换成树节点
- 将所有节点已经是红黑树节点的链表转为红黑树
二、完整文档图片