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

Вставка в HashMap будет иметь логарифмическую сложность O(log n) только в случае коллизий, когда корзина (bucket) превращается в сбалансированное дерево (в Java 8+). Это происходит при достижении порога TREEIFY_THRESHOLD (по умолчанию 8 элементов в корзине) и когда общее количество элементов в HashMap превышает MIN_TREEIFY_CAPACITY (64).

Пример:

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

В остальных случаях вставка остается O(1).