Time for getting by comparable key from HashMap

Question

AFAIK since java 8 bucket structure was changed from linked list to tree.

So in case hashCode() method return constant and our key class implements Comparable interface then complexity to get element from single cell will be reduced from O(n) to O(log n).

I tried to check it:

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

MyComparableClass:

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 is the same as MyComparableClass but doesn't implement Comparable interface.

And unexpectedly i always get results where time for getting value by non comparable key less than by comparable.

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

Can someone explain?

Answer 1

您的基准存在一些缺陷，但在这种情况下，趋势仍然可以被承认。您的代码的问题在于您正在实现原始类型Comparable，但HashMap实现在决定使用它来解决哈希冲突之前会验证类型兼容性。

\n\n

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

\n\n

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

\n\n

对于未实现的关键类Comparable，测试立即结束x instanceof Comparable。对于另一个类，这个相当便宜的instanceof测试评估为true，并对泛型类型签名进行更复杂的测试，然后该测试将失败。并且这个测试的结果不会被记住，而是不仅对每个键重复：

\n\n

当你看HashMap.find：

\n\n

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {\n    TreeNode<K,V> p = this;\n    do {\n        int ph, dir; K pk;\n        TreeNode<K,V> pl = p.left, pr = p.right, q;\n        if ((ph = p.hash) > h)\n            p = pl;\n        else if (ph < h)\n            p = pr;\n        else if ((pk = p.key) == k || (k != null && k.equals(pk)))\n            return p;\n        else if (pl == null)\n            p = pr;\n        else if (pr == null)\n            p = pl;\n        else if ((kc != null ||\n                  (kc = comparableClassFor(k)) != null) &&\n                 (dir = compareComparables(kc, k, pk)) != 0)\n            p = (dir < 0) ? pl : pr;\n        else if ((q = pr.find(h, k, kc)) != null)\n            return q;\n        else\n            p = pl;\n    } while (p != null);\n    return null;\n}\n

\n\n

您将看到测试comparableClassFor失败后find会递归调用。kc它尝试使用并传递它来记住测试的结果，但在失败的情况下，它\xe2\x80\x99snull因此被视为尚未完成，换句话说，每当下降到子树时都会重复测试，但由于不使用自然顺序，如果在第一个子树中没有找到键，则此代码可能也必须循环遍历另一个子树，并且在每次迭代中重复测试。

\n\n

或者，换句话说，comparableClassFor(k)在最坏的情况下，可能会对该存储桶中的每个元素重复此操作。JVM 优化甚至可能会改变结果，有利于未实现的类Comparable，因为 JVM 可能会识别instanceof对同一关键对象的重复相同测试并对其进行优化，而泛型类型签名的测试不是固有的 JVM 操作，其结果不太可能被预测。

\n\n

当然，当你MyComparableClass正确实现时，结果会发生巨大变化Comparable<MyComparableClass>。然后，使用自然顺序将时间复杂度从 改为O(n)，O(log n)但每次查找只进行一次测试，因为 then-nonnull结果将被记住在 中kc。

\n