Como é que a complexidade de adicionar um novo elemento à estrutura de dados HashMap é determinada e avaliada?

A complexidade de adicionar um novo elemento a um HashMap é geralmente avaliada como O(1) amortizado. Isso significa que, em média, a operação de inserção leva um tempo constante, independentemente do tamanho da estrutura.

O HashMap usa uma função hash para calcular o índice do balde (bucket) onde o elemento é colocado. Se não houver colisões no balde, o elemento é adicionado rapidamente. No entanto, em caso de colisões (quando várias chaves têm o mesmo hash), os elementos são armazenados em uma lista ou árvore, o que pode aumentar o tempo de inserção até O(n) no pior caso.

Além disso, ao atingir uma certa carga (fator de carga), ocorre uma redistribuição (rehashing), o que temporariamente aumenta o tempo de inserção.

Exemplo em Java (Android):

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // O(1) amortizado

Assim, na maioria dos casos, adicionar um novo elemento é eficiente, mas em casos raros pode ser mais caro devido a colisões ou rehashing.