Map(key, value) - коллекция хранит не множество элементов, а множество «пар элементов».
Bucket(array) -> Односвязный list Node<K, V>(ключ - значение) или TreeNode
Node содержит: hashCode, key, value, next.
Позволяет добавить (null, null), null будет первым ключом в коллекции.
HashMap bucket будет трансформирован из односвязного списка(Node) в дерево(TreeNode) при размере > 8. И произойдёт обратное при > 6.
default initial capacity = 16 - размер массива bucket.
load_factor = 0.75 - процент на который должен быть заполнен capacity(non-empty buckets) для умножения capacity на 2. Если установить 1 или больше - Map не будет расширяться.
Если во время обхода карта меняется(кроме iterator.remove()), бросается ConcurrentModificationException. Под капотом это работает через счётчик модификаций(modCount), который проверяется в каждом next().
На основе бинарного(каждый узел имеет только два потомка) красно-чёрного(сбалансированного) дерева. Гарантирует сложность log(n).
Красно-чёрное дерево - добавляет балансировку. Во время добавления до 2-х поворотов. При удалении до 3-х.
Для создания объекта дерева, необходимо передать Comparator в конструктор. Или ключом должен быть класс реализующий интерфейс Comparable<T>.
LinkedHashMap - это упорядоченная реализация хэш-таблицы. В порядке добавления.
boolean accessOrder(by default false) - параметр. false - порядок согласно вставке; true - порядок согласно частоте доступа(от меньшего к большему). Влияют только на get() и put(). Подходит для LRU-cache.
removeEldestEntry(Entry<K, V> eldest) - удаление старых данных.
HashMap часто применяют для кэширования, но он держит сильные ссылки на ключи, мешая GC освободить память даже тогда, когда объект уже больше нигде не используется. Это может привести к утечкам памяти.
WeakHashMap хранит ключи через weak reference. Если на объект key больше нет сильных ссылок, GC может удалить его, и запись в map исчезнет автоматически.
Используется для временных кэшей, хранения слушателей, метаданных, привязанных к жизненному циклу объекта.
Когда объекты "равны", но не одинаковы.
HashMap проверяет ключи через метод .equals(). Если у вас два объекта с одинаковыми данными, но это разные экземпляры (например, два Person с одинаковым именем, но разными записями), то HashMap перезапишет значение.
IdentityHashMap сравнивает ключи только по ссылке (==), игнорируя .equals(). Разные объекты всегда будут разными ключами, даже если у них одинаковые данные.
Используется во фреймворках, парсерах и графах зависимостей, где важна физическая идентичность объекта.
Оптимизированный вариант для enum-ключей.
Эффективная key-value структура, использующая enum в качестве ключа.
Быстрее и легче, чем HashMap<Enum, X> (например, для меток или конфигураций по статусу).
Использовать enum как ключ в HashMap неэффективно. Нужно считать хэши, обрабатывать коллизии, хотя набор ключей фиксирован на этапе компиляции.
EnumMap специально создан для enum-ключей. Внутри он работает через массив, используя ordinal() значения enum в качестве индекса. Это даёт настоящие O(1)-операции и экономит память.
Используется всегда, если ключи берутся из одного enum.
Использует сегментирование распространённые блокировки(в новых версиях — на уровне bucket), что позволяет нескольким потокам читать и писать без полной блокировки карты.
Hashtable при обращении блокировалась полностью.
HashTable и Collection.synchronized(HashMap) - Очень похожи. Но HashTable имеет функционал Enumerators(счетчики).
Потокобезопасная и отсортированная реализация интерфейса NavigableMap, которая работает на основе skip list(списка с пропусками). Skip list — это многослойная структура данных, состоящая из нескольких уровней связных списков: нижний уровень содержит все элементы в порядке сортировки, а верхние уровни - лишь часть элементов для ускорения поиска. При добавлении элемента случайно выбирается его "высота" (количество уровней, на которых он присутствует), что позволяет "перепрыгивать" через блоки данных на верхних уровнях и выполнять операции со сложностью O(log n). Если нужен параллельный доступ к отсортированной мапе
Skip List: Многослойный список с пропусками, где верхние уровни помогают быстро достигать нужного диапазона элементов, снижая количество переходов по связям.
Потокобезопасность обеспечивается за счёт использования CAS (Compare-And-Swap) операций и минимального блокирования. Модификации происходят безопасно без полной блокировки структуры.
Элементы всегда хранятся в отсортированном порядке по их ключам, что позволяет выполнять операции вроде поиска диапазонов или итераций по упорядоченным ключам очень эффективно.
Высокая доступность: чтение не блокируется, даже если выполняются параллельные операции вставки или удаления.
Операции чтения (например, get или containsKey) выполняются быстро и без блокировок благодаря структуре skip list.
Операции записи (например, put и remove) синхронизированы, но производительность сохраняется за счёт оптимизации с использованием CAS.
Поддерживает натуральный порядок ключей или порядок, определённый переданным компаратором.
Эффективен для сценариев, где важны отсортированные данные и параллельный доступ, но количество обновлений не слишком велико.