> Какая сложность операций в HashMap и TreeMap в Java (Go)

Короткий ответ

В Java HashMap даёт амортизированное O(1) для get, put и remove при корректном hashCode, но в худшем случае деградирует до O(log n) при коллизиях, превращающих bucket в дерево, или до O(n) без treeification. TreeMap на красно-чёрном дереве гарантирует O(log n) для этих операций и поддерживает упорядоченный обход. Для backend-сервисов это ключевой trade-off между скоростью и порядком.

Подход к решению

Сначала стоит разделить среднюю и худшую сложность, потому что на собеседовании senior-уровня важно показать понимание внутренней реализации, а не только заученные оценки. В HashMap корзины изначально это linked list, но с Java 8 при длине цепочки больше TREEIFY_THRESHOLD (8) и размере таблицы не меньше 64 она преобразуется в красно-чёрное дерево, что даёт O(log n) на коллизиях. Ресайз при превышении loadFactor (0.75) даёт амортизированное O(1), хотя отдельная вставка может стоить O(n). В TreeMap операции всегда O(log n), потому что структура сбалансирована, а ключи сравниваются через Comparable или Comparator. Для Go-разработчика полезно провести параллель с map в Go, где нет упорядоченности и худший случай тоже может деградировать.

Пример кода

JAVA
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class MapComplexityDemo {
    public static void main(String[] args) {
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("user:42", 1);
        hashMap.get("user:42");
        hashMap.remove("user:42");

        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("user:42", 1);
        treeMap.get("user:42");
        treeMap.remove("user:42");
        treeMap.firstKey();
    }
}

Edge cases

Плохой hashCode, возвращающий константу, превращает HashMap в цепочку или дерево и убивает производительность. Мутабельные ключи, изменённые после вставки, ломают и HashMap, и TreeMap. В TreeMap ключи должны быть сравнимы, иначе ClassCastException. HashMap допускает один null-ключ, а TreeMap с natural ordering нет. При конкурентном доступе оба не потокобезопасны, нужны ConcurrentHashMap или внешняя синхронизация.

Как отвечать на собеседовании

Стоит сразу назвать средние оценки, затем уточнить худший случай и внутреннее устройство. Хорошо упомянуть treeification в Java 8, loadFactor и ресайз. Затем сравнить с TreeMap и объяснить, когда порядок важнее скорости. В конце добавить, что для конкурентных сценариев используют ConcurrentHashMap, а не Collections.synchronizedMap.

Что проверяет интервьюер

Проверяется понимание структур данных, а не только таблицы сложностей. Кандидат должен объяснить, почему HashMap не всегда O(1), как коллизии влияют на производительность и когда TreeMap оправдан. Также важно умение связать это с реальными backend-задачами: кэши, индексы, диапазонные запросы и конкурентный доступ.