Collection – для отдельных значений, Map – для пары ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add, добавления элемента.
Collection в свою очередь делится на три основных группы с интерфейсами:
List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу.
Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двунаправленная очередь.
Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
Свойства коллекций
Тип коллекций
Временная сложность
ArrayList - Является реализацией динамического массива объектов. В основе обычный массив.
По дефолту размер 10 при добавлении 11 элемента пересчитывается (дорогая операция) и становится 16 (на 50% больше). Расширяется путем копирования старого массива в новый большего объема.
Следует применять, если предполагается частое обращение к элементам по индексу.
Не надо применять, если требуется частое удаление/добавление элементов в середину коллекции.
Быстрый доступ к элементам по индексу за время O(1);
Доступ к элементам по значению за линейное время O(n);
Медленный, когда вставляются и удаляются элементы из «середины» списка;
LinkedList - Представляет связанный список в каждом элементе которого(кроме первого и последнего) хранится: ссылка на предыдущий элемент, значение, ссылка на следующий элемент.
У нас есть доступ к первому и последнему элементу в любой момент времени O(1).
Из LinkedList можно организовать стек, очередь, или двойную очередь, со временем доступа O(1);
На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя потребуется O(1);
По дефолту размер 16 - initial Capacity, 0.75 load Factor. Если не хватит 16, увеличится в 2 раза.
Условия увеличения (initial Capacity) * (load Factor) = 16 * 0.75 = 12. По достижению определенного количества бакетов или node в одном бакете – преобразуется в красно-черное дерево.
Ассоциативный массив(ключ - любой объект, значение - любой объект).
Структура данных для хранения связанных вместе пар “ключ-значение”.
Хэширует только ключи для быстрого поиска. Хэширование выполняется немного быстрее, чем вставка в дерево, поэтому данные отображение используется, когда не требуется отсортированный порядок ключей.
Нельзя сохранить 2 значения по одинаковым ключам, второе значение заменит первое
HashMap содержит в себе динамически расширяемый массив, элементы в котором называются
Bucket(Бочка). В каждой ячейка этого массива находится связный список наподобие LinkedList из элементов class Node.
Обычно один класс Node должен занимать одну ячейку и его поле next = null, но при обработки коллизии(когда несколько объектов распределяются в одну ячейку) мы сравниваем ключи если они разные тогда мы добавляем в ячейку еще один элемент, если одинаковые заменяем Node на новый.
Map<byte[](ссылка),String> ссылка ведет на разные области памяти в массиве.
Мы можем не найти данные в мапе если изменили хэшкод у ранее записанного объекта.
Потокобезопасные коллекции
HashTable - методы обращения синхронизированы (медленно)
ConcurrentHashMap - синхронизирует только сегменты, не полностью, делая остальную часть доступной для многопоточности.
CopyOnWriteArrayList - по принципу fail-safe, каждый поток работает со своей копией листа(не возникает ConcurrentModificationException).
Comparator vs Comparable (Сортировка 1, -1, 0)
Comparator
Comparable
Comparator
Comparable
1
interface
Interface
2
Когда мы хотим менять характеристики для сравнения
Когда мы хотим сравнивать по главным характеристикам