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.
(b) Sondagem quadrática

Passo 1

Temos que inserir os valores 2341, 4234, 2839, 430, 22, 397 e 3920 em uma tabela hash de tamanho 7 usando sondagem quadrática (endereco aberto). A função de hash é h(x) = x % 7. Para resolver, vamos usar a fórmula de sondagem quadrática index(i) = (h(x) + i²) mod 7 até achar posição livre.

Passo 2

Primeiro, calculamos o hash de cada valor: (1) 2341 % 7 = 3; (2) 4234 % 7 = 6; (3) 2839 % 7 = 4; (4) 430 % 7 = 3; (5) 22 % 7 = 1; (6) 397 % 7 = 5; (7) 3920 % 7 = 0.
Agora inserimos sem colisão os valores cujas posições h(x) estavam livres: 2341 em índice 3; 4234 em índice 6; 2839 em índice 4; 22 em índice 1; 397 em índice 5.

Passo 3

Para os que colidiram, aplicamos a sondagem quadrática: • Inserção de 430 (h=3) colide em 3. Testamos i=1: (3+1²) mod 7 = 4 (ocupado); i=2: (3+2²) mod 7 = 0 (vazio). Logo, 430 vai para o índice 0. • Inserção de 3920 (h=0) colide em 0. Testamos i=1: (0+1²) mod 7 = 1 (ocupado); i=2: (0+2²) mod 7 = 4 (ocupado); i=3: (0+3²) mod 7 = 2 (vazio). Logo, 3920 vai para o índice 2.

Passo 4

A tabela final (índices 0 a 6) fica assim: índice 0→430; 1→22; 2→3920; 3→2341; 4→2839; 5→397; 6→4234.

Resposta

(430,;22,;3920,;2341,;2839,;397,;4234)

Exercícios relacionados