Какая сложность получения элемента в HashMap

В среднем - O(1), в худшем случае - O(n).

HashMap использует хеш-функцию для определения индекса корзины (bucket). При хорошей хеш-функции и равномерном распределении элементов доступ к элементу происходит за константное время.

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

Пример:

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

// O(1) в среднем, O(n) в худшем случае
Integer value = map.get("a");