1

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

// 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()”方法。但从排序集的角度来看，这并不重要。

感谢你的帮助。

4

4 回答 4

2

In your compareTo-implementation you are mixing two different properties in an illegal way. Thus you break the contract of the Comparable interface.

In your comparison, you look at the index only if the values are not equal. This way you do not define an overall natural order for your items. Depending on what comparison is done first, the result of sorting a list will be random.

    @Override
    public int compareTo(Item o) {
        int vCompare = this.value.compareTo(o.value);
        if (vCompare == 0) {
            return  this.index - o.index;
        }
        return vCompare;
    }

This implementation will first compare by value and then by index. It adheres to the Comparable contract and actually defines a natural order for Items and works fine with the Set implementation.

Caution: This sample implementation will break the tests. The tests are there to show the code behaves as intended. But in this case the intended behavior is the actual issue.

  • It is incompatible with the Comparable contract.
  • You cannot sort a list by numeric index and expect a lookup by alphabetical value to succeed. But that's exactly what is attempted here. Sort by index but find duplicate names. It does not work this way.
于 2019-05-14T11:30:14.910 回答
2

您违反了 的合同compareTo，这会导致未定义的行为。

最后，实现者必须确保对于所有 z 都x.compareTo(y)==0意味着。sgn(x.compareTo(z)) == sgn(y.compareTo(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

迹象不同，因此合同已被破坏。

于 2019-05-14T11:23:23.100 回答
0

我不详细了解 ConcurrentSkipListSet 的实现，但看起来您需要重写类的 equals 方法来指定使两个对象相等的条件。

于 2019-05-14T11:06:24.533 回答
0

这不是答案，而是基于@Michael 和@Jochen 发现的根本原因来实现目标的解决方案。将类比较器修改Item为以下以具有value字符串的自然顺序。

public int compareTo(Item o) {
   return this.value.compareTo(o.value);
}

然后，添加了一个基于索引的比较器来实现FIFO检索。

// This iterator would now be used in assertItems() method in main class.
private Iterator<Item> getFIFOIterator() {
        ArrayList<Item> list = new ArrayList<>(set);
        list.sort(Comparator.comparingInt(Item::getIndex));
        return list.iterator();
    }

@Michael 和@Jochen：感谢您花时间找出根本原因。

于 2019-05-15T08:06:57.380 回答