Duplicate items added in ConcurrentSkipListSet

Question

I am trying to maintain insertion order in ConcurrentSkipListSet. The item being added is a custom class type with value(String) and index (int) properties. It implements Comparable interface. The set behaves very inconsistently, sometimes adding duplicate items. Items are considered duplicate if they have same value.

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

Expected : passed for :[yyyy, bbbb, aaaa]

Actual : failed for :[yyyy, bbbb, yyyy, aaaa]

But as mentioned before, the result is very inconsistent. Most of the times, it passes. Please let know what could be the reason for this behavior. Is the 'compareTo()' method wrong? If so, it should always fail.

Ideally we should override 'equals()' method also. But it doesn't matter from sorted set perspective.

Appreciate your help.

Answer 1

I don't know the implementation of ConcurrentSkipListSet in detail, but it looks like you need to override the equals method of your class to specify what qualifies two objects to be equal.

Answer 2

You have broken the contract of compareTo, which results in undefined behaviour.

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

You can easily see that you fail this requirement by pulling your Items out into variables:

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

Output:

0
-1
1

The signs are different, therefore the contract has been broken.

Answer 3

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.

Answer 4

This is not an answer, rather a solution to achieve the objective based on root cause finding by @Michael and @Jochen. Modified the Item class comparator to below to have natural order of value String.

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

And then, added an index based comparator to achieve FIFO retrieval.

// 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 and @Jochen : Appreciate you for taking your time and figuring out the root cause.