Какая алгоритмическая сложность в HashMap

В среднем случае операции put(), get(), remove() в HashMap работают за O(1) благодаря хешированию и равномерному распределению элементов по корзинам (бакетам).

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

Пример:

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

Примечание: Рехеширование (увеличение capacity) выполняется за O(n), но амортизированно это все равно O(1).