Какова временная сложность получения значения по ключу в структуре данных HashMap?

В структуре данных HashMap получение значения по ключу в среднем имеет временную сложность O(1). Это достигается за счёт использования хеш-функции, которая напрямую вычисляет индекс для хранения значения.

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