В ConcurrentSkipListSet добавлены дубликаты

Question

Я пытаюсь сохранить порядок вставки в ConcurrentSkipListSet. Добавляемый элемент - это пользовательский тип класса со свойствами value (String) и index (int). Он реализует сопоставимый интерфейс. Набор ведет себя очень противоречиво, иногда добавляя дубликаты предметов. Элементы считаются дублирующими, если они имеют одинаковое значение.

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

Ожидается: передано для: [гггг, bbbb, аааа]

Фактически: не удалось: [гггг, bbbb, гггг, аааа]

Но, как упоминалось ранее, результат очень противоречивый. В большинстве случаев это проходит. Пожалуйста, дайте знать, что может быть причиной такого поведения. Является ли метод «CompareTo ()» неправильным? Если это так, он всегда должен потерпеть неудачу.

В идеале мы должны также переопределить метод equals (). Но это не имеет значения с точки зрения отсортированного набора.

Ценю вашу помощь.

Answer 1

В вашей реализации compareTo вы смешиваете два разных свойства незаконным образом. Таким образом вы нарушаете контракт Сопоставимого интерфейса.

При сравнении вы смотрите на индекс только в том случае, если значения не равны. Таким образом, вы не определяете общий естественный порядок для ваших предметов. В зависимости от того, что сравнение выполняется первым, результат сортировки списка будет случайным.

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

Эта реализация будет сначала сравниваться по значению, а затем по индексу. Он придерживается контракта Comparable и фактически определяет естественный порядок для Предметов и прекрасно работает с реализацией Set.

Внимание: этот пример реализации сломает тесты. Тесты показывают, что код ведет себя так, как задумано. Но в этом случае предполагаемое поведение является актуальной проблемой.

• Несовместимо с сопоставимым договором.
• Вы не можете отсортировать список по числовому индексу и ожидать, что поиск по алфавиту будет успешным. Но это именно то, что здесь делается. Сортировать по индексу, но найти повторяющиеся имена. Это не работает таким образом.

Answer 2

Вы нарушили контракт compareTo, что привело к неопределенному поведению.

Наконец, разработчик должен убедиться, что x.compareTo(y)==0 означает, что sgn(x.compareTo(z)) == sgn(y.compareTo(z)),для всех 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

Знаки разные, поэтому договор расторгнут.

Answer 3

Это не ответ, а решение для достижения цели, основанное на поиске первопричин @Michael и @Jochen.Изменен компаратор класса Item, приведенный ниже, чтобы он имел естественный порядок value String.

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: благодарю вас за то, что вы нашли время и выяснили причину.

Answer 4

Я не знаю подробно реализации ConcurrentSkipListSet, но похоже, что вам нужно переопределить метод equals вашего класса, чтобы указать, какие два объекта квалифицируются как равные.