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

В Java структура данных HashMap реализована на основе массива бакетов, где каждый бакет содержит связанный список или дерево (с Java 8). Метод get в среднем работает за O(1) — константное время, так как вычисляется хеш ключа и сразу обращаются к нужному бакету.

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

Пример использования:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42);
Integer value = map.get("key"); // Средняя временная сложность O(1)