La recherche par clé dans HashMap offre-t-elle une complexité de temps constante dans tous les cas?

Поиск по ключу в HashMap (или HashMap-подобных структурах) обычно имеет амортизированную константную сложность O(1). Это достигается за счёт хеширования ключа и быстрого доступа к соответствующей корзине (bucket).

Однако в худшем случае, если много ключей попадают в одну корзину (коллизии), поиск может деградировать до линейной сложности O(n), где n — количество элементов в этой корзине.

Современные реализации, например в Java начиная с версии 8, используют сбалансированные деревья (например, красно-чёрные) внутри корзин при большом числе коллизий, что снижает худший случай до O(log n).

Таким образом, постоянная сложность не гарантируется во всех случаях, но на практике благодаря улучшениям и хорошему хешированию поиск остаётся очень быстрым.