Устройство HashMap / TreeMap
Как HashMap находит значение по ключу так быстро. Внутри это массив корзин (buckets). Каждый ключ через hashCode() превращается в число, которое указывает на конкретную корзину — поэтому get/put не перебирают все элементы, а сразу “прыгают” в нужное место.
Копнуть глубже
Коллизии — когда два разных ключа попадают в одну корзину. Это нормально (хэш-функция не идеальна), и HashMap решает это, храня в одной корзине связный список пар ключ-значение. При совпадении номера корзины Java дополнительно сверяет ключи через equals(), чтобы понять — это правда один ключ или просто коллизия хэшей.
Load factor и resize. Когда корзины заполняются (по умолчанию на 75%), HashMap автоматически увеличивает массив вдвое и перераспределяет все записи по новым корзинам (rehashing) — это разовая дорогая операция, но она случается редко и поддерживает быстрый доступ в среднем.
Под капотом
С Java 8 длинные цепочки коллизий превращаются в красно-чёрное дерево. Если в одной корзине накопилось много элементов (порог — 8), список превращается в сбалансированное дерево — это меняет худший случай поиска с O(n) на O(log n). Защита от намеренной атаки: если злоумышленник специально подбирает ключи с одинаковым хэшем, чтобы замедлить HashMap до линейного перебора, дерево не даёт это сделать.
TreeMap устроен принципиально иначе — он весь является красно-чёрным деревом (не массивом корзин), отсюда и его гарантия O(log n) на все операции и всегда отсортированный порядок ключей. Подробнее — в теме «TreeMap / TreeSet».
• что такое коллизия и как HashMap её разруливает (если дошёл до 2-го слоя);
• зачем нужно дерево вместо списка в корзине при Java 8+ (если дошёл до 3-го слоя).