Hardtreemap
Как работает TreeMap?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
TreeMap — реализация NavigableMap на основе красно-чёрного дерева (self-balancing BST). Ключи отсортированы (natural ordering или Comparator). Все операции O(log n).
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(2, "b"); map.put(1, "a"); map.put(3, "c");
map.firstKey(); // 1
map.lastKey(); // 3
map.higherKey(1); // 2
map.ceilingKey(2); // 2
map.subMap(1, 3); // {1=a, 2=b}
map.descendingMap(); // reverse orderПравила красно-чёрного дерева:
- каждый узел красный или чёрный; корень чёрный;
- красные узлы не имеют красных детей;
- все пути от узла к leaves содержат одинаковое число чёрных узлов.
Итерация — in-order (sorted). Null-ключ зависит от Comparator: natural — не разрешает. ConcurrentSkipListMap — concurrent sorted map (skiplist).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.