Содержание

Что это

Collections Framework - это специальные классы для хранения использования и удаление множества одинаковых объектов. Нельзя работать с примитивами.

Основные разделы:

• Iterator
• Queue - FIFO.
• PriorityQueue - FIFO. Queue в котором приоритетные элементы будут помещаться в начало очереди. Для пользовательских классов использует Comparator, для Integer, String, Character не нужно.
• Stack - FILO.
• List
• Map
• Set

Новые методы в коллекциях:

1. Iterable.forEach(Consumer action)
2. Map.forEach(BiConsumer action)
3. Collection.removeIf(Predicate filter)
4. Map.compute(K key,BiFunction remappingFunction) - если по ключу есть/нет элемент, заменить/добавить значение на результат переданной функции.
5. Map.computeIfPresent(K key, BiFunction remappingFunction) - ТОЛЬКО если по ключу есть элемент, заменить значение на результат переданной функции.
6. Map.computeIfAbsent(K key, Function mappingFunction) - если отсутствует по ключу, добавить переданный ключ, а значение на результат переданной функции.
7. Map.getOrDefault(Object key, V defaultValue) - возвращает значение, соответствующее ключу key. Если такой ключ не существует — возвращает значение по умолчанию.
8. Map.merge(K key, V value, BiFunction remappingFunction)
   Если в вашей Map ключ key не существует, или value для этого ключа равно null — метод добавляет в Map переданную пару key-value.
   Если ключ Key существует и его value != null — метод меняет его value на результат выполнения переданной функции remappingFunction.
   Если remappingFunction возвращает null - key удаляется из коллекции.
9. Map.putIfAbsent(K key, V value) - если нужно положить в Map и не заменять значение, если элемент по ключу уже лежит.
10. Map.replace и Map.replaceAll()
    Map.replace(K key, V newValue — заменяет значение ключа key на newValue, если такой ключ существует. Если нет — ничего не происходит.
    Map.replace(K key, V oldValue, V newValue) — делает то же самое, но только если текущее значение key равно oldValue.
    Map.replaceAll(BiFunction function) — заменяет все значения value на результат выполнения функции function.

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

O(1) - Константное время

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

Это как мгновенный доступ к элементу массива по индексу.

Пример: доступ к элементу массива по индексу.

O(log n) — Логарифмическое время

В логарифмических алгоритмах задача сокращается на каждом шаге вдвое.

Пример: бинарный поиск в отсортированном массиве.

O(n) — Линейное время

Время выполнения растёт пропорционально объёму входных данных.

Пример: поиск элемента в массиве перебором.

O(n log n) — Линейно-логарифмическое время

Время выполнения немного быстрее, чем квадратичное, и включает логарифмическое количество операций на каждый элемент.

Пример: сортировка массива алгоритмами быстрой сортировки(quick sort) или слиянием(merge sort).

O(n²) — Квадратичное время

Время выполнения растёт пропорционально квадрату входных данных.

В алгоритмах с квадратичной сложностью каждый элемент сравнивается с каждым другим.

Пример: сортировка пузырьком(Bubble Sort).

O(2ⁿ) — Экспоненциальное время

Время выполнения удваивается с каждым новым элементом входа. Такие алгоритмы быстро становятся неэффективными при больших объёмах данных.

Пример: генерация всех подмножеств множества.

O(n!) — Факториальное время

Факториальная сложность возникает в задачах, связанных с вычислением всех возможных перестановок или комбинаций.

Пример: генерация всех перестановок множества.