1. 导读

这次的分享是关于 HashMap ::put, 主要是围绕下面几个方面展开:

.1 HashMap::put源码解析;

.2 红黑树 插入的处理;

.3 红黑树与链表的互转;

2. HashMap::put源码解析

因为HashMap::put的源码较长, 用下面的流程图来替代:

下面我们一步步来分析:

.1 因为HashMap在初始化的时候, 没有初始化table, 所以在第一次插入时需要初始化table;

.2 判断table[(n – 1) & hash]是否为空, 如果为空则证明是首节点, 直接插入即可;

.3 若不为空, 则需判断挂载的是链表还是红黑树, 若是红黑树, 则走红黑树的插入;

.5 遍历链表, 如果key相同且hash相同, 则直接退出循环;

.6 如果已经到了尾节点, 则直接插入, 再判断链表的长度是否大于8; 若大于8需要转成红黑树;

.7 退出循环后再判断相同key能否覆盖, 能覆盖时直接覆盖, 并返回结果;

.8 插入完成后再判断HashMap.size 是否大于 threshold; 为真时需要扩容;

.9 HashMap::put正常插入的返回结果都为null;

.10 HashMap::put流程中的afterNodeAccess(), afterNodeInsertion()无需关注, 这是LinkedHashMap的处理;

HashMap::put的主流程还是比较清晰的, 但是在JAVA8以后加入了红黑树的处理, 我们需要关注下红黑树的插入与链表转红黑树的操作;

3. 红黑树的插入

HashMap.TreeNode::putTreeVal是红黑树插入的主逻辑:

.1 从根节点遍历槽点的红黑树;

.2 判断待插入节点位于左子树还是右子树, key相等时直接返回, 由主流程判断是否更新节点值;

.3 当遍历到当前节点的左(右)子节点为空时, 插入待插入节点;

.4 再次平衡红黑树;

判断节点位于左右子树的过程在前面的HashMap::get中已经详细的讲解过了, 先比较hash再比较key是否实现了Comparable接口;如果不实现时, 调用HashMap.TreeNode::tieBreakOrder, 我们来看下tieBreakOrder方法做了什么:

tie bread在网球比赛中叫做平局决胜, 如果把判断节点位于那颗子树作为比赛的话:

.1 比较节点的hash值是第一轮;

.2 通过Comparable比较是第二轮;

.3 如果前面两轮没有分出结果, 那么tieBreakOrder就作为决胜轮来比较出一个结果;

.4 当然如果key没有实现Comparable接口, 那么第一轮没结果就会直接进入决胜轮;

我们来看下作为决胜轮的tieBreakOrder方法是如何做到必定出结果的:

 static int tieBreakOrder(Object a, Object b) {
 int d;
 if (a == null || b == null ||
 (d = a.getClass().getName().
 compareTo(b.getClass().getName())) == 0)
 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
 -1 : 1);
 return d;
 }
 

.1 当两个对象都不为空时, 使用类名做比较; 因为JAVA中的类型是String, 而String实现了Comparable接口, 故可直接使用String::compareTo比较;

.2 当第一步的结果为0, 或者至少有一个对象为空时, 会调用System::identityHashCode来做比较;

.3 System::identityHashCode 与 Obejct::hashCode的区别是: 前者不能被重写, 而且当传入的对象为null时, 返回的结果是0; 所以即使两个对象都为null, 也可以通过 <= 返回一个 -1;

红黑树的再次平衡过程因为内容较多, 我们放到后面专门讲解; 接下来我们再看下链表转换为红黑树的过程:

4. 链表转红黑树

 final void treeifyBin(Node<K,V>[] tab, int hash) {
 int n, index; Node<K,V> e;
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode<K,V> hd = null, tl = null;
 do {
 TreeNode<K,V> p = replacementTreeNode(e, null);
 if (tl == null)
 hd = p;
 else {
 p.prev = tl;
 tl.next = p;
 }
 tl = p;
 } while ((e = e.next) != null);
 if ((tab[index] = hd) != null)
 hd.treeify(tab);
 }
 }
 

上面的代码是将链表升级为红黑树的主流程:

.1 通过遍历链表, 将链表节点转换为树节点(这时候还没设置左右子树以及颜色);

.2 设置节点的父节点与子节点, 这时候其实是将单向链表升级为 双向链表 ;

.3 调用HashMap.TreeNode::treeify给双向链表上色以及设置左右子树;

我们发现在链表升级为红黑树的主流程中, 先是将单向链表升级为双向链表, 并且设置父子节点; 但是我们不通过这步操作直接调用HashMap.TreeNode::treeify也可以实现链表转红黑树, 为什么要多此一举呢?

因为在HashMap中不仅有链表转红黑树, 也有红黑树转链表的操作, 上面转双向链表的操作其实是维护了当前的链表结构, 方便红黑树转链表;

HashMap.TreeNode::treeify的流程可以理解为遍历链表数据并插入红黑树, 所以HashMap.TreeNode::treeify的实现和红黑树的插入核心基本一致, 这里就不做重复叙述了;

本次分享到此结束了, 主要是分享了HashMap对红黑树插入的处理, 但是红黑树插入节点后再平衡的过程会放到下次分享;

如果看了本次对你有帮助, 烦请点赞转发, 感谢;