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

Добавление элемента в HashMap в среднем выполняется за O(1) — константное время. Это связано с хешированием ключа и доступом к соответствующему бакету. Однако, в худшем случае (при коллизиях и необходимости перебалансировки) время может ухудшиться до O(n).

Пример:

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

Нюансы:

• При достижении loadFactor (по умолчанию 0.75) происходит рехеширование (resize), что временно увеличивает сложность.
• Для String и стандартных классов с хорошим hashCode() коллизии редки.
• В Java 8 при большом количестве коллизий в бакете используется сбалансированное дерево вместо списка, что улучшает худший случай до O(log n).