从 HashMap 获取可比键的时间

Question

AFAIK 自 java 8 桶结构已从链表更改为树。

因此，如果 hashCode() 方法 return 常量和我们的键 class 实现 Comparable 接口，那么从单个单元格获取元素的复杂度将从 O(n) 降低到 O(log n ).

我试了一下：

 public static void main(String[] args) {
    int max = 30000;
    int times = 100;
    HashMap<MyClass, Integer> map = new HashMap<>();
    HashMap<MyComparableClass, Integer> compMap = new HashMap<>();

    for(int i = 0; i < max; i++) {
        map.put(new MyClass(i), i);
        compMap.put(new MyComparableClass(i), i);
    }

    long startTime = System.nanoTime();
    for (int i = max; i > max - times; i--){
        compMap.get(new MyComparableClass(i));
    }
    System.out.println(String.format("Key is comparable:    %d", System.nanoTime() - startTime));

    startTime = System.nanoTime();
    for (int i = max; i > max - times; i--){
        map.get(new MyClass(i));
    }
    System.out.println(String.format("Key isn't comparable: %d", System.nanoTime() - startTime));
}

我的比较类：

public class MyComparableClass
        implements Comparable {
    public Integer value;

    public MyComparableClass(Integer value) {
        this.value = value;
    }

    @Override
    public int compareTo(Object o) {
        return this.value - ((MyComparableClass) o).value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        MyComparableClass myClass = (MyComparableClass) o;

        return value != null ? value.equals(myClass.value) : myClass.value == null;
    }

    @Override
    public int hashCode() {
        return 1;
    }
}

MyClass 与 MyComparableClass 相同，但未实现 Comparable 接口。

而且出乎意料的是，我总是得到这样的结果，即通过非可比键获取价值的时间少于通过可比键获取价值的时间。

Key is comparable:    23380708
Key isn't comparable: 10721718

谁能解释一下？

Answer 1

即使你的class没有可比性，它仍然使用二叉树！如中所述，它使用较低级别的方法来比较两个对象（例如 System.identityHashCode），您的结果可能是以下组合：

迭代次数不足，因此无法比较 JIT 编译版本。尝试颠倒时间（先进行非比较，然后进行比较），看看是否会得到不同的结果。使用 JMH 进行适当的基准测试。
调用您自己的 compareTo 方法不如 HashMap 内部使用的比较不可比较对象的方法快。
您也在计时内存分配器的性能，因为您正在创建一个新的 class 以在每次迭代中传递给 HashMap.get（尽管 JVM 最终会执行当 JIT 编译器启动时进行逃逸分析，并将其转换为堆栈分配）。

Answer 2

你的基准测试有一些缺陷，但在这种情况下，趋势仍然是可以接受的。您的代码的问题是您正在实现原始类型 Comparable，但是 HashMap 实现在决定使用它来解决散列冲突之前验证类型兼容性。

因此，在您的情况下，HashMap 实现中从未使用自然顺序，但是您的 class 实现原始类型 Comparable 会导致更昂贵的检查。看看 HashMap.comparableClassFor(Object x):

static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

您的密钥 class 未实现 Comparable，测试在 x instanceof Comparable 结束。对于另一个 class，这个相当便宜的 instanceof 测试评估为 true 并且对通用类型签名进行了更复杂的测试，然后将失败。而这个测试的结果并没有被记住，而是重复了不仅对每个key:

当你看HashMap.find时：

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;
}

你会看到在测试comparableClassFor失败后，递归调用find。它试图记住使用 kc 的测试结果并将其传递下去，但在失败的情况下它是 null 并且因此被视为尚未完成，换句话说，测试将在任何时候重复下降到子树中，但由于未使用自然顺序，因此如果在第一个子树中未找到密钥，则此代码也可能必须循环遍历其他子树，并在每次迭代中重复测试。

或者换句话说，在最坏的情况下，可能会对该桶中的每个元素重复此 comparableClassFor(k)。 JVM 优化甚至可能会改变结果以支持 class 不实现 Comparable，因为 JVM 可能会识别对同一关键对象重复的相同 instanceof 测试并优化它们，而通用类型签名的测试不是内部 JVM 操作，其结果不太可能得到预测。

当然，当您的 MyComparableClass 正确实施 Comparable<MyComparableClass> 时，结果会发生巨大变化。然后，使用自然顺序将时间复杂度从 O(n) 更改为 O(log n)，而且每次查找只进行一次测试，因为 then-non-null 结果将在 kc.

中被记住

从 HashMap 获取可比键的时间

Time for getting by comparable key from HashMap

java

hashtable

hashmap

java-8