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.
© Encadeamento separado

Passo 1

Resumindo o enunciado: temos uma tabela hash de tamanho 7 e queremos inserir os valores 2341, 4234, 2839, 430, 22, 397 e 3920 usando encadeamento separado para tratar colisões. O conteúdo envolve tabelas hash e resolução de colisões por encadeamento separado.

Passo 2

Para cada valor x aplicamos a função de hash h(x)=x bmod 7. Calculando: 2341 bmod 7 = 3, 4234 bmod 7 = 6, 2839 bmod 7 = 4, 430 bmod 7 = 3, 22 bmod 7 = 1, 397 bmod 7 = 5 e 3920 bmod 7 = 0.

Passo 3

No encadeamento separado, cada posição (bucket) da tabela armazena uma lista de elementos cujo hash dá o mesmo índice. Inserimos cada valor na ordem dada, adicionando ao fim da lista do bucket correspondente: - 2341 e depois 430 vão para o bucket 3; - 22 para o bucket 1; - 2839 para o bucket 4; - 397 para o bucket 5; - 3920 para o bucket 0; - 4234 para o bucket 6.

Passo 4

Agora montamos a tabela final listando, para cada índice de 0 a 6, os elementos encadeados na ordem de inserção.

Resposta

Índice 0: [3920]
Índice 1: [22]
Índice 2: []
Índice 3: [2341, 430]
Índice 4: [2839]
Índice 5: [397]
Índice 6: [4234]

Exercícios relacionados