JDK java.util.concurrent.ConcurrentSkipListSet.equals(Object o) 执行效率

Question

java.util.concurrent.ConcurrentSkipListSet在JDK中的equals实现如下

public boolean equals(Object o) {
    // Override AbstractSet version to avoid calling size()
    if (o == this)
        return true;
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    try {
        return containsAll(c) && c.containsAll(this);
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

但我认为下面的代码似乎更有效率

public boolean myEquals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != this.size()) {
        return false;
    }

    Iterator ic = c.iterator();
    Iterator id = iterator();

    while (ic.hasNext() && id.hasNext()) {
        if (!ic.next().equals(id.next())) {
            return false;
        }
    }

    return true;
}

一个简单的测试也可能支持第二个 equals

public class Test {
    public static void main(String[] args) {
        ConcurrentSkipListSet<Integer> set1 = new ConcurrentSkipListSet<Integer>();
        ConcurrentSkipListSet<Integer> set2 = new ConcurrentSkipListSet<Integer>();

        for (int i = 0; i < 10000000; i++) {
            set1.add(i);
            set2.add(i);
        }

        long ts = System.currentTimeMillis();
        System.out.println(set1.equals(set2));
        System.out.println(System.currentTimeMillis() - ts);

        ts = System.currentTimeMillis();
        System.out.println(myset1.myEquals(myset2));
        System.out.println(System.currentTimeMillis() - ts);
    }
}

输出结果

true
2713
true
589

在 JDK 评论中说，This definition ensures that the equals method works properly across different implementations of the set interface. 谁能解释一下？

Answer 1

作为参考，OpenJDK thread resulted in creating JDK-8181146 ConcurrentSkipListSet.equals efficiency.

In the JDK comment it says, This definition ensures that the equals method works properly across different implementations of the set interface. Could anyone kindly explain this?

来自Set.equals(Object)。根据文档：

Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set). This definition ensures that the equals method works properly across different implementations of the set interface.

这意味着 Set.equals 实现应该由 Set.contains(Object). Which then leads you to this verbiage from the java.util.SortedSet:

的行为来定义

Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface. (See the Comparable interface or Comparator interface for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

那么为什么 ConcurrentSkipListSet 中的 'this contains that and that contains this'？首先你想避免调用 ConcurrentSkipListSet.size() 因为：

Beware that, unlike in most collections, this method is NOT a constant-time operation. Because of the asynchronous nature of these sets, determining the current number of elements requires traversing them all to count them. Additionally, it is possible for the size to change during execution of this method, in which case the returned result will be inaccurate. Thus, this method is typically not very useful in concurrent applications.

第二个原因是你想成为'consistent with equals'.

让我们根据你的代码做一个残酷的例子：

private static boolean myEquals(Set o1, Set o2) {
    if (o1.size() == 1 && o2.size() == 1) {
        Iterator ic = o2.iterator();
        Iterator id = o1.iterator();

        while (ic.hasNext() && id.hasNext()) {
            if (!ic.next().equals(id.next())) {
                return false;
            }
        }
        return true;
    }
    return o1.equals(o2);
}

public static void main(String[] args) {
    print(skiplist(new BigDecimal("1.0")), tree(new BigDecimal("1.00")));
    print(skiplist(new BigDecimal("1.0")), hash(new BigDecimal("1.00")));
    print(skiplist(new BigDecimal("1.0")), identity(new BigDecimal("1.00")));
    print(skiplist(BigDecimal.ONE), identity(new BigDecimal(BigInteger.ONE, 0)));
}

private static Collection<BigDecimal> e() {
    return Arrays.asList(new BigDecimal("1.0"));
}

private static <E> Set<E> hash(E... e) {
    return new HashSet<>(Arrays.asList(e));
}

private static <E> Set<E> skiplist(E... e) {
    return new ConcurrentSkipListSet<>(Arrays.asList(e));
}

private static <E> Set<E> tree(E... e) {
    return new TreeSet<>(Arrays.asList(e));
}

private static <E> Set<E> identity(E... e) {
    Set<E> s = Collections.newSetFromMap(new IdentityHashMap<E, Boolean>());
    Collections.addAll(s, e);
    return s;
}

private static void print(Set o1, Set o2) {
    System.out.println(o1.getClass().getName()
            + "==" + o2.getClass().getName() + ": "
            + o1.equals(o2) + ": " + myEquals(o1, o2));
    System.out.println(o2.getClass().getName()
            + "==" + o1.getClass().getName() + ": " + o2.equals(o1)
            + ": " + myEquals(o2, o1));
}

输出：

java.util.concurrent.ConcurrentSkipListSet==java.util.TreeSet: true: false
java.util.TreeSet==java.util.concurrent.ConcurrentSkipListSet: true: false
java.util.concurrent.ConcurrentSkipListSet==java.util.HashSet: false: false
java.util.HashSet==java.util.concurrent.ConcurrentSkipListSet: false: false
java.util.concurrent.ConcurrentSkipListSet==java.util.Collections$SetFromMap: false: false
java.util.Collections$SetFromMap==java.util.concurrent.ConcurrentSkipListSet: false: false
java.util.concurrent.ConcurrentSkipListSet==java.util.Collections$SetFromMap: false: true
java.util.Collections$SetFromMap==java.util.concurrent.ConcurrentSkipListSet: false: true

该输出表明新的实现不会是 consistent with equals:

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

现在我们可以通过将元素检查替换为 ((Comparable) e1).compareTo((Comparable) e2) != 0 或 Comparator.compare(e1, e2) != 0 并添加检查以尝试确定这两个集合使用相同的顺序，但请记住集合可以被包装并且没有什么可以阻止来自 hiding the fact that a set is backed by sorted set 的调用者。现在你回到了 equals 的 'this contains that and that contains this' 实现，它可以处理集合包装器。

'this contains that and that contains this' 实现的另一个不错的 属性 是 equals 实现不会为给定的集合创建一个迭代器对象，在最坏的情况下可能会有像 Arrays.asList(s.toArray()).iterator() 这样的实现在引擎盖下。

如果不放宽规范，放宽现有行为，或添加 returns 一个 BiPredicate 的收集方法来捕获收集的 'equivalence relationship'，我认为很难将这样的优化添加到 JDK.