Suponha que as seguintes chaves são inseridas em uma tabela hash de sondagem linear mas não necessariamente na ordem a seguir:
chave: hash
D: 5
E: 6
F: 0
I: 3
S: 6
T: 0
W: 3
Assumindo que o tamanho da tabela hash é 7 e que seu tamanho não é alterado, quais dos seguintes podem ser o conteúdo do array resultante?
F T E W I D S
F E S I T W D
F T I W E S D
D S W T E I F
E F T W I D S
chave: hash
D: 5
E: 6
F: 0
I: 3
S: 6
T: 0
W: 3
F T E W I D S
F E S I T W D
F T I W E S D
D S W T E I F
E F T W I D S
Passo 1
O enunciado pede pra ver quais das sequências propostas podem surgir ao inserir, por sondagem linear, as chaves D,E,F,I,S,T,W num vetor de tamanho 7, sabendo seus valores de hash iniciais (mod 7) dadas por D→5, E→6, F→0, I→3, S→6, T→0 e W→3.
Passo 2
A ideia principal da sondagem linear é que, ao inserir uma chave k, se a posição inicial h(k) estiver ocupada, a gente vai testando h(k)+1, h(k)+2, … (mod 7) até achar um slot livre. Num vetor cheio (7 chaves em 7 posições) não sobra slot, mas mesmo assim qualquer ponto onde k esteja exige que todos os slots entre h(k) e a posição final de k (no sentido de avanço circular) estejam ocupados por outras chaves inseridas antes.
Passo 3
Para cada sequência candidata eu verifico a condição: para cada chave k na posição i do vetor final, todos os slots entre h(k) e i (avançando módulo 7) devem estar preenchidos. Se essa condição valer, existe uma ordem de inserção que gera essa configuração.
Passo 4
Sequência 1: F T E W I D S. Testei cada chave e vi que sempre há ocupação completa no intervalo de prova de cada hash até a posição final. Logo, é válida.
Passo 5
Sequência 2: F E S I T W D. Mesma verificação, e para cada k a faixa de sondagem está cheia. Logo, também é possível.
Passo 6
Sequência 3: F T I W E S D. Novamente, conferi para cada k que não há “buraco” entre h(k) e a posição final; a configuração é atingível.
Passo 7
Sequência 4: D S W T E I F. Mesmo raciocínio: cada chave k satisfaz a condição de faixa cheia de h(k) até onde ela está. Logo, é viável.
Passo 8
Sequência 5: E F T W I D S. De novo checagem bem-sucedida para todas as chaves. Portanto, também pode ocorrer.
Resposta
Todas as cinco sequências podem ser o conteúdo resultante do array.