В каком случае вставка в HashMap будет выполняться с логарифмической сложностью

Ну, вот смотри, как же это работает на самом деле. Ты вроде думаешь, что HashMap — это просто, положил ключ-значение за O(1) и пошёл дальше. Ан нет, ёпта, жизнь-то оказывается сложнее.

Представь себе идеальный мир, где хэш-функция разбрасывает ключи по корзинам (бакетам) как бог — равномерно и без конфликтов. Тогда да, вставка — это константа, O(1), красота. Но мир-то неидеален, чувак! Бывает же такое, что разные ключи, сука, выдают один и тот же хэш. Вот тут начинается самое интересное.

Раньше, в старые добрые времена, при коллизии всё превращалось в простой связный список внутри корзины. И если тебе не повезло и все десять ключей попали в одну корзину, то поиск по ней уже был O(n). Представляешь? Линейная сложность в нашей хэш-мапе! Это пиздец как неэффективно, особенно если какой-нибудь хитрожопый злоумышленник специально сгенерирует кучу ключей с одинаковым хэшем — это же классическая атака на отказ в обслуживании.

Так вот, умные дядьки из Oracle на Java 8 посмотрели на это безобразие и сказали: «Ёб твою мать, так дело не пойдёт». И придумали фишку: когда в одной корзине накапливается овердохуища элементов (а именно 8, это TREEIFY_THRESHOLD), и при этом общий размер мапы уже не мелкий (больше 64, MIN_TREEIFY_CAPACITY), то эта несчастная корзина превращается из связного списка в сбалансированное красно-чёрное дерево.

И вот тут, внимание, магия! Вставка в такое дерево уже имеет сложность O(log n). Это уже не ужасный O(n), а вполне терпимый логарифм. То есть, если в одну корзину набьётся, условно, 1024 коллизионных ключа, то поиск среди них займёт не 1024 шага, а всего около 10. Чувствуешь разницу? Это просто космос!

Вот смотри на этот код, тут как раз смоделирована такая поганая ситуация:

HashMap<Key, Value> map = new HashMap<>();
// Множество коллизий для одного bucket
for (int i = 0; i < 10; i++) {
    map.put(new Key(i), "Value" + i); // При коллизиях Key с одинаковым hashCode
}
// После 8 элементов корзина становится деревом

Здесь мы насильно пихаем 10 объектов, у которых hashCode() возвращает одно и то же значение. Первые 8 будут тихо висеть в списке. Но как только суётся девятый — ёперный театр! — корзина накрывается медным тазом, список летит в пизду, и на его месте вырастает дерево. Все последующие вставки в эту корзину будут уже O(log n).

Так что запомни: доверия ебать ноль к простым ответам. Говорить «вставка в HashMap — O(1)» это как минимум неполно. Да, в большинстве случаев, когда коллизий мало — это правда. Но если тебе на голову свалится худший случай с кучей коллизий, то будь готов к O(log n). Не ни хуя себе, а так и есть. Ядрёна вошь, как всё продумано, однако.