时间戳

首页 > 解决方案 > 在 ConcurrentSkipListSet 中添加了重复项

java - 在 ConcurrentSkipListSet 中添加了重复项

问题描述

我正在尝试维护 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()”方法。但从排序集的角度来看，这并不重要。

感谢你的帮助。

标签： javaconcurrentskiplistmap

解决方案

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.

推荐阅读