Как TreeMap поддерживает порядок элементов?

TreeMap отличается от HashMap тем, что всегда поддерживает упорядоченность ключей.

Внутренний механизм

Определение:
TreeMap — это реализация Map, основанная на красно-черном дереве.

Красно-черное дерево:

• является самобалансирующимся

• поддерживает высоту дерева близкой к логарифмической

• гарантирует предсказуемую производительность

Как формируется порядок

Перед объяснением важно отметить, что TreeMap сортирует ключи, а не значения.

1. Естественный порядок

   • ключи должны реализовывать Comparable

   • используется метод compareTo()

2. Сравнение при вставке

   • при добавлении элемента выбирается позиция в дереве

   • дерево балансируется автоматически

TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "B");
map.put(1, "A");
map.put(3, "C");

Последствия использования дерева

• операции get, put, remove работают за O(log n)

• ключи не могут быть null без явного компаратора

• порядок всегда сохранен при итерации

Краткий вывод

TreeMap поддерживает порядок элементов за счет красно-черного дерева и логарифмических операций при работе с ключами.