Какая сложность поиска объекта в HashMap

Поиск объекта в HashMap в среднем имеет сложность O(1) (константное время), если хеш-функция хорошо распределяет элементы и отсутствуют коллизии.

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
int value = map.get("key1");  // O(1) в среднем

Факторы, влияющие на скорость:

• Качество hashCode() ключей.
• Размер HashMap и коэффициент загрузки (по умолчанию 0.75).
• Коллизии (редкие — O(1), частые — O(log n) или O(n)).