Какая сложность операций в HashMap и TreeMap в Java

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

Знаете ли вы оценки и понимаете ли, откуда берётся худший случай у хеш-таблицы.

Как отвечать

HashMap: get, put, remove, containsKey в среднем O(1). Худший случай O(log n): при массовых коллизиях длинная цепочка превращается в красно-чёрное дерево (с восьми элементов в корзине при таблице не меньше 64). До Java 8 худший случай был O(n), и это была не только проблема скорости, но и уязвимость к подбору коллизий.

Перестроение таблицы стоит O(n), но амортизируется: при коэффициенте загрузки 0.75 оно случается редко, и средняя стоимость вставки остаётся постоянной.

TreeMap: get, put, remove за O(log n) всегда, потому что это красно-чёрное дерево. Взамен ключи хранятся отсортированными, доступны навигационные методы (firstKey, floorKey, ceilingKey, subMap), и обход идёт по возрастанию.

Обход обеих карт целиком это O(n), но у HashMap он дороже по константе, если таблица разрежена: приходится пройти пустые корзины.

Как выбирать: нужен только доступ по ключу, значит HashMap. Нужен порядок ключей или запросы по диапазону, значит TreeMap и мириться с логарифмом. Нужен порядок вставки, значит LinkedHashMap, который даёт O(1) и предсказуемый обход.

Оговорка про память: у HashMap есть пустые корзины, у TreeMap на каждый элемент узел с двумя ссылками и цветом.

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

Говорят, что HashMap всегда O(1), не упоминая условие хорошего распределения хешей.

Не знают про превращение цепочки в дерево.

Считают TreeMap быстрее из-за сортировки.

Забывают, что качество hashCode напрямую определяет фактическую сложность.