В чем разница между HashMap и TreeMap и где лучше использовать TreeMap

Что проверяют

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

Как отвечать

HashMap это хеш-таблица: доступ в среднем за постоянное время, порядок обхода не определён и может меняться при перестроении. Ключ должен корректно реализовывать equals и hashCode.

TreeMap это красно-чёрное дерево: ключи хранятся отсортированными, операции за логарифм. Ключ должен быть сравнимым (Comparable) или карте передаётся Comparator.

Когда TreeMap оправдан, ради этого вопрос и задают:

• нужен порядок ключей: обход всегда идёт по возрастанию;
• нужны диапазонные запросы: headMap, tailMap, subMap дают срез по ключам;
• нужны соседи: floorKey, ceilingKey, higherKey, lowerKey, firstEntry, lastEntry. Это то, чего у хеш-таблицы нет в принципе. Классический пример: подобрать тариф по сумме или найти ближайшую дату.

Есть и третий вариант: LinkedHashMap сохраняет порядок вставки при скорости хеш-таблицы. Если нужен именно порядок добавления, а не сортировка, берут его.

Ещё отличия: HashMap допускает один null-ключ, TreeMap не допускает вовсе, потому что его нечем сравнивать. Ни та, ни другая не потокобезопасны, для конкурентного доступа есть ConcurrentHashMap и ConcurrentSkipListMap.

Где спотыкаются

Берут TreeMap просто «чтобы был порядок», хотя нужен порядок вставки, а не сортировка.

Не знают про навигационные методы, а это единственная веская причина брать TreeMap.

Кладут в TreeMap ключи без Comparable и получают исключение во время выполнения.

Полагаются на порядок обхода HashMap.