Dado os valores
, uma tabela hash de tamanho 7 , e função de hash
, mostre as tabelas resultantes depois de inserir os valores na ordem dada com cada uma destas estratégias de colisão.
(a) Sondagem linear
(a) Sondagem linear
Passo 1
A questão pede para inserir os valores 2341, 4234, 2839, 430, 22, 397 e 3920 em uma tabela hash de tamanho 7 usando sondagem linear. O conteúdo é tratamento de colisões em hashing, e vamos usar a função de hash h(x)=x % 7 e, em caso de colisão, avançar uma posição por vez até achar um slot vazio.
Passo 2
Começamos inserindo os três primeiros valores, que não causam colisões: h(2341)=2341 % 7=3, então colocamos 2341 na posição 3; h(4234)=4234 % 7=6, colocamos 4234 na posição 6; h(2839)=2839 % 7=4, colocamos 2839 na posição 4.
Passo 3
Agora inserimos 430: h(430)=430 % 7=3. A posição 3 já tem 2341, sondamos linearmente e vemos que a posição 4 está ocupada (2839), mas a posição 5 está livre. Então inserimos 430 na posição 5.
Passo 4
Inserimos 22: h(22)=22 % 7=1. A posição 1 está livre, então colocamos 22 na posição 1.
Passo 5
Inserimos 397: h(397)=397 % 7=5. A posição 5 tem 430, sondamos e vemos que a posição 6 tem 4234, então avançamos e a posição 0 está livre. Colocamos 397 na posição 0.
Passo 6
Por fim, inserimos 3920: h(3920)=3920 % 7=0. A posição 0 tem 397, sondamos e a posição 1 tem 22, avançamos e a posição 2 está livre. Então colocamos 3920 na posição 2.
Resposta
A tabela resultante após inserir todos os valores com sondagem linear é:
[
]