В чем преимущество хэш-таблицы по сравнению с массивом

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

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

Как отвечать

Главное преимущество: поиск, вставка и удаление по произвольному ключу в среднем за O(1). В массиве быстрый доступ есть только по целочисленному индексу, а найти элемент по значению можно перебором за O(n) или бинарным поиском за O(log n), если массив отсортирован.

Откуда берётся константа, покажите на HashMap:

• устройство: внутри массив корзин. Номер корзины считается из hashCode() ключа: старшие биты подмешиваются к младшим, затем берётся (n - 1) & hash. Ёмкость всегда степень двойки, чтобы вместо деления с остатком работала битовая маска;
• расширение: по умолчанию 16 корзин и loadFactor 0,75. Когда элементов становится больше 75% от ёмкости, таблица удваивается и элементы перераскладываются. Это O(n), но в пересчёте на одну вставку выходит амортизированная константа;
• коллизии: элементы одной корзины хранятся связным списком. С Java 8, когда цепочка перерастает порог в восемь элементов, а ёмкость таблицы не меньше 64, список превращается в красно-чёрное дерево, и худший случай поиска становится O(log n) вместо O(n);
• контракт: равные по equals объекты обязаны иметь одинаковый hashCode. Изменяемый ключ, у которого после вставки поменялось поле, в карте уже не найти.

И назовите цену. Хэш-таблица не хранит порядок (для него есть LinkedHashMap, для сортировки TreeMap). Каждая запись это отдельный объект Node плюс упаковка примитивов, поэтому памяти уходит в разы больше, а данные хуже ложатся в кеш процессора. Массив выигрывает, когда ключи это плотный диапазон целых чисел или нужен проход по порядку.

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

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

Переопределяют equals без hashCode, после чего map.get() возвращает null для «равного» ключа.

Утверждают, что хэш-таблица растёт бесплатно, а массив дорого. Перехеширование при росте HashMap тоже стоит O(n).