HashMap中对红黑树find()的源码分析

布满荆棘的人生 2023-09-29 14:28 16阅读 0赞

要讲红黑树的搜索，还是要提一下二叉搜索树，因为红黑树也可以说是二叉搜索树的一种变种树，他比二叉搜索树要稳定，不会退化成链表，是一种相对平衡的二叉搜索树，红黑树的5条定义，在构建红黑树时的各种操作都是为了让其变得平衡；**二叉搜索树的定义非常简单：当前节点的左子节点值小于当前节点的值，右子节点值大于当前节点的值；而红黑树也是一种二叉搜索树，当然也是满足这个定义；也就是说，对红黑树的查找其实就是对一个二叉搜索树的查找；**  
  
就算不知道二叉搜索树也没关系，看下面2个例子就可以了解二叉搜索树的搜索过程了；

![二叉搜索树][d01e03e13b104eed94cef205cda4312b.png_pic_center]  
这是一颗二叉搜索树，现在我们要查询节点值为：80 的节点；对所有搜索树的查找值都是从root节点开始搜索；根据二叉搜索树的性质用要查找的目标值与当前节点值比较决定搜索的分支；

*  比当前节点值大，到右分支中搜索；
 *  比当前节点值小，到左分支中搜索；
 *  和当前节点值相等，返回当前节点；
 *  如果到叶子节点都没能找到目标值；则说明要搜的值不存在直接返回null

下图是寻找节点值：80 的过程  
  
  
  
  
  
  
![在这里插入图片描述][d0bd07d8e69e49b889717701ced0c391.png_pic_center]

--------------------

现在查找节点值为：175的搜索过程

![在这里插入图片描述][527eda62290540ed9b8f55f037d32bad.png_pic_center]  
上面列举了2个例子，对二叉搜索树的查找做了说明；其实在HashMap中对红黑树的搜索也是这么一个过程；心里面有这个图，然后再来看hashmap中关于对红黑树搜索的源码就会发觉其实没那么难；

**在HashMap的红黑树中不是直接以key作为排序关键字来判断key的大小，而是以key的hash值作为排序的关键字来判断key的大小；当key的hash值相同时（hash 冲突），有2大类情况：**

*  key实现了Comparable接口，比较key大小，决定搜索分支；
 *  key没有实现Comparable接口，没法直接比较key大小，因此会搜索当前节点的左右分支；

find源码：

--------------------

// k：搜索的目标； 
    		// h:目标key的hash值 ；
    		// kc ：key的class对象
            final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        
                TreeNode<K,V> p = this;
                do {
        
                    int ph, dir; K pk;
                    //pl:当前节点的左子节点
                    //pr :当前节点的右子节点
                    TreeNode<K,V> pl = p.left, pr = p.right, q;
                    //ph:当前节点的hash
                    if ((ph = p.hash) > h)//case1 : 小于当前hash，继续在左子节点搜索
                        p = pl;
                    else if (ph < h)//case 2 ：大于当前hash，继续在右子节点中搜索
                        p = pr;
                        // case 3:等于当前hash值，并且(当前节点key值)pk == k(目标key)；直接返回当前节点
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
                        //下面几种情况都是 hash冲突了（hash相等），但是key不相等的情况
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
                return null;
            }

--------------------

### 产生hash冲突之后源码的分析 ###

hash冲突之后的分支比较多，单独把hash冲突的部分代码提出来分析：

上面我们分析到了当hash值相等，但是key不等，这就产生了hash冲突的情况；在这种情况下我们没能找到目标key只能继续往下搜索：就会遇到几种情况

##### 0.该节点没有子节点（左右子节点都为null，pl=null,pr=null） #####

进入pl=null的分支，并且会结束循环，因为此时pr=null； p= pr; --------> p==null;循环条件P!=null；

else if (pl == null)
          p = pr;

##### 1.该节点只有 right节点(pl=null) #####

进入pl=null的分支只有右分支，因此会进入右分支继续搜索key

else if (pl == null)
          p = pr;

##### 2.该节点只有 left节点(pr==null) #####

当前节点只有一个左节点，则进入左节点中继续寻找目标key

else if (pr == null)
           p = pl;

##### 3.该节点 有2个子节点 #####

这个时候，就需要对选择一条分支进行搜索。那我们要选择哪一条分支呢？

当发生hash冲突之后，没法靠hash值决定搜索路径，这个时候会依据key的大小来决定搜索路径。因为key是object，如果没有实现Comparable接口就没法比大小，因此首先需要查看key的class类有没有实现Comparable接口

*  实现了Comparable接口（用来排序的）就会调用compareTo(key1,key2)方法比大小；用当前节点key与目标key比大小决定去哪个分支（这其实与前面比较hash决定分支是一样的）
 *  没有实现Comparable接口，无法比较key值的大小；因此两个分支都需要查找；先找右分支（pr）如果在右边没找到，再找左边分支（pl）

//利用key的class类实现的比大小的方法，比较key的大小，然后决定查找的分支
    else if ((kc != null ||
            (kc = comparableClassFor(k)) != null) &&
            (dir = compareComparables(kc, k, pk)) != 0)
                 p = (dir < 0) ? pl : pr;
    //没有实现Comparable接口，或者实现了接口但是比较结果dir=0都会检测左右分支，q = pr.find(h, k, kc)检查右分支；q,是右分支查询结果；q!=null在右分支中找到了目标key,
     else if ((q = pr.find(h, k, kc)) != null)
                 return q;
      else//q==null,查询左分支；
         p = pl;

--------------------

#### 分析 ####

通过上面的一通分析之后，感觉它hash冲突之后的代码写的有点多余；当hash冲突之后，不用管该节点是否有几个分支；

首先应该看key的class类是否实现了Comparable接口；

*  实现了直接就比key的大小；通过判断key值的大小决定去哪个分支
 *  没有实现接口，将左右分支全部排查完

重写hash冲突之后的代码

else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
    		                    
    			                    ||
    			                    ||
    			                    ||
    			                    ||
    			                    ||
    			                    || 
    			                    \/
    
    				//检查是否实现了排序接口，实现了排序接口，就用key比大小决定搜索分支
    				
    				else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
    				//没有实现排序接口，这个时候需要左右分支都搜索
    				else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;

实际上后面三个分支完全覆盖了所有可能的情况；（ps：如果发现有错或者有不同的看法，希望可以评论区留言讨论）

--------------------

#### 后续 ####

我们可以注意到当key没有实现Comparable接口时，当发生hash冲突时没法判断应该搜索哪个分支hashmap会递归的将左右分支全部搜索一遍，如果当key的hash冲突比较严重的话，就会严重影响到搜索的效率；因此作为key的类应该实现Comparable接口，这样即使发生了hash冲突也能快速查找key；

--------------------

[d01e03e13b104eed94cef205cda4312b.png_pic_center]: https://img-blog.csdnimg.cn/d01e03e13b104eed94cef205cda4312b.png#pic_center
[d0bd07d8e69e49b889717701ced0c391.png_pic_center]: https://img-blog.csdnimg.cn/d0bd07d8e69e49b889717701ced0c391.png#pic_center
[527eda62290540ed9b8f55f037d32bad.png_pic_center]: https://img-blog.csdnimg.cn/527eda62290540ed9b8f55f037d32bad.png#pic_center