Нужно быстро находить ближайшую запись с ключом не больше заданного и выбирать все записи в диапазоне дат. Какая структура подходит?
TreeMap как NavigableMap: floorKey/ceilingKey/lowerKey/higherKey и subMap, headMap, tailMap за O(log n). Хеш-таблица порядок не хранит.
- Красно-чёрное дерево
- Многопоточно — ConcurrentSkipListMap
- Пример: тарифная сетка по датам — floorEntry(дата)
А ещё Диапазон subMap — представление, а не копия
Подробно
Хеш-таблица не хранит порядок, поэтому любой запрос «ближайший» или «в диапазоне» вырождается в полный перебор. TreeMap построен на красно-чёрном дереве, все операции стоят O(log n), а навигационные методы дают ровно нужную семантику: floorKey — наибольший ключ не больше заданного, ceilingKey — наименьший не меньше, subMap — представление на диапазон. Важная деталь: subMap возвращает именно представление, а не копию, поэтому изменения видны в обе стороны, и запись за границы диапазона бросит IllegalArgumentException.
Что хотят услышать
- Выбор TreeMap и навигационные методы.
- Сложность и конкурентная альтернатива.
Частые ошибки
- Сортировать ключи HashMap на каждый запрос диапазона.
- Считать subMap независимой копией.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✓TreeMap с floorKey и subMap
- ✗HashMap с сортировкой ключей при каждом запросе — поиск всё равно за O(1)
- ✗LinkedHashMap в порядке вставки
- ✗ArrayList с линейным поиском
Что спросят дальше
- Чем floorKey отличается от lowerKey?
- Можно ли положить null-ключ в TreeMap?
Разбор темы
- TreeMap, TreeSet и сортировка
Красно-чёрное дерево, NavigableMap, Comparable против Comparator, согласованность с equals и TimSort.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.