Como é avaliada a eficiência da operação de inserção de um elemento numa tabela de hash em diferentes condições?

A eficiência da operação de inserção de um elemento numa tabela de dispersão depende de vários fatores:

1. Carga da tabela (fator de carga) — a relação entre o número de elementos e o tamanho do array. Com uma carga baixa, a inserção geralmente é feita em tempo amortizado O(1).

2. Qualidade da função de dispersão — uma distribuição uniforme das chaves minimiza colisões.

3. Gestão de colisões:

   • Com encadeamento, a inserção consiste em adicionar a uma lista ligada ou outro contêiner na caixa. Em média, O(1), mas no pior caso O(n) se todos os elementos caírem na mesma caixa.
   • Com endereçamento aberto (sondagem linear, quadrática), a inserção pode requerer procurar um espaço livre, o que aumenta o tempo em cargas altas.

4. Rehashing — quando se atinge um limiar de carga, a tabela é expandida, o que requer redistribuir os elementos e temporariamente aumenta o tempo de inserção.

Resumindo: com uma boa função de dispersão e carga moderada, a inserção é amortizada em O(1). Com cargas altas ou má função de dispersão, o tempo pode degradar-se para O(n).