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:
(a) Sondagem linear, função hash: h(k)=(k+i) % M

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
h(k,i) = (k + i) bmod M
onde M = 10 e i = 0,1,2,… até encontrar uma posição livre.

Passo 3

Para inserir 371, calculamos com i = 0:
h(371,0) = (371 + 0) bmod 10 = 371 bmod 10 = 1
A posição 1 está livre, então colocamos 371 em T[1].

Passo 4

Para inserir 121, começamos com i = 0:
h(121,0) = 121 bmod 10 = 1
Mas T[1] já tem 371, então incrementamos i:
h(121,1) = (121 + 1) bmod 10 = 122 bmod 10 = 2
A posição 2 está livre, então colocamos 121 em T[2].

Passo 5

Para inserir 173, com i = 0:
h(173,0) = 173 bmod 10 = 3
A posição 3 está livre, então colocamos 173 em T[3].

Passo 6

Para inserir 203, tentamos i = 0:
h(203,0) = 203 bmod 10 = 3
Colidiu com 173 em T[3], então i = 1:
h(203,1) = (203 + 1) bmod 10 = 204 bmod 10 = 4
A posição 4 está livre, então colocamos 203 em T[4].

Passo 7

Para inserir 11, começamos com i = 0:
h(11,0) = 11 bmod 10 = 1
Colide com 371; tentamos i = 1:
h(11,1) = 12 bmod 10 = 2
Colide com 121; i = 2:
h(11,2) = 13 bmod 10 = 3
Colide com 173; i = 3:
h(11,3) = 14 bmod 10 = 4
Colide com 203; i = 4:
h(11,4) = 15 bmod 10 = 5
T[5] está livre, então colocamos 11 em T[5].

Passo 8

Para inserir 24, i = 0:
h(24,0) = 24 bmod 10 = 4
Colide com 203; i = 1:
h(24,1) = 25 bmod 10 = 5
Colide com 11; i = 2:
h(24,2) = 26 bmod 10 = 6
T[6] está livre, então colocamos 24 em T[6].

Resposta

A tabela de hash final (índices de 0 a 9) fica:
[-,;371,;121,;173,;203,;11,;24,;-,;-,;-]

Exercícios relacionados