Suponha uma tabela de hash de tamanho
com endereçamento aberto para armazenar chaves no intervalo [1, 999]. Insira as seguintes chaves nessa tabela: 371,
, nessa ordem, considerando diferentes métodos de resolução de colisões:
© Sondagem quadrática, função hash:
© 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
onde i é o número de tentativas de sondagem (i = 0,1,2,…).
Passo 2
Para inserir 371, fazemos i = 0:
O slot 1 está vazio, então colocamos 371 em 1.
Passo 3
Para inserir 121, começamos com i = 0:
Mas o slot 1 já tem 371 (colisão). Tentamos i = 1:
O slot 4 está vazio, então colocamos 121 em 4.
Passo 4
Para inserir 173, com i = 0:
O slot 3 está vazio, então colocamos 173 em 3.
Passo 5
Para inserir 203, começamos com i = 0:
Slot 3 está ocupado por 173. Com i = 1:
O slot 6 está vazio, então colocamos 203 em 6.
Passo 6
Para inserir 11, iniciamos em i = 0:
Slot 1 ocupado. i = 1:
Slot 4 ocupado. i = 2:
Slot 9 está vazio, inserimos 11 em 9.
Passo 7
Para inserir 24, começamos em i = 0:
Slot 4 ocupado. i = 1:
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
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]