Duplo Hashing
O que é?
O Duplo Hashing é uma evolução e aprimoramento da Sondagem Linear dentro do modelo de Endereçamento Aberto. Seu principal objetivo é resolver o problema de Agrupamento Primário. Para alcançar isto, a distância saltada na busca de uma vaga não é fixa em 1 ou um valor invariável; ela é calculada através de uma segunda função de hash independente.
Se as funções de hash forem adequadamente matemáticas e primos entre si ao tamanho da tabela, o duplo hashing é capaz de simular a inserção aleatória uniformemente distribuída, que é o cenário ideal num sistema.
Aplicação no Sistema
Ao acionar o "Endereçamento Aberto: Duplo Hashing" no simulador:
- Quando você tenta inserir um elemento, o programa calculará duas funções matemáticas:
h1(k), o hash primário que dita a tentativa inicial, eh2(k), a função secundária que dita o salto. - Se houver uma colisão em
h1, a fórmula executada pelo simulador mudará para:(Hash_Inicial + Tentativa * Hash2) % Tamanho_da_Tabela. O passo para a próxima tentativa agora é ditado de forma personalizada pela string e seu valor interno. - O log interativo exibirá ambos os cálculos. Este mecanismo garantirá visualmente que dois dados que colidem inicialmente no mesmo índice provavelmente pularão para índices completamente diferentes, espalhando uniformemente os itens pela tabela e evitando blocos aglomerados lentos na pesquisa.