Какой худший случай поиска элемента в HashMap

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

Пример:

HashMap<String, String> map = new HashMap<>();
// Все ключи имеют одинаковый хэш
map.put("a", "1");
map.put("b", "2"); 
map.put("c", "3");
// Поиск "c" будет O(n), так как все элементы в одном bucket
String value = map.get("c"); 

В Java 8+ при большом количестве коллизий корзина преобразуется в сбалансированное дерево (O(log n)), но это всё равно хуже O(1).