java - 在 ConcurrentSkipListSet 中添加了重复项

Question

我正在尝试维护 ConcurrentSkipListSet 中的插入顺序。正在添加的项目是具有 value(String) 和 index (int) 属性的自定义类类型。它实现了 Comparable 接口(interface)。该集合的行为非常不一致，有时会添加重复的项目。如果项目具有相同的值，则认为它们是重复的。

// This is the Item class being added in the set.
final class Item implements Comparable<Item> {
        private String value;
        private int index;

        Item(String val, int idx) {
            this.value = val;
            this.index = idx;
        }

        @Override
        public int compareTo(Item o) {
            // returns zero when values are equal indicating it's a duplicate item.
            return this.value.equals(o.value) ? 0 : this.index - o.index;

        }
        @Override
        public String toString() {
            return this.value;
        }
    }

// Below is the main class.
public class Test {

    ConcurrentSkipListSet<Item> set;
    AtomicInteger index;

    public Test() {
        set = new ConcurrentSkipListSet<>();
        index = new AtomicInteger(0);
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            Test test = new Test();
            test.addItems();
            test.assertItems();
        }
    }

//trying to test it for 10 times. It always fails for once or twice.
    private void assertItems() {
        Iterator<Item> iterator = set.iterator();
        String[] values = {"yyyy", "bbbb", "aaaa"};
        for (String value : values) {
            if (!value.equals(iterator.next().toString())) {
                System.out.println("failed for :" + set);
                return;
            }
        }
        System.out.println("passed for :" + set);
    }

    //adding items with some duplicate values
    private void addItems() {
        set.add(new Item("yyyy", index.getAndIncrement()));
        set.add(new Item("bbbb", index.getAndIncrement()));
        set.add(new Item("yyyy", index.getAndIncrement()));
        set.add(new Item("aaaa", index.getAndIncrement()));
    }

预期:通过:[yyyy, bbbb, aaaa]

实际:失败:[yyyy, bbbb, yyyy, aaaa]

但如前所述，结果很不一致。大多数时候，它会过去。请告知此行为的可能原因。 “compareTo()”方法是否错误？如果是这样，它应该总是失败。

理想情况下，我们也应该覆盖“equals()”方法。但从有序集的角度来看，这并不重要。

感谢您的帮助。

Answer 1

你坏了the contract of compareTo ，这会导致未定义的行为。

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

通过将项目拉出到变量中，您可以很容易地看到您未满足此要求:

final Item x = new Item("yyyy", index.getAndIncrement());
final Item z = new Item("bbbb", index.getAndIncrement());
final Item y = new Item("yyyy", index.getAndIncrement());

System.out.println(x.compareTo(y));
System.out.println(x.compareTo(z));
System.out.println(y.compareTo(z));

输出:

0
-1
1

标志不同，因此契约(Contract)已被破坏。