Множества (Sets). HashSet, LinkedHashSet

Список (List) хранит все элементы, которые в него добавили. Множество (Set) хранит только уникальные элементы. Повторяющиеся элементы просто не добавляются во множество.

Set<Integer> intSet = new HashSet<>(Arrays.asList(1, 1, 2, 3, 5, 8, 13, 21));
System.out.println(intSet);
// [1, 2, 3, 5, 21, 8, 13]

Метод add у множеств возвращает true, если элемент был добавлен, и false, если он уже есть во множестве.

System.out.println(intSet.add(21)); // false
System.out.println(intSet.add(34)); // true
System.out.println(intSet.add(34)); // false

Порядок

HashSet хранит элементы таким образом, что элемент можно очень быстро найти. Методы contains и indexOf у ArrayList проходят последовательно по элементам списка в поисках нужного элемента, а метод contains у HashSet ищет элемент многократно быстрее, так как использует совсем другой подход: каждый элемент находится в так называемой «корзине» (на иллюстрации — 16 серых корзин), которая выбирается исходя из значения самого элемента (на иллюстрации — 7 зелёных элементов множества).

Внутренности HashSet

Тема и проблематика хэш-корзин рассмотрена в презентации Джейка Уортона Exploring Java Hidden Costs (Неявные преграды производительности Java).

Если нужно сохранить тот порядок, в котором элементы были добавлены во множество, можно использовать LinkedHashSet — реализацию Set, которая хранит порядок добавления элементов.

Set<Integer> intSet = new LinkedHashSet<>(Arrays.asList(1, 1, 2, 3, 5, 8, 13, 21));
System.out.println(intSet);
// [1, 2, 3, 5, 8, 13, 21]

Внутренности LinkedHashSet

Доступ по индексу

Множество, как и список, и любую коллекцию (и не только) можно обойти в цикле for-each:

for (Integer number : intSet) {
    System.out.println(number);
}

Но вот доступ по индексу (порядковому номеру) (list.get) есть только у List, у Set этого метода нет. Это связано с тем, что порядок элементов во множестве не определён.

LinkedHashSet хоть и позволяет обходить элементы в порядке их добавления, но доступ к n-ому элементу потребовал бы обход всех предыдущих элементов. Множества просто не предназначены для порядкового доступа. При необходимости можно создать список из множества: new ArrayList(someSet);.

Комментарии к уроку

Сообщить об ошибке