Что важно знать
- Индекс бакета из хеша ключа; коллизии — список, при длине больше 8 — красно-чёрное дерево.
- Расширение вдвое при заполнении на 75%.
HashSet— обёртка надHashMap.LinkedHashMapхранит порядок вставки или доступа — основа LRU.
Этап 2 из 11 · ≈ 6 ч
HashMap, HashSet и LinkedHashMap
Основа с Junior
Бакеты, коллизии, treeify, resize, порядок обхода и 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 ищут в другой корзине и не находят равный объект: до вызова equals дело не доходит.
Полный разборКак HashMap находит место для пары ключ-значение?Junior
По hashCode ключа вычисляется индекс корзины в массиве, внутри корзины ключи сравниваются через equals.
Полный разборЧем HashMap отличается от Hashtable и ConcurrentHashMap?Middle
HashMap — не потокобезопасна, допускает один null-ключ и null-значения. Hashtable — устаревшая, все методы synchronized, null запрещён. ConcurrentHashMap — потокобезопасная с мелкой блокировкой, null запрещён.
Полный разборЧто LinkedHashMap добавляет к обычной HashMap?Junior
Предсказуемый порядок обхода — по умолчанию в порядке вставки — поверх той же хеш-таблицы.
Полный разборЧто происходит в HashMap при коллизии ключей?Middle
Коллизии кладутся в один bucket; HashMap ищет нужный ключ через equals, а длинную цепочку (≥8 при таблице ≥64) превращает в красно-чёрное дерево.
Полный разборЧто произойдёт при добавлении в HashSet элемента, который там уже есть?Junior
Множество не изменится, а add вернёт false — удобная проверка «элемент новый?».
Полный разборРазборы темы
- HashMap изнутри: бакеты, treeify, resize
Таблица бакетов, перемешивание хеша и индекс, превращение цепочки в дерево, ресайз и load factor, контракт ключа.
- Set: HashSet, LinkedHashSet, TreeSet
Почему Set построен поверх Map, три реализации и их гарантии порядка, роль equals/hashCode.
- LinkedHashMap и LRU-кэш
Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.
Партнёр платформы
Разбор собеседования
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.