HashMap, HashSet и LinkedHashMap

Основа с Junior

Бакеты, коллизии, treeify, resize, порядок обхода и LRU-кэш.

Что важно знать

Индекс бакета из хеша ключа; коллизии — список, при длине больше 8 — красно-чёрное дерево.
Расширение вдвое при заполнении на 75%.
HashSet — обёртка над HashMap.
LinkedHashMap хранит порядок вставки или доступа — основа LRU.

Критерии освоения

Junior ≈ 6 ч

Объясняет устройство HashMap — хеш, бакеты, коллизии, расширение

Практика. Объяснить на листке, что происходит при put в HashMap с коллизией и при расширении.

Middle ≈ 4 ч

Объясняет treeify, коэффициент загрузки и цену resize
Реализует LRU-кэш на LinkedHashMap

Практика. Реализовать LRU-кэш на LinkedHashMap и с нуля на хеш-таблице и двусвязном списке.

Вопросы с собеседований

Чем HashSet, LinkedHashSet и TreeSet отличаются? Junior
HashSet — без порядка, операции O(1); LinkedHashSet — помнит порядок вставки, O(1); TreeSet — отсортирован (красно-чёрное дерево), O(log n) и навигация: first, ceiling, subSet.
Какое правило связывает equals() и hashCode()? Middle
Равные по equals объекты обязаны иметь равный hashCode; обратное не требуется — коллизии нормальны. Иначе HashMap и HashSet ищут в другой корзине и не находят равный объект: до…
Как HashMap находит место для пары ключ-значение? Junior
По hashCode ключа вычисляется индекс корзины в массиве, внутри корзины ключи сравниваются через equals.
Чем HashMap отличается от Hashtable и ConcurrentHashMap? Middle
HashMap — не потокобезопасна, допускает один null-ключ и null-значения. Hashtable — устаревшая, все методы synchronized, null запрещён. ConcurrentHashMap — потокобезопасная с…
Что LinkedHashMap добавляет к обычной HashMap? Junior
Предсказуемый порядок обхода — по умолчанию в порядке вставки — поверх той же хеш-таблицы.
Что происходит в HashMap при коллизии ключей? Middle
Коллизии кладутся в один bucket; HashMap ищет нужный ключ через equals, а длинную цепочку (≥8 при таблице ≥64) превращает в красно-чёрное дерево.

Разборы темы

HashMap изнутри: бакеты, treeify, resize
Таблица бакетов, перемешивание хеша и индекс, превращение цепочки в дерево, ресайз и load factor, контракт ключа.
Set: HashSet, LinkedHashSet, TreeSet
Почему Set построен поверх Map, три реализации и их гарантии порядка, роль equals/hashCode.
LinkedHashMap и LRU-кэш
Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.

← Вся карта «Java»

Закрытая бета

Знать тему — половина дела

На живом собеседовании sotto слышит вопрос интервьюера и показывает короткий ответ и план. Оставьте контакт — пришлём доступ и промокод.

Промокод на 2 часа — сверх пробных 30 минут
Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
Первыми узнаете о версии для Mac — пока sotto только для Windows
Прямая связь с разработчиком: что улучшить — сделаем