- Suponha que você deseja fazer um estudo comparativo entre duas tabelas hash de tamanho 11. Uma delas usa endereçamento aberto com probing linear e função primária de hash
. A outra usa a mesma função primária e probing quadrático
e
. Qual a melhor tabela considerando que as operações realizadas foram apenas inserções dos valores:
, 17, 88, 59?
Passo 1
O enunciado pede para comparar duas tabelas hash de tamanho
usando endereçamento aberto e a mesma função primária de hash
– uma com probing linear e outra com probing quadrático definido por
onde
e
. As operações realizadas foram apenas inserções dos valores
Precisamos simular ambas as formas de probing, contar colisões e verificar se todas as chaves cabem sem falha.
Passo 2
Simulação com probing linear. Para cada chave
calculamos
e, em caso de ocupação, avançamos uma posição de cada vez até achar um slot livre. Contamos uma colisão sempre que descobrimos a célula ocupada:
-
. Insere em 10 (0 colisões). -
. Insere em 0 (0 colisões). -
. Insere em 9 (0 colisões). -
. Insere em 4 (0 colisões). -
ocupado (1ª colisão), tenta 5 livre ⇒ insere em 5 (1 colisão). -
. Insere em 6 (0 colisões). -
ocupado (1), tenta 7 livre ⇒ insere em 7 (1 colisão). -
ocupado (1), tenta 1 livre ⇒ insere em 1 (1 colisão). -
ocupado (1), tenta 5 ocupado (2), tenta 6 ocupado (3), tenta 7 ocupado (4), tenta 8 livre ⇒ insere em 8 (4 colisões).
Total de colisões no probing linear:
Passo 3
Simulação com probing quadrático
. Para cada chave
e tentativa
calculamos
Se a célula estiver ocupada contamos uma colisão e incrementamos
.
-
, slot 10 livre (0 colisões). -
, slot 0 livre (0 colisões). -
, slot 9 livre (0 colisões). -
, slot 4 livre (0 colisões). -
slot 4 ocupado (1), com temos livre ⇒ insere em 8 (1 colisão). -
, slot 6 livre (0 colisões). -
slot 6 ocupado (1), → ocupado (2), → ocupado (3), → livre ⇒ insere em 3 (3 colisões). -
slot 0 ocupado (1), (2), (3), (4), (5), (6), … volta a repetir 3 e 8 infinitamente.
Portanto a inserção de
entra em ciclo sem encontrar slot livre. O probing quadrático falha em inserir todas as chaves.
Passo 4
Comparando os dois esquemas:
- Probing linear conseguiu inserir todas as
chaves com colisões. - Probing quadrático não consegue inserir todas as chaves (falha no
).
Resposta
A tabela com probing linear é melhor, pois insere todas as chaves enquanto o probing quadrático falha em inserir
.