Как устроен и работает HashMap в Java

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

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

Как отвечать

HashMap это массив корзин. При добавлении берётся hashCode ключа, дополнительно перемешивается (h ^ (h >>> 16), чтобы старшие биты влияли на индекс), и по остатку от размера массива определяется корзина.

Если корзина занята, это коллизия. Записи складываются в связный список, а начиная с восьми элементов в корзине и при размере таблицы от 64 список превращается в красно-чёрное дерево: поиск в такой корзине становится логарифмическим вместо линейного.

Сравнение внутри корзины идёт по equals, поэтому контракт equals и hashCode обязателен.

Размер и перестроение: по умолчанию 16 корзин и коэффициент загрузки 0.75. Когда записей становится больше, массив удваивается и все элементы перераспределяются. Отсюда практика: если известно примерное число записей, задавайте начальную ёмкость, перестроение стоит дорого.

Сложность операций в среднем O(1), в вырожденном случае с плохим hashCode вырождается до O(log n) на дереве. Порядок обхода не гарантируется, для порядка вставки есть LinkedHashMap, для сортировки TreeMap.

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

Говорят «хеш-таблица» и не могут объяснить, что происходит при коллизии.

Не знают про превращение списка в дерево, хотя это в Java с восьмой версии.

Считают, что HashMap потокобезопасна. Параллельная запись при перестроении раньше могла зациклить список, сейчас портит данные, для конкурентного доступа есть ConcurrentHashMap.

Забывают, что null допустим и как ключ, и как значение, в отличие от ConcurrentHashMap.