1. 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 \mathrm{h}^{\prime}(\mathrm{k})=\mathrm{k} \% \mathrm{~m}. A outra usa a mesma função primária e probing quadrático \operatorname{com} \mathrm{c} 1=1 e \mathrm{c} 2=3. Qual a melhor tabela considerando que as operações realizadas foram apenas inserções dos valores: 10,22,31,4,15,28, 17, 88, 59?

Passo 1

O enunciado pede para comparar duas tabelas hash de tamanho m=11 usando endereçamento aberto e a mesma função primária de hash
\mathrm{h}'(k)=k \bmod m
– uma com probing linear e outra com probing quadrático definido por
\mathrm{h}(k,i)=\bigl(\mathrm{h}'(k)+c_1\,i+c_2\,i^2\bigr)\bmod m
onde c_1=1 e c_2=3. As operações realizadas foram apenas inserções dos valores
10,\,22,\,31,\,4,\,15,\,28,\,17,\,88,\,59.
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 k calculamos h=\mathrm{h}'(k) 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:
  • 10\to h=10. Insere em 10 (0 colisões).
  • 22\to h=0. Insere em 0 (0 colisões).
  • 31\to h=9. Insere em 9 (0 colisões).
  • 4\to h=4. Insere em 4 (0 colisões).
  • 15\to h=4 ocupado (1ª colisão), tenta 5 livre ⇒ insere em 5 (1 colisão).
  • 28\to h=6. Insere em 6 (0 colisões).
  • 17\to h=6 ocupado (1), tenta 7 livre ⇒ insere em 7 (1 colisão).
  • 88\to h=0 ocupado (1), tenta 1 livre ⇒ insere em 1 (1 colisão).
  • 59\to h=4 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:
1+1+1+4 = 7.

Passo 3

Simulação com probing quadrático c_1=1,c_2=3. Para cada chave k e tentativa i=0,1,2,\dots calculamos
\mathrm{h}(k,i)=\bigl(h'+i+3i^2\bigr)\bmod 11.
Se a célula estiver ocupada contamos uma colisão e incrementamos i.
  • 10\to i=0, slot 10 livre (0 colisões).
  • 22\to i=0, slot 0 livre (0 colisões).
  • 31\to i=0, slot 9 livre (0 colisões).
  • 4\to i=0, slot 4 livre (0 colisões).
  • 15\to i=0 slot 4 ocupado (1), com i=1 temos (4+1+3)\bmod11=8 livre ⇒ insere em 8 (1 colisão).
  • 28\to i=0, slot 6 livre (0 colisões).
  • 17\to i=0 slot 6 ocupado (1), i=1 (6+1+3)\bmod11=10 ocupado (2), i=2 (6+2+12)\bmod11=9 ocupado (3), i=3 (6+3+27)\bmod11=3 livre ⇒ insere em 3 (3 colisões).
  • 88\to i=0 slot 0 ocupado (1), i=1 \to 4 (2), i=2 \to 3 (3), i=3 \to 8 (4), i=4 \to 8 (5), i=5 \to 3 (6), … volta a repetir 3 e 8 infinitamente.
Portanto a inserção de 88 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 9 chaves com 7 colisões.
  • Probing quadrático não consegue inserir todas as chaves (falha no 88).

Resposta

A tabela com probing linear é melhor, pois insere todas as chaves enquanto o probing quadrático falha em inserir 88.

Exercícios relacionados