Что такое хэшмап

Что проверяют

Знаете ли вы, как HashMap устроен внутри, а не только что он хранит пары ключ-значение. Следом почти всегда спрашивают про коллизии, контракт equals/hashCode и что будет, если изменить ключ после вставки.

Как отвечать

HashMap это реализация Map на хэш-таблице: массив корзин (bucket), индекс корзины вычисляется из хэша ключа.

• индекс корзины: берётся key.hashCode(), старшие биты смешиваются с младшими (h ^ (h >>> 16)), затем hash & (n-1), где n это размер массива, всегда степень двойки;
• коллизии: ключи с одинаковым индексом лежат в одной корзине связным списком. С Java 8, когда список становится длиннее 8 элементов, а таблица не меньше 64 корзин, корзина превращается в красно-чёрное дерево, и худший случай становится O(log n) вместо O(n);
• сравнение ключей: сначала по хэшу, потом через equals. Отсюда контракт: равные объекты обязаны давать одинаковый hashCode;
• рост: начальная ёмкость 16, loadFactor 0.75. Когда элементов становится больше capacity * loadFactor, массив удваивается и записи перераспределяются, на этой вставке операция стоит O(n);
• null: один null-ключ (живёт в корзине 0) и сколько угодно null-значений;
• порядок: не гарантирован и может поменяться после расширения. Нужен порядок вставки, берите LinkedHashMap, сортировка по ключу, TreeMap.

Про потоки: HashMap не потокобезопасен, для конкурентного доступа есть ConcurrentHashMap. Collections.synchronizedMap тоже работает, но блокирует всю карту на каждую операцию.

Где спотыкаются

Говорят «O(1) всегда». Это средняя оценка при нормальной хэш-функции; при плохом hashCode все ключи падают в одну корзину.

Используют изменяемый объект как ключ и меняют его поле после put. Хэш уже другой, запись остаётся в старой корзине, и get возвращает null, хотя элемент в карте есть.

Переопределяют equals без hashCode. Два «равных» ключа попадают в разные корзины, и в карте появляются дубли.