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:
(d) Hash duplo, função hash:
, função hash 2:
(d) Hash duplo, 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 por hash duplo, onde h₁(k) = k mod 10 e h₂(k) = 7 − (k mod 7).
Passo 2
No hash duplo a posição i-ésima sondada para uma chave k é dada por
[(h₁(k) + i ⋅ h₂(k)) mod M].
Passo 3
Inserção de 371: calculamos
h₁(371) = 371 mod 10 = 1.
Como a posição 1 está vazia, colocamos 371 em 1.
Passo 4
Inserção de 121: temos
h₁(121) = 121 mod 10 = 1 (colisão).
h₂(121) = 7 − (121 mod 7) = 7 − 2 = 5.
Sondamos em i=1: (1 + 1⋅5) mod 10 = 6, que está livre. Colocamos 121 em 6.
Passo 5
Inserção de 173: calculamos
h₁(173) = 173 mod 10 = 3.
3 está livre, então 173 vai para 3.
Passo 6
Inserção de 203: temos
h₁(203) = 203 mod 10 = 3 (colisão).
h₂(203) = 7 − (203 mod 7) = 7 − 0 = 7.
Sondamos em i=1: (3 + 1⋅7) mod 10 = 0, que está livre. Colocamos 203 em 0.
Passo 7
Inserção de 11: calculamos
h₁(11) = 11 mod 10 = 1 (colisão).
h₂(11) = 7 − (11 mod 7) = 7 − 4 = 3.
Sondamos em i=1: (1 + 1⋅3) mod 10 = 4, livre. Colocamos 11 em 4.
Passo 8
Inserção de 24: temos
h₁(24) = 24 mod 10 = 4 (colisão).
h₂(24) = 7 − (24 mod 7) = 7 − 3 = 4.
Sondamos em i=1: (4 + 1⋅4) mod 10 = 8, livre. Colocamos 24 em 8.
Passo 9
A tabela final (índices 0 a 9) fica:
0 → 203, 1 → 371, 2 → –, 3 → 173, 4 → 11, 5 → –, 6 → 121, 7 → –, 8 → 24, 9 → –
0 → 203, 1 → 371, 2 → –, 3 → 173, 4 → 11, 5 → –, 6 → 121, 7 → –, 8 → 24, 9 → –
Resposta
Índices: [0:203, 1:371, 2:–, 3:173, 4:11, 5:–, 6:121, 7:–, 8:24, 9:–]