Dado os valores
, uma tabela hash de tamanho 7 , e função de hash
, mostre as tabelas resultantes depois de inserir os valores na ordem dada com cada uma destas estratégias de colisão.
© Encadeamento separado
© 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
. Calculando:
,
,
,
,
,
e
.
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
: [3920]
Índice : [22]
Índice : []
Índice : [2341, 430]
Índice : [2839]
Índice : [397]
Índice : [4234]
Índice
Índice
Índice
Índice
Índice
Índice