Почему доступ к элементу в Map по ключу в Java происходит за константное время
Что проверяют
Понимаете ли вы, что это верно только для хеш-реализации, и знаете ли условия.
Как отвечать
Первым делом уточните: это свойство HashMap, а не интерфейса карты вообще. У TreeMap доступ логарифмический, у LinkedHashMap постоянный, как у хеш-таблицы.
Механика в HashMap:
- вычисляется хеш ключа;
- хеш дополнительно перемешивается: старшие биты складываются побитовым исключающим или с младшими. Это нужно потому, что индекс корзины берётся младшими битами, и без перемешивания ключи, различающиеся только старшими битами, попали бы в одну корзину;
- индекс корзины вычисляется побитовой операцией, потому что размер таблицы всегда степень двойки. Это дешевле остатка от деления;
- в корзине сравниваются ключи: сначала по хешу, потом методом равенства.
Все шаги не зависят от числа элементов, отсюда постоянное время.
Условия, при которых это выполняется:
- хорошее распределение хешей. Плохой метод вычисления хеша сваливает всё в одну корзину, и поиск становится линейным;
- низкий коэффициент заполнения. При превышении порога в три четверти таблица удваивается и все элементы перекладываются. Это стоит линейно, но происходит редко, поэтому амортизируется.
Худший случай: с восьмой версии длинная цепочка в корзине превращается в дерево, и вырождение ограничено логарифмом вместо линейного времени. До этого поведение было хуже, и оно же было вектором атаки через подбор коллизий.
Честная оговорка: постоянное время не учитывает стоимость вычисления самого хеша. Для длинной строки он считается по всей длине, поэтому константа относительна к числу элементов, а не к размеру ключа.
Где спотыкаются
Говорят про постоянное время для любой карты, включая упорядоченную.
Не упоминают требований к качеству хеша.
Не знают про перемешивание битов и про превращение цепочки в дерево.
Переопределяют равенство без вычисления хеша и ломают всю схему.