Java HashMap类源码解析(续)-TreeNode
由于TreeNode本身是红黑树的实现,所以在分析TreeNode的之前我还是摸了一篇算法导论里红黑树的读书笔记:算法导论——红黑树,从伪代码行数也可以看出完整的红黑树的插入和删除操作代码是很长的,下面源码分析部分的行数就更多了,所以所谓手写红黑树画个图分析下逻辑还行,手写代码估计要写死(滑稽) TreeNode从JDK8开始引入,作用是当HashMap解决冲突的链表长度超过了8时,生成一个红黑树来加速查找和插入,这里树结构存在并不影响本身依然存在线性链表结构,意思是Node.next这个属性依然有效,所以说树替换了线性链表依然还是链表法解决冲突,只不过链表的实现策略换了。当结点因为移除或分裂操作少于6个时,消除树结构。虽然生产树之后能加快查找插入和删除,但是建立和消除树本身是存在消耗的,所以在两个临界值之间来回插入和删除会导致开销快速增加。HashMap的源码分析见:Java HashMap类源码解析 红黑树是基于二叉搜索树扩展而来,对于TreeNode来说排序的依据是结点的hash值,若相等然后比较key值,若key不能比较或是相等则根据hash值,左儿子的hash值小于等于父亲,...