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

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

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

Пример:

HashMap<String, String> map = new HashMap<>();
map.put("key1", "value1");
String value = map.get("key1"); // В среднем O(1), в худшем O(n)