飞利浦·斯塔克|重温数据结构经典：HashMap原理( 二 )

(6) 链表树化

链表树化的条件有两点；链表长度大于等于8、桶容量大于64 ，否则只是扩容，不会树化。
链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗平衡树。同时在树转换过程中会记录链表的顺序， tl.next = p ，这主要方便后续树转链表和拆分更方便。
链表转换成树完成后，再进行红黑树的转换。先简单介绍下，红黑树的转换需要染色和旋转，以及比对大小。在比较元素的大小中，有一个比较有意思的方法， tieBreakOrder加时赛，这主要是因为HashMap没有像TreeMap那样本身就有Comparator的实现。

(7) 红黑树转链在转换树的过程中，记录了原有链表的顺序，红黑树转链表时候，直接把TreeNode转换为Node ，因为记录了链表关系，所以替换过程很容易。
(8) 查找

扰动函数的使用，获取新的哈希值
下标的计算，tab[(n - 1) & hash
)
确定了桶数组下标位置，接下来就是对红黑树和链表进行查找和遍历操作了

(9) 删除

删除的操作也比较简单，没有太多的复杂的逻辑。
另外红黑树的操作因为被包装了，只看使用上也是很容易。

(10) 遍历

这里我们要设定一个既有红黑树又有链表结构的数据场景
为了可以有这样的数据结构，我们最好把 HashMap 初始长度设定为 64 ，避免在

链表超过 8 位后扩容，而是直接让其转换为红黑树。

找到 18 个元素，分别放在不同节点(这些数据通过程序计算得来)；
桶数组 02 节点：24、46、68
桶数组 07 节点：29
桶数组 12 节点：150、172、194、271、293、370、392、491、590

测试代码

添加元素，在 HashMap 还是只链表结构时，输出测试结果 01
添加元素，在 HashMap 转换为红黑树的时候，输出测试结果 02
删除元素，在 HashMap 转换为链表结构时，输出测试结果 03

结果如下：
排序01：
24 46 68 29 150 172 194 271

排序02：
24 46 68 29 271 150 172 194 293 370 392 491 590

排序03：
24 46 68 29 172 271 150 194
Process finished with exit code 0

这一篇 API 源码以及逻辑与上一篇数据结构中扰动函数、负载因子、散列表实现等，内容的结合，算是把 HashMap 基本常用技术点，梳理完成了。但知识绝不止于此，这里还有红黑树的相关技术内容，后续会进行详细。
除了 HashMap 以外还有 TreeMap、ConcurrentHashMap 等，每一个核心类都有一与之相关的核心知识点，每一个都非常值得深入研究。这个烧脑的过程，是学习获得的知识的最佳方式。
【飞利浦·斯塔克|重温数据结构经典：HashMap原理】可能关于 HashMap 还有一些疏漏的点，也希望阅读的小伙伴可以提出更多的问题，互相学习，共同进步，本文就到这里，感谢您的阅读！