В чём разница между HashMap и TreeMap? Когда и где их нужно использовать?

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

HashMap хранит пары в хэш-таблице: порядок обхода не определён и зависит от хэш-кодов и размера таблицы, операции put, get, remove в среднем O(1); допускается один null-ключ и null-значения. TreeMap хранит записи в красно-чёрном дереве: ключи всегда отсортированы — по естественному порядку (Comparable) или заданному Comparator, а все операции занимают O(log n).

Как это работает подробнее

TreeMap — это самобалансирующееся бинарное дерево поиска: в каждой вершине хранятся ключ, значение, ссылки на потомков и цвет (красный или чёрный); инварианты балансировки гарантируют высоту O(log n). null-ключ TreeMap не допускает, так как при вставке ключ нужно с чем-то сравнивать. Главный козырь — работа с упорядоченными данными: firstKey(), lastKey(), headMap(), tailMap(), subMap().

• HashMap: порядок ключей не важен и нужна максимальная скорость.
• TreeMap: нужен отсортированный обход, поиск ближайших ключей или диапазонные выборки.

Пример кода

TreeMapDemo.javaКопировать

Map<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");
System.out.println(map.keySet());      // [1, 2, 3] — отсортировано
System.out.println(map.headMap(3));    // {1=one, 2=two}
System.out.println(map.subMap(2, 4));  // {2=two, 3=three}

Что использовать на практике

• Используйте HashMap, когда порядок ключей не важен и нужен средний O(1).
• Используйте TreeMap, когда нужен обход по возрастанию ключей, ближайшие ключи или диапазонные выборки.

Подводные камни

• У TreeMap нет константного доступа — все основные операции O(log n).
• TreeMap не принимает null-ключ (при вставке нужно сравнение), хотя null-значения разрешены.
• Порядок обхода HashMap непредсказуем и меняется при resize — не рассчитывайте на него.

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

• Противопоставьте структуры: хэш-таблица против красно-чёрного дерева → сравните сложности: средний O(1) у HashMap и O(log n) у TreeMap → добавьте про null и чем задаётся порядок (Comparable или Comparator) → перечислите фишки TreeMap: firstKey, lastKey, headMap, tailMap, subMap → дайте правило выбора по задаче.