Какая алгоритмическая сложность получения значения из Hashmap по ключу

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

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

Пример на JavaScript (где Map аналогичен HashMap):

const map = new Map();
map.set('key1', 'value1');
console.log(map.get('key1')); // O(1) в среднем