Sondagem Linear
O que é?
A Sondagem Linear (Linear Probing) é uma técnica pertencente ao modelo de Endereçamento Aberto. No endereçamento aberto, não existem estruturas de dados extras: todos os elementos são armazenados nos slots da própria tabela hash. Como resultado, o tamanho da tabela define estritamente o número máximo de itens.
Ao utilizar Sondagem Linear, quando a função hash mapeia um elemento para um índice que já está em uso, a regra é simples: procurar na próxima posição livre. O índice aumenta de forma linear (1 em 1) até que um slot não preenchido seja encontrado.
Aplicação no Sistema
Se você escolher a estratégia "Endereçamento Aberto: Sondagem Linear" no sistema, ele demonstrará este comportamento passo a passo:
- Quando não houver colisão, o slot exibirá o nó armazenado ali, mantendo o controle total do espaço no array principal.
- Caso o slot determinado por
h1esteja preenchido, o simulador inicia as Tentativas (ou saltos). A fórmula utilizada para encontrar a próxima vaga é:(Hash_Inicial + Tentativa) % Tamanho_da_Tabela. - O log lateral detalhará cada verificação com a variável Tentativa = 1, Tentativa = 2 e assim sucessivamente. Ao final da tabela, o operador módulo
%garante que o salto retornará ao índice 0 (varredura circular). - Este modelo ilustra na prática o problema do "Agrupamento Primário", onde longas sequências de itens adjacentes se formam, aumentando drasticamente o tempo necessário para buscar ou inserir dados num espaço vago próximo.