Какая алгоритмическая сложность операций put, get и remove в хэшмапе при коллизиях

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

Знаете ли вы, как устроен HashMap изнутри, а не только формулу «O(1) в среднем». Главное, чего ждут: изменение в Java 8, после которого худший случай перестал быть линейным для большинства ключей. Следом спрашивают про контракт equals и hashCode и про то, что будет с изменяемым ключом.

Как отвечать

Сначала механика. Индекс корзины считается как (n-1) & hash, где n это размер таблицы (степень двойки, по умолчанию 16), а хэш предварительно перемешивается: h ^ (h >>> 16). Коллизии разрешаются цепочками. Любая из трёх операций находит корзину за O(1), а дальше проходит её содержимое, сравнивая хэш и equals.

Дальше сложность:

• средний случай: put, get, remove за O(1), если ключи распределяются ровно, а таблица заполнена не больше чем на loadFactor, по умолчанию 0.75;
• много коллизий до Java 8: корзина была связным списком, худший случай O(n);
• Java 8 и новее: когда в корзине больше восьми элементов (TREEIFY_THRESHOLD) и таблица не меньше 64 ячеек, список превращается в красно-чёрное дерево. Для ключей с Comparable худший случай O(log n). При таблице меньше 64 вместо дерева происходит расширение;
• обратное превращение: при разделении корзины во время ресайза дерево из шести и меньше узлов снова становится списком;
• ресайз: при превышении порога таблица удваивается и записи переносятся. Эта конкретная вставка стоит O(n), в среднем на операцию выходит O(1).

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

Для полноты: открытая адресация в JDK тоже есть, её использует IdentityHashMap с линейным пробированием.

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

Отвечают «всегда O(1)» или «при коллизиях O(n)», не упоминая деревья. Для собеседования на Java это главный пропуск.

Считают, что дерево спасает от любых коллизий. Если ключи не реализуют Comparable, а хэши совпадают полностью, поиску приходится обходить дерево целиком.

Меняют поле ключа, участвующее в hashCode, после put. Запись остаётся в старой корзине, и get её больше не находит, хотя в карте она есть.