Как работает TreeMap?

TreeMap — реализация NavigableMap на красно-чёрном дереве. Все операции O(log n): get, put, remove. Ключи хранятся в отсортированном порядке — по natural ordering (Comparable) или по переданному Comparator. Даёт методы firstKey(), lastKey(), headMap(), tailMap(), subMap() — удобно для диапазонных запросов. Не допускает null-ключей (нечего сравнивать). Используй когда нужен отсортированный порядок ключей или диапазонные операции. HashMap быстрее (O(1) vs O(log n)), если порядок не нужен.