Set

Проработать

  1. 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(значение помещается в 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 вместо HashMap.

  • Разница HashSet и LinkedHashSet? - LinkedHashSet хранит записи в порядке добавления, двухсвязный список.