Какая скорость поиска значения в HashMap

Средняя скорость поиска в HashMap — O(1), но в худшем случае (при коллизиях) — O(n). Это возможно, если все ключи попадают в одну корзину (например, из-за плохой хэш-функции). В Java 8+ при большом количестве коллизий корзина переключается с linked list на сбалансированное дерево, что улучшает худший случай до O(log n).

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);

// Поиск за O(1) в среднем
Integer value = map.get("key1");

Для эффективности важно:

1. Хорошая хэш-функция (у String, Integer в Java она уже оптимизирована)
2. Равномерное распределение ключей