博客

//HashMap中红黑树的查找函数find()实现
/**
         * 调用树的find()函数
         */
        final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

/**
         * 从根节点p开始查找指定hash值和关键字key的结点
         * 当第一次使用比较器比较关键字时，参数kc储存了关键字key的 比较器类别
         */
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)			//如果给定哈希值小于当前节点的哈希值，进入左节点
                    p = pl;
                else if (ph < h)				//如果大于，进入右结点
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))	//如果哈希值相等，且关键字相等，则返回当前节点
                    return p;
                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;
        }