Como é que a complexidade temporal é determinada ao inserir novos elementos numa tabela de hash?

A complexidade temporal de inserir um elemento numa tabela de dispersão é geralmente avaliada como O(1) amortizado, ou seja, a inserção leva tempo constante em média.

Isto é conseguido através de:

• Cálculo rápido da função de dispersão para determinar o índice.
• Acesso rápido à célula do array.

No entanto, no pior caso (por exemplo, em colisões, quando várias chaves caem na mesma caixa), a inserção pode degradar-se para O(n), se for utilizada uma lista ligada para armazenar colisões.

Implementações modernas (por exemplo, em Java HashMap) quando há muitas colisões mudam para árvores balanceadas, o que reduz o pior caso para O(log n).

Assim, a eficiência temporal depende da eficácia da função de dispersão, do número de colisões e da estrutura de dados utilizada para resolver colisões.