Какой самый худший вариант наполнения HashMap

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

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

Как отвечать

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

Дальше главное:

• treeify: когда в корзине 8 элементов (TREEIFY_THRESHOLD) и массив не меньше 64 (MIN_TREEIFY_CAPACITY), список превращается в красно-чёрное дерево. При меньшем массиве вместо этого идёт расширение. Если при расширении в корзине остаётся 6 элементов и меньше, она снова становится списком;
• одинаковый hashCode у ключей Comparable: дерево упорядочивает их через compareTo, поиск остаётся O(log n). Это защищает от атак строками с одинаковым хэшем вроде "Aa" и "BB";
• настоящий худший случай: одинаковый hashCode у ключей без Comparable. Дерево строится, но искать приходится в обоих поддеревьях, get деградирует до O(n), а заполнение n ключами до O(n²);
• худший вариант на практике: наполнять без начальной ёмкости. По умолчанию ёмкость 16 и коэффициент загрузки 0.75, каждый выход за порог удваивает массив и перераскладывает элементы. Если размер известен, берите HashMap.newHashMap(n) (Java 19+) или ёмкость с запасом на коэффициент;
• изменяемые ключи: поменяли после put поле, от которого зависит hashCode, и запись потерялась.

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

Говорят про O(n) и не знают о деревьях в корзинах. Для современной Java это ответ уровня Java 7.

Советуют «перейти на открытую адресацию». В HashMap это не настраивается, можно только написать нормальный hashCode или взять другую структуру.

Переопределяют equals без hashCode. Равные объекты попадают в разные корзины, и containsKey возвращает false для ключа, равного только что положенному.