Как устроена TreeMap в Java?

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

Знаете ли вы структуру внутри и понимаете ли, что равенство определяется сравнением, а не equals.

Как отвечать

TreeMap это красно-чёрное дерево, самобалансирующееся дерево поиска. Отсюда все свойства:

• все основные операции за O(log n): получение, вставка, удаление. Гарантированно, без худшего случая, потому что дерево балансируется при каждом изменении;
• ключи хранятся упорядоченными, обход идёт по возрастанию;
• порядок задаётся либо естественным сравнением ключа, либо переданным компаратором.

За счёт упорядоченности TreeMap реализует навигационный интерфейс, чего нет у хеш-карты: первый и последний ключ, ближайший снизу и сверху, строго больший и строго меньший, а также представления в виде поддиапазонов и обратного порядка. Именно ради этих операций его и берут.

Ключевая тонкость, ради которой обычно и спрашивают: TreeMap определяет равенство ключей через сравнение, а не через equals. Два ключа считаются одинаковыми, если сравнение вернуло ноль. Отсюда классический пример с десятичными числами: значения 1.0 и 1.00 не равны по equals, но сравнение считает их одинаковыми, и в такой карте они займут одну ячейку. Формально это нарушает общий контракт карты, и в документации об этом сказано прямо.

Остальные отличия от HashMap:

• null в качестве ключа не допускается при естественном порядке, потому что сравнение упадёт;
• обход стоит дороже по константе, но идёт в предсказуемом порядке;
• память: узел с двумя ссылками и цветом на каждый элемент.

Не потокобезопасен. Для конкурентного упорядоченного доступа есть карта на списках с пропусками, где операции тоже логарифмические, но без глобальных блокировок.

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

Считают, что равенство ключей определяется через equals.

Кладут null в качестве ключа.

Берут TreeMap там, где порядок не нужен, и платят логарифмом.

Передают компаратор, несогласованный с equals, и получают неожиданное поведение.