TreeMap, SortedMap и NavigableMap в Java - Вопросы
Всего: 5 вопросов
1. Как устроен TreeMap в Java и как он сравнивает ключи?
Как устроен TreeMap в Java и как он сравнивает ключи?
TreeMap хранит пары в узлах красно-чёрного дерева — самобалансирующегося двоичного дерева поиска высотой порядка log n. Поэтому get(), put(), remove() и containsKey() выполняются за O(log n), а обход всегда идёт по возрастанию ключей.
Ключи сравниваются не через equals() и hashCode(), а через compareTo() (естественный порядок, ключ должен быть Comparable) или через Comparator, переданный в конструктор. Если сравнение вернуло 0, ключи считаются одинаковыми: put() заменит значение, а ключ останется прежним.
Отсюда два следствия: put(null, ...) при естественном порядке бросает NullPointerException, а ключ без Comparable и без компаратора — ClassCastException на первом put(). TreeMap реализует интерфейсы SortedMap и NavigableMap.
2. Чем интерфейс SortedMap отличается от NavigableMap?
Чем интерфейс SortedMap отличается от NavigableMap?
SortedMap (Java 1.2) гарантирует обход по возрастанию ключей и добавляет firstKey(), lastKey(), comparator() и поддиапазоны headMap(to), subMap(from, to), tailMap(from): нижняя граница включается, верхняя — нет. Поддиапазоны — живые представления исходной карты; put() ключа вне диапазона бросает IllegalArgumentException: key out of range.
NavigableMap (Java 6) расширяет SortedMap методами навигации: lowerKey(), floorKey(), ceilingKey(), higherKey() и их Entry-версии, firstEntry()/lastEntry(), pollFirstEntry()/pollLastEntry(), descendingMap(), а также headMap(), tailMap(), subMap() с флагами inclusive для каждой границы. Реализации NavigableMap — TreeMap и потокобезопасный ConcurrentSkipListMap.
3. Чем отличаются методы lowerKey(), floorKey(), ceilingKey() и higherKey() в NavigableMap?
Чем отличаются методы lowerKey(), floorKey(), ceilingKey() и higherKey() в NavigableMap?
Все четыре ищут ближайший ключ и не требуют точного совпадения: lowerKey(k) — наибольший ключ строго меньше k (<), floorKey(k) — наибольший ключ меньше или равный k (≤), ceilingKey(k) — наименьший ключ больше или равный k (≥), higherKey(k) — наименьший ключ строго больше k (>). Если подходящего ключа нет, возвращается null.
Для карты с ключами 10, 20, 30, 40, 50: lowerKey(30) = 20, floorKey(30) = 30, ceilingKey(30) = 30, higherKey(30) = 40; для отсутствующего ключа 35 floorKey = 30, ceilingKey = 40; lowerKey(10) и higherKey(50) возвращают null. Методы lowerEntry(), floorEntry(), ceilingEntry(), higherEntry() возвращают пару целиком — неизменяемый снимок, у которого setValue() бросает UnsupportedOperationException.
4. Как с помощью NavigableMap выбрать значение по диапазону, например оценку по баллу?
Как с помощью NavigableMap выбрать значение по диапазону, например оценку по баллу?
Ключом карты делают нижнюю границу диапазона, а нужный диапазон находит floorEntry(value) — наибольший ключ, не превышающий значение. Это O(log n) вместо цепочки if-else:
NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(0, "неудовлетворительно");
grades.put(60, "удовлетворительно");
grades.put(75, "хорошо");
grades.put(90, "отлично");
grades.floorEntry(74).getValue(); // удовлетворительноЕсли значение меньше самой нижней границы (например, -5), floorEntry() вернёт null, и getValue() бросит NullPointerException, поэтому шкала должна начинаться с минимально возможного значения или результат нужно проверять. Так же строят тарифы по весу, скидки по сумме и расписания: для интервала времени — subMap(from, true, to, true), для ближайшего события — ceilingEntry(now).
5. Когда выбирать TreeMap, а когда HashMap?
Когда выбирать TreeMap, а когда HashMap?
HashMap выбирают по умолчанию: get() и put() в среднем O(1), но порядок ключей не гарантирован; ключу нужны корректные equals() и hashCode(), один null-ключ разрешён.
TreeMap медленнее — O(log n) на операцию, — зато хранит ключи отсортированными по возрастанию или по Comparator, умеет искать ближайший ключ (floorKey(), ceilingEntry()), брать минимум и максимум и вырезать диапазоны (subMap()). Ключ должен быть Comparable или сравниваться компаратором; null-ключ при естественном порядке запрещён.
Частый приём — собрать данные в HashMap, а перед выводом один раз отсортировать: new TreeMap<>(hashMap). Обе карты не потокобезопасны: замена HashMap — ConcurrentHashMap, замена TreeMap — ConcurrentSkipListMap.