Чем TreeMap отличается от LinkedHashMap по гарантиям порядка

Вопрос звучит просто, но проверяет, понимаете ли вы разницу между порядком сортировки и порядком вставки — это два разных механизма, и они не заменяют друг друга.

LinkedHashMap хранит порядок в отдельном двусвязном списке поверх обычной хеш-таблицы. По умолчанию это порядок вставки. Можно включить accessOrder = true — тогда порядок становится порядком последнего доступа, это база для LRU-кэша.

TreeMap устроен иначе — внутри красно-чёрное дерево, элементы всегда упорядочены по ключу через Comparable или переданный Comparator. Порядок вставки роли не играет вообще: элемент попадает на своё место по значению ключа, а не по времени добавления.

Map tree = new TreeMap<>(); tree.put("c", 1); tree.put("a", 2); tree.put("b", 3); // итерация: a, b, c — // порядок ключей, не вставки

Спросят следом: какая сложность у операций. У LinkedHashMap get/put — O(1) в среднем, как у обычного HashMap, дополнительный список не меняет асимптотику. У TreeMap — O(log n) на каждую операцию, потому что нужно пройти по дереву. Ещё спросят про NavigableMap — floorKey(), ceilingKey(), это то, чего у LinkedHashMap нет вообще: искать ближайший ключ по значению можно только в упорядоченной структуре.

Если нужен порядок вставки или LRU — LinkedHashMap. Если нужен порядок по значению ключа и диапазонные запросы — TreeMap. Путать их на собесе означает не понимать, что каждая структура решает.

Тренажёр: 600 вопросов, мок с таймером, план повторов

senior·base — что спрашивают на самом деле

В этом посте были ссылки, но мы их удалили по правилам Сетки