Какая сложность доступа по ключу в TreeMap

Доступ по ключу в TreeMap имеет сложность O(log n), так как реализован на основе красно-чёрного дерева (сбалансированное бинарное дерево поиска). Каждая операция (get(), put(), remove()) требует прохода по дереву от корня до листа, что в худшем случае занимает время, пропорциональное высоте дерева (log n для сбалансированного дерева).

Пример:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "One");
treeMap.put(2, "Two");
String value = treeMap.get(2); // O(log n)

Для сравнения: в HashMap доступ по ключу — O(1) (амортизированно).