Como é determinada a complexidade da operação de inserção de um elemento no HashMap em caso de colisão?

A inserção de um elemento em um HashMap geralmente tem uma complexidade amortizada de O(1). No entanto, em caso de colisão, quando duas chaves são hashadas para o mesmo balde, os elementos nesse balde são armazenados na forma de uma lista ligada ou de uma árvore balanceada (a partir do Java 8).

• Se uma lista ligada for usada no balde, a inserção no pior caso pode ser O(n), onde n é o número de elementos nesse balde.
• Se o número de elementos no balde exceder um limite (geralmente 8), a lista ligada é transformada em uma árvore vermelho-preto, o que reduz a complexidade de busca e inserção para O(log n).

Portanto, em caso de colisões, a complexidade da inserção depende da estrutura de dados no balde e do número de elementos nele.