В каком порядке TreeMap отдаёт свои ключи при обходе?

TreeMap основан на сбалансированном красно-чёрном дереве. Ключи хранятся отсортированными, поэтому обход идёт по возрастанию.

Как задаётся порядок:

• естественный — ключ реализует Comparable (String, Integer, LocalDate);
• внешний — Comparator, переданный в конструктор: new TreeMap<>(Comparator.reverseOrder()).

Цена сортировки — операции за O(log n) вместо O(1) у хеш-таблицы. Взамен есть то, чего у HashMap нет:

• диапазоны: subMap, headMap, tailMap;
• ближайшие ключи: floorKey, ceilingKey, firstKey, lastKey.

Тонкость: одинаковость ключей TreeMap определяет через сравнение (compareTo == 0), а не через equals. Если компаратор считает разные объекты равными, второй перезапишет первый. null в качестве ключа при естественном порядке не допускается.

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

TreeMap<Integer, String> grades = new TreeMap<>(Map.of(90, "A", 75, "B", 60, "C"));
grades.floorKey(82);      // 75 — ближайший ключ снизу
grades.headMap(75, true); // {60=C, 75=B}