В чём разница между 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, когда нужен обход по возрастанию ключей, ближайшие ключи или диапазонные выборки.