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:
(d) Hash duplo, função hash: h 1(k)=k % M, função hash 2: h 2(k)=7-(k % 7)

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 → –

Resposta

Índices: [0:203, 1:371, 2:–, 3:173, 4:11, 5:–, 6:121, 7:–, 8:24, 9:–]

Exercícios relacionados