Suponha uma tabela de hash de tamanho M=10 com endereçamento aberto para armazenar chaves no intervalo [1, 999]. Insira as seguintes chaves nessa tabela: 371, 121,173,203,11,24, nessa ordem, considerando diferentes métodos de resolução de colisões:
© Sondagem quadrática, função hash:

Passo 1

Estamos com uma tabela de hash de tamanho M = 10 usando endereçamento aberto e sondagem quadrática. Vamos inserir as chaves 371, 121, 173, 203, 11 e 24 nesta ordem, com a função de hash
h(k) = (k + 2i + i^2) % M
onde i é o número de tentativas de sondagem (i = 0,1,2,…).

Passo 2

Para inserir 371, fazemos i = 0:
h(371) = (371 + 2·0 + 0^2) % 10 = 371 % 10 = 1
O slot 1 está vazio, então colocamos 371 em 1.

Passo 3

Para inserir 121, começamos com i = 0:
h(121) = (121 + 0 + 0) % 10 = 1
Mas o slot 1 já tem 371 (colisão). Tentamos i = 1:
h(121) = (121 + 2·1 + 1^2) % 10 = (121 + 2 + 1) % 10 = 124 % 10 = 4
O slot 4 está vazio, então colocamos 121 em 4.

Passo 4

Para inserir 173, com i = 0:
h(173) = 173 % 10 = 3
O slot 3 está vazio, então colocamos 173 em 3.

Passo 5

Para inserir 203, começamos com i = 0:
h(203) = 203 % 10 = 3
Slot 3 está ocupado por 173. Com i = 1:
h(203) = (203 + 2·1 + 1^2) % 10 = (203 + 2 + 1) % 10 = 206 % 10 = 6
O slot 6 está vazio, então colocamos 203 em 6.

Passo 6

Para inserir 11, iniciamos em i = 0:
h(11) = 11 % 10 = 1
Slot 1 ocupado. i = 1:
h(11) = (11 + 2 + 1) % 10 = 14 % 10 = 4
Slot 4 ocupado. i = 2:
h(11) = (11 + 2·2 + 2^2) % 10 = (11 + 4 + 4) % 10 = 19 % 10 = 9
Slot 9 está vazio, inserimos 11 em 9.

Passo 7

Para inserir 24, começamos em i = 0:
h(24) = 24 % 10 = 4
Slot 4 ocupado. i = 1:
h(24) = (24 + 2 + 1) % 10 = 27 % 10 = 7
Slot 7 está vazio, então colocamos 24 em 7.

Passo 8

Ao final, a tabela de hash (índices 0 a 9) fica assim:
0: –
1: 371
2: –
3: 173
4: 121
5: –
6: 203
7: 24
8: –
9: 11

Resposta

Índices 0 a 9: [–, 371, –, 173, 121, –, 203, 24, –, 11]

Exercícios relacionados