Как устроен HashMap внутри: бакеты, коллизии, расширение и деревья с Java 8?

ЗнаниеMiddleЧасто

Проверила команда СопроводОбновлено

Короткий ответ

HashMap хранит записи в массиве бакетов. Номер бакета считается из hashCode() ключа: старшие биты хеша смешиваются с младшими, результат обрезается маской по размеру таблицы. Ключи с одним номером лежат в бакете цепочкой и различаются через equals(). Когда записей больше 0,75 от емкости, таблица удваивается. С Java 8 длинная цепочка превращается в красно-черное дерево.

Почему этот вопрос задают

HashMap есть почти в каждом сервисе, и от его устройства зависят скорость, память и баги с изменяемыми ключами. Middle должен объяснить, что происходит внутри put и get, своими словами.

Как рассуждать

  1. Опишите массив бакетов и то, как из hashCode() получается номер бакета
  2. Объясните коллизию: два ключа в одном бакете различаются через equals()
  3. Назовите порог расширения: при заполнении больше 0,75 таблица удваивается и записи переезжают
  4. Закончите деревьями с Java 8 и обоими условиями: длина цепочки и емкость от 64

Ответ с примером

Кеш профилей онлайн-игры держит в HashMap профили по нику. put берет hashCode() ключа, смешивает старшие 16 бит с младшими через h ^ (h >>> 16) и обрезает маской (n - 1). Емкость всегда степень двойки, поэтому маска заменяет деление с остатком. У ников «Aa» и «BB» одинаковый хеш 2112, и в таблице на 16 мест оба попадают в бакет 0. Коллизия ничего не теряет: в бакете лежит цепочка узлов, и get находит свой профиль через equals().

По умолчанию емкость 16 и коэффициент загрузки 0,75, поэтому на 13-й записи таблица удваивается до 32. Каждая запись остается в своем бакете или сдвигается ровно на 16 позиций. Если в бакете уже 8 записей и емкость не меньше 64, цепочка становится красно-черным деревом. Когда ключи различаются хешами или реализуют Comparable, поиск в нем занимает O(log n) вместо O(n).

Java
public class Main {
    public static void main(String[] args) {
        Map<String, Profile> cache = new HashMap<>();
        for (Profile p : List.of(new Profile("Aa", 12), new Profile("BB", 40))) {
            cache.put(p.nick(), p);
            int h = p.nick().hashCode(), bucket = (16 - 1) & (h ^ (h >>> 16));
            System.out.println(p.nick() + ": hashCode " + h + ", бакет " + bucket);
        }
        System.out.println(cache.get("Aa") + " " + cache.get("BB"));
    }
}
record Profile(String nick, int level) {}
Вывод
Aa: hashCode 2112, бакет 0
BB: hashCode 2112, бакет 0
Profile[nick=Aa, level=12] Profile[nick=BB, level=40]

Как ответить сильнее

Что добавит опытный кандидат

Что спросят следом

Доступно по подписке

Приемы опытных и готовые ответы

Частые ошибки

  • «HashMap хранит записи в порядке добавления»

    Скажите, что порядок обхода зависит от хешей и меняется после расширения. Нужен порядок добавления — берите LinkedHashMap, нужна сортировка по ключу — TreeMap

  • «Дерево появляется, как только в бакете 8 элементов»

    Добавьте второе условие: емкость таблицы не меньше 64. Маленькую таблицу HashMap сначала удваивает, это дешевле дерева

  • «get и put всегда работают за O(1)»

    Уточните: в среднем O(1) при хорошем hashCode(). Дерево в бакете дает O(log n) при разных хешах или ключах с Comparable, а само расширение таблицы стоит O(n)

  • «Load factor 0,75 значит, что таблица заполняется на 75% и дальше не растет»

    Поправьте: после порога таблица удваивается. 0,75 — компромисс между памятью и длиной цепочек, другое значение можно передать в конструктор

Сигналы для интервьюера

Сильный ответ

Считает номер бакета для конкретного ключа на доске и объясняет, что случится при 13-й вставке в таблицу на 16

Тревожный сигнал

Уверенно описывает бакеты и расширение, а сдвиг h >>> 16 в hash() считает лишней микрооптимизацией

Красный флаг

Уверен, что при коллизии новая запись затирает старую, и не упоминает equals() вовсе

Как еще могут спросить

  • Как HashMap находит бакет для ключа?
  • Что происходит в HashMap при коллизии хешей?
  • Когда HashMap увеличивает размер таблицы?
  • Что изменилось в устройстве HashMap в Java 8?

Похожие вопросы

ЗадачаJuniorЧасто

Объект-ключ не находится в HashMap, хотя все поля совпадают — исправьте класс ключа

HashMap по hashCode ключа выбирает корзину, в ней сначала сравнивает сохраненный хеш и только при совпадении вызывает equals. В классе переопределен один equals, hashCode берется из Object, и у двух одинаковых мест хеши почти всегда разные: до equals дело не доходит. Переопределите hashCode по тем же полям, что и equals, например через Objects.hash, а поля сделайте final.

  • Коллекции
  • HashMap
236
ЗнаниеJuniorЧасто

Чем == отличается от equals в Java и почему сравнение Integer через == ломается на числе 128?

Оператор == у объектов сравнивает ссылки: один ли это объект в памяти. Метод equals() сравнивает содержимое так, как его определил класс. При автоупаковке Integer берет числа от -128 до 127 из кеша, поэтому две переменные со значением 127 указывают на один объект. Для 128 создаются два объекта, и == дает false. Объекты сравнивайте через equals().

  • Java Core
  • сравнение объектов
198
ЗадачаSeniorЧасто

Реализуйте LRU-кэш на заданное число элементов на основе LinkedHashMap

LinkedHashMap умеет хранить порядок доступа: передайте третьим аргументом конструктора true, это флаг accessOrder, и каждый get или put перенесет запись в конец. Переопределите removeEldestEntry, чтобы он возвращал size() > capacity: после вставки карта сама удалит самую давнюю запись. Чтение и запись идут за O(1). Класс не потокобезопасен, для общего кэша нужна синхронизация.

  • Коллекции
  • LinkedHashMap
245
ЗнаниеJuniorЧасто

Чем ArrayList отличается от LinkedList и когда LinkedList действительно быстрее?

ArrayList хранит элементы в массиве: доступ по индексу за O(1), вставка в конец в среднем тоже, вставка в середину сдвигает хвост. LinkedList — двусвязный список: get(i) идет по узлам от ближнего края, зато вставка и удаление через итератор, который уже стоит на месте, занимают O(1). На практике почти всегда быстрее ArrayList, а для очереди берут ArrayDeque.

  • коллекции
  • Java Core
273

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Емкость по умолчанию 16, коэффициент загрузки 0,75, порог дерева 8 и минимальную емкость для дерева 64. Чтобы назвать их уверенно и объяснить, откуда каждое взялось, прочитайте хотя бы раз методы hash, putVal и resize, в IDE это пять минут.

Нарисуйте массив из 16 ячеек, в одну положите два узла с ключами «Aa» и «BB», рядом напишите формулу индекса. Покажите, что узел хранит хеш, ключ, значение и ссылку на следующий узел. Такой рисунок сразу отвечает на пару следующих вопросов.

Чаще всего к ключам, порядку обхода и многопоточности. Повторите контракт equals() и hashCode(), LinkedHashMap с порядком доступа, TreeMap и ConcurrentHashMap: вопросы по ним идут цепочкой сразу после устройства таблицы.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

Назовите две-три причины, которые связывают вас именно с этой компанией: продукт, задачи, масштаб, команда. Каждую подкрепите фактом, который нашли сами: новость, проект, текст вакансии, свой опыт клиента. Потом покажите, что принесете со своей стороны. Слова о стабильности и известном бренде подходят любой компании, поэтому на них ответ не держится.

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

Назовите свое правило: что вы отдаете команде и что оставляете себе, и покажите его на одной задаче. Расскажите, кому и почему передали, какие полномочия и рамки дали, как проверяли без мелкого контроля. Закончите честным итогом: что получилось хуже или медленнее, чем у вас, и что вы выиграли.

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

Поговорите сначала с каждым по отдельности: что случилось, с чего началось и что мешает работать. Потом соберите обоих вместе и обсуждайте работу: кто за какие данные и шаги отвечает. За такой ссорой часто стоит размытая ответственность. Запишите договоренности, назовите новый срок для сорванного отчета и через пару недель проверьте, что все работает.

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227