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:
(a) Sondagem linear, função hash:
(a) Sondagem linear, função hash:
Passo 1
O enunciado pede para inserir as chaves 371, 121, 173, 203, 11 e 24 em uma tabela de hash de tamanho M = 10 usando endereçamento aberto e sondagem linear. O conteúdo envolve tabelas de hash, colisões e resolução por sondagem linear, e vamos precisar da função de hash com incremento de i para resolver colisões.
Passo 2
Em sondagem linear com incremento de passo 1, definimos a função de hash como
onde M = 10 e i = 0,1,2,… até encontrar uma posição livre.
Passo 3
Para inserir 371, calculamos com i = 0:
A posição 1 está livre, então colocamos 371 em T[1].
Passo 4
Para inserir 121, começamos com i = 0:
Mas T[1] já tem 371, então incrementamos i:
A posição 2 está livre, então colocamos 121 em T[2].
Passo 5
Para inserir 173, com i = 0:
A posição 3 está livre, então colocamos 173 em T[3].
Passo 6
Para inserir 203, tentamos i = 0:
Colidiu com 173 em T[3], então i = 1:
A posição 4 está livre, então colocamos 203 em T[4].
Passo 7
Para inserir 11, começamos com i = 0:
Colide com 371; tentamos i = 1:
Colide com 121; i = 2:
Colide com 173; i = 3:
Colide com 203; i = 4:
T[5] está livre, então colocamos 11 em T[5].
Passo 8
Para inserir 24, i = 0:
Colide com 203; i = 1:
Colide com 11; i = 2:
T[6] está livre, então colocamos 24 em T[6].
Resposta
A tabela de hash final (índices de 0 a 9) fica: