java 8 HashMap中使用哪种树类型？

Question

正如我所知,在java8中HashMap的桶实现有所改变.如果桶大小超过某个值,则列表转换为"平衡树".

我不明白
1. Oracle JDK中使用什么类型的平衡树？(AVL？red-black？类似于索引数据库？)
2.是二叉树吗？
据我所知,排序是根据哈希码执行的.例如,在我的桶中,我有102个元素.带有hashcode的100个值12(我明白它值得但我只需要理解这个行为)和2带有hashcode 22.
如何执行搜索值？

Answer 1

看一下实现,它看起来像一棵二叉树.更具体地说,下面的评论表明它是一棵红黑树:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

至于处理相同的哈希码,这在Javadoc中解决:

树容器(即,其元素都是TreeNode的容器)主要通过hashCode排序,但在tie的情况下,如果两个元素具有相同的" class C implements Comparable<C>"类型,那么它们的compareTo方法用于排序.

据说TreeNode使用的s的HashMap结构类似于TreeMap.

您可以在TreeNode此处查看搜索包含所需密钥的实现:

    /**
     * Finds the node starting at root p with the given hash and key.
     * The kc argument caches comparableClassFor(key) upon first use
     * comparing keys.
     */
    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;
    }

如您所见,这类似于标准二叉搜索树搜索.首先,他们搜索与搜索到的密钥TreeNode相同hashCode的密码(因为a的单个桶HashMap可能包含具有不同hashCodes的条目).然后继续进行,直到找到TreeNode具有等于​​所需密钥的密钥.compareTo如果密钥的类实现,则辅助搜索使用Comparable.否则,执行更详尽的搜索.