Set

Проработать

  1. HashSet в Java
  2. Как не стоит работать с HashSet в Java?

Что это

Set(множество) - коллекция в которой элементы хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов.

Особенности

  1. Не возможны дубликаты.
  2. Не имеет методов для получения элементов.

Основные реализации

  1. HashSet
  2. TreeSet
  3. LinkedHashSet
  4. CopyOnWriteArraySet - это потокобезопасный вариант of ArrayList, но буз дубликатов. Разница в том, что все мутативные операции, такие как add, set, remove, clear... создают новую копию массива.
  5. ConcurrentSkipListSet - set на базе ConcurrentSkipListMap.

HashSet

HashSet - реализация интерфейса Set на основе HashMap.

Внутри использует HashMap(значение помещается в Key а в Value объект пустышка(new Object())).

Элементы хранятся в односвязном списке.

Не гарантирует порядок элементов.

Метод add() возвращает true - был ли заменён объект.

Позволяет добавить (null).

Set

Как получить значение из Hashset? Вызвать его Iterator или использовать метод toArray()

Сложность алгоритмов

  1. Получение - если нет коллизии - O(1), если есть коллизия O(n).
  2. Вставить - если нет коллизии - O(1), если есть коллизия O(n).
  3. Удаление - если нет коллизии - O(1), если есть коллизия O(n).

TreeSet

TreeSet - хранение уникальных значений в сортированном виде. Реализует красно-чёрное дерево.

Сложность алгоритмов TreeSet

  1. Получение - если первый элемент - O(1), если не первый O(log(n)).
  2. Вставить - O(log(n)).
  3. Удаление - O(log(n)).
  • Разница HashSet и TreeSet? - TreeSet на основе дерева. При добавлении сортирует. Для добавления необходимо передать Comparator или чтобы его элементы реализовывали Comparable.

    • LinkedHashSet

    LinkedHashSet - как HashSet но в порядке добавления(двухсвязный список). В основе лежит LinkedHashMap.

    EnumSet

    Высокопроизводительное множество для enum.

    Используйте вместо HashSet <Enum> (например, для фильтрации флагов или ролей).

    Для concurrent доступа