Insira a seguinte sequência de 12 chaves em uma tabela hash com 3 cadeias de encadeamento:
chave: hash
D: 2
Q: 0
B: 0
I: 1
M: 2
H: 0
G: 2
U: 1
A: 2
C: 1
R: 1
S: 2
Considere um busca pela chave J, cuja hash é 2. Qual é a sequência de chaves que é comparada com J?

Passo 1

A questão pede para inserir 12 chaves numa tabela hash de tamanho 3 usando encadeamento separado (cadeias ligadas) e depois pesquisar a chave J, cujo hash é 2, listando a ordem das comparações. Vamos usar o método padrão de inserir cada novo elemento no início (head) da lista do seu bucket.

Passo 2

Para cada chave, já temos o valor de hash (índice do bucket). Na ordem dada fazemos: D(2), Q(0), B(0), I(1), M(2), H(0), G(2), U(1), A(2), C(1), R(1), S(2). Em cada inserção colocamos o nó no início da lista correspondente.

Passo 3

Depois de todas as inserções, as cadeias ficam assim: bucket 0: H→B→Q; bucket 1: R→C→U→I; bucket 2: S→A→G→M→D. Em particular, para o índice 2 a lista é S, A, G, M, D.

Passo 4

Na busca por J com $hash(J)=2$ acessamos a cadeia do bucket 2 e comparamos J em cada nó, na ordem da lista: primeiro S, depois A, depois G, depois M e por fim D.

Resposta

As chaves são comparadas em sequência: S, A, G, M, D.

Exercícios relacionados