Как определяется сложность операции вставки элемента в HashMap при возникновении коллизии?

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

• Если в бакете используется связный список, то вставка в худшем случае может быть O(n), где n — количество элементов в этом бакете.
• Если количество элементов в бакете превышает порог (обычно 8), связный список преобразуется в красно-черное дерево, что снижает сложность поиска и вставки до O(log n).

Таким образом, при коллизиях сложность вставки зависит от структуры данных в бакете и количества элементов в нем.