Использует ли TreeMap сортировку элементов по ключу при их добавлении?

Да, TreeMap в Java хранит элементы в отсортированном порядке по ключу. При добавлении нового элемента TreeMap использует либо естественный порядок ключей (если ключи реализуют Comparable), либо переданный компаратор (Comparator), чтобы определить позицию для вставки.

Таким образом, элементы всегда упорядочены, и операции поиска, вставки и удаления выполняются с логарифмической сложностью.

Пример:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "три");
map.put(1, "один");
map.put(2, "два");

System.out.println(map.keySet()); // [1, 2, 3]