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

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

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

Пример:

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