Какая сложность у HashMap если столкнулись с коллизией

В среднем случае сложность операций в HashMap (get, put, remove) остается O(1), так как коллизии разрешаются через цепочки (LinkedList или TreeNode в Java 8+). Однако в худшем случае, когда все ключи попадают в один бакет, сложность деградирует до O(n) из-за перебора элементов в цепочке. В Java 8 при большом количестве коллизий (TREEIFY_THRESHOLD = 8) LinkedList преобразуется в сбалансированное дерево, снижая худший случай до O(log n).

Пример:

Map<String, Integer> map = new HashMap<>();
// Все ключи имеют одинаковый хеш
map.put("a", 1);  // O(1)
map.put("b", 2);  // O(1) -> O(n) или O(log n) при коллизиях