HashMap中对红黑树查找的源码分析

      红黑树的查找其实非常简单，你可能会被红黑树的创建和删除时要对节点进行旋转和调整节点颜色的那些东西吓到了，以为红黑树的查找也很难；其实不然~红黑树的查找和那些东西一点关系也没有。
      要讲红黑树，还是要提一下二叉搜索树，因为红黑树也可以说是二叉搜索树的一种变种树，他比二叉搜索树要稳定，不会退化成链表，是一种相对平衡的二叉搜索树，红黑树的5条定义，在构建红黑树时的各种 *** 作都是为了让其变得平衡；二叉搜索树的定义非常简单：当前节点的左子节点值小于当前节点的值，右子节点值大于当前节点的值；而红黑树也是一种二叉搜索树，当然也是满足这个定义；也就是说，对红黑树的查找其实就是对一个二叉搜索树的查找；

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

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

下图是寻找节点值：80 的过程

---

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

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

		// 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值相等，但是key不等，这就产生了hash冲突的情况；在这种情况下我们没能找到目标key只能继续往下搜索：就会遇到几种情况

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

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

   else if (pl == null)
      p = pr;
当前节点没有子节点，或者是当前节点只有右子节点时，都会进入这个分支；
当前节点没有子节点时，会直接结束循环；因为此时pr=null；   p= pr;  ====> p==null;循环条件P!=null,
当前节点只有一个右节点，则进入右节点继续寻找目标key；

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

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

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

3.该节点 有2个子节点

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

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

• 实现了Comparable接口（用来排序的）就会调用key的class类的排序方法比大小；用当前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接口，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;

实际上，后面三个分支完全覆盖了所有可能的情况；这样写感觉逻辑还要好一点。。（如果发现有错或者有不同的看法，希望可以评论区留言讨论）

---

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