LinkedHashSet итерации не в порядке возрастания?

Question

В следующем коде, если параметр равен {1,3,2}, в цикле while i равен 1, 3, 2.

Я уже использую LinkedHashSet, почему порядок не 1, 2, 3? Что еще мне нужно сделать, чтобы сделать итерацию в порядке возрастания?

Не можете использовать TreeSet как это add, remove, contains() в о (журнал N) времени.

public static void iterate(int[] num) {
    LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();

    for (int i : num) {
        set.add(i);
    }

    Iterator<Integer> iter = set.iterator();
    while (iter.hasNext()) {
        // WHY IS i THE SAME ORDER AS INSERATION ORDER, NOT ASSENDING ORDER?
        int i = iter.next();
    }
}

Answer 1

Потому что LinkedHashSet выполняет итерацию в порядке вставки и не сортируется! Из Javadoc:

Эта реализация отличается от HashSet тем, что поддерживает двусвязный список, проходящий через все его записи. Этот связанный список определяет порядок итераций, который является порядком, в котором элементы были вставлены в набор (порядок вставки).

Вы захотите использовать TreeSet для отсортированного набора, взгляните на отсортированный набор javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html

Answer 2

Итак, вы хотите HashSet для быстрого contains и правильно увидел, что LinkedHashSet поддерживает дополнительную структуру данных, к сожалению, для упорядочения путем вставки.

Если приведенный выше код показывает все вставки, вы можете отсортировать вставленные данные заранее:

Arrays.sort(num);
Collections.addAll(set, num);

Более общим решением было бы скопировать набор в новую коллекцию и отсортировать его.

Если числа находятся в определенном диапазоне, особенно положительном, а не разреженном, вы можете использовать BitSet. Это действительно эффективное решение, если применимо.

Answer 3

Нет реализации Java, которая выполняет сортировку перед возвратом итератора. Есть только реализации вроде TreeSet которые сортируются из-за их структуры данных.

В какой-то момент сортировка должна быть сделана. Не может быть (Hash-) реализации, которая поддерживает постоянное время adding а также getting и будучи по сути отсортированы. Если бы что-то подобное существовало, мы могли бы сортировать в постоянном времени.

Если вы хотите остаться с Hash-Выполнение, то вы должны выполнить "сортировку" непосредственно до / после извлечения элементов. Поскольку вы не можете изменить before Единственное решение состоит в том, чтобы отсортировать after извлечение элементов.

Пример кода с заказом Guava:

while (Integer i : Ordering.natural().sortedCopy(hashSet)) {
    // "i" in sorted order
}