Dada uma tabela hash de tamanho 17, se as chaves 2,32,43,16,77,51,1,17,42,111 forem inseridas sequencialmente com a função de hash h(k)=k % 17, qual o resultado da tabela quando usado
(a) Sondagem linear
(b) Sondagem quadrática
© Hashing duplo com h 1(k)=1+k % 13

Passo 1

A ideia é inserir as chaves 2, 32, 43, 16, 77, 51, 1, 17, 42, 111 numa tabela de tamanho m=17 usando h(k)=k % 17 e depois resolver colisões por diferentes métodos.

Passo 2

Para sondagem linear usamos a fórmula de prova: (h(k)+j) mod 17, j=0,1,2,… até achar um slot vazio. Aplicando todas as inserções, obtemos esta tabela (índice:key, ‘-’ slot vazio): 0:51, 1:1, 2:2, 3:17, 4:-, 5:-, 6:-, 7:-, 8:42, 9:43, 10:77, 11:111, 12:-, 13:-, 14:-, 15:32, 16:16.

Passo 3

Na sondagem quadrática usamos (h(k)+j²) mod 17. Repetindo o processo de inserção com j=0,1,2,…, ficamos com: 0:51, 1:1, 2:2, 3:-, 4:17, 5:-, 6:-, 7:-, 8:42, 9:43, 10:77, 11:-, 12:-, 13:111, 14:-, 15:32, 16:16.

Passo 4

No hashing duplo usamos i=(h(k)+j·h₁(k)) mod 17, com h₁(k)=1+(k % 13). Fazendo as inserções, o resultado final é: 0:51, 1:1, 2:2, 3:-, 4:-, 5:77, 6:-, 7:111, 8:42, 9:43, 10:17, 11:-, 12:-, 13:-, 14:-, 15:32, 16:16.

Resposta

(a) Sondagem linear:
0:51, 1:1, 2:2, 3:17, 4:-, 5:-, 6:-, 7:-, 8:42, 9:43, 10:77, 11:111, 12:-, 13:-, 14:-, 15:32, 16:16
(b) Sondagem quadrática:
0:51, 1:1, 2:2, 3:-, 4:17, 5:-, 6:-, 7:-, 8:42, 9:43, 10:77, 11:-, 12:-, 13:111, 14:-, 15:32, 16:16
© Hashing duplo:
0:51, 1:1, 2:2, 3:-, 4:-, 5:77, 6:-, 7:111, 8:42, 9:43, 10:17, 11:-, 12:-, 13:-, 14:-, 15:32, 16:16

Exercícios relacionados