Dado os valores 2341,4234,2839,430,22,397,3920, uma tabela hash de tamanho 7 , e função de hash h(x)=x % 7, mostre as tabelas resultantes depois de inserir os valores na ordem dada com cada uma destas estratégias de colisão.
(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 é:
[ c|ccccccc Índice & 0 & 1 & 2 & 3 & 4 & 5 & 6hline Valor & 397 & 22 & 3920 & 2341 & 2839 & 430 & 4234 Í ]

Exercícios relacionados