Movendo -se da sondagem linear para a sondagem quadrática (Hash Collisonns)

Question

Minha implementação atual de uma tabela de hash está usando sondagem linear e agora quero passar para a sondagem quadrática (e posteriormente para encadear e talvez dupla hash). Eu li alguns artigos, tutoriais, Wikipedia, etc ... mas ainda não sei exatamente o que devo fazer.

A investigação linear, basicamente, tem uma etapa de 1 e isso é fácil de fazer. Ao pesquisar, inserir ou remover um elemento da tabela de hash, preciso calcular um hash e, para isso, faço isso:

index = hash_function(key) % table_size;

Em seguida, enquanto procura, inserindo ou removendo, fico através da mesa até encontrar um balde livre, assim:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

Quanto à investigação quadrática, acho que o que preciso fazer é mudar como o tamanho da etapa "índice" é calculado, mas é isso que não entendo como devo fazê -lo. Eu já vi várias peças de código, e todas elas são um pouco diferentes.

Além disso, vi algumas implementações de sondagem quadrática, onde a função de hash é alterada para acomodar isso (mas não todas). Essa mudança é realmente necessária ou posso evitar modificar a função de hash e ainda usar sondagem quadrática?

EDITAR:Depois de ler tudo apontado por Eli Bendersky abaixo, acho que tive a ideia geral. Aqui está parte do código em http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx:

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

Há duas coisas que não entendo ... eles dizem que a sonda quadrática geralmente é feita usando c(i)=i^2. No entanto, no código acima, está fazendo algo mais como c(i)=(i^2-i)/2

Eu estava pronto para implementar isso no meu código, mas simplesmente faria:

index = (index + (index^index)) % table_size;

...e não:

index = (index + (index^index - index)/2) % table_size;

Se alguma coisa, eu faria:

index = (index + (index^index)/2) % table_size;

... porque vi outros exemplos de código mergulhando por dois. Embora eu não entenda o porquê ...

1) Por que está subtraindo a etapa?
2) Por que está mergulhando por 2?

Answer 1

Você não precisa modificar a função de hash para sondagem quadrática. A forma mais simples de sondagem quadrática é realmente apenas adicionar quadrados consequentes à posição calculada em vez de linear 1, 2, 3.

Há um bom recurso aqui. O seguinte é retirado a partir daí. Esta é a forma mais simples de sondagem quadrática quando o simples polinômio c(i) = i^2 é usado:

No caso mais geral, a fórmula é:

E você pode escolher suas constantes.

Lembre -se, no entanto, que a sonda quadrática é útil apenas em certos casos. Enquanto o Entrada da Wikipedia estados:

A sondagem quadrática fornece um bom cache de memória porque preserva alguma localidade de referência; No entanto, a investigação linear tem maior localidade e, portanto, melhor desempenho do cache. A sondagem quadrática evita melhor o problema de agrupamento que pode ocorrer com sondagem linear, embora não seja imune.

---

EDITAR: Como muitas coisas na ciência da computação, as constantes e polinômios exatos da sondagem quadrática são heurísticos. Sim, a forma mais simples é i^2, mas você pode escolher qualquer outro polinômio. Wikipedia dá o exemplo com h(k,i) = (h(k) + i + i^2)(mod m).

Portanto, é difícil responder à sua pergunta "por que". O único "por que" aqui está por que você precisa de sondagem quadrática? Ter problemas com outras formas de sondagem e obter uma tabela em cluster? Ou é apenas uma tarefa de casa ou auto-aprendizagem?

Lembre -se de que, de longe, a técnica de resolução de colisão mais comum para tabelas de hash é o encadeamento ou a sondagem linear. O quadrático sonda é uma opção heurística disponível para casos especiais e, a menos que você saiba o que está fazendo muito bem, eu não recomendaria usá -lo.

Answer 2

Existe uma maneira particularmente simples e elegante de implementar sondagem quadrática se o tamanho da sua tabela for uma potência de 2:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

Em vez de olhar para as compensações 0, 1, 2, 3, 4 ... do índice original, isso analisará os compensações 0, 1, 3, 6, 10 ... (o I^º A sonda está no deslocamento (i*(i+1))/2, ou seja, é quadrático).

É garantido que isso atinge todas as posições na tabela de hash (então você é garantido para encontrar um balde vazio, se houver) forneceu O tamanho da tabela é uma potência de 2.

---

Aqui está um esboço de uma prova:

1. Dado um tamanho de tabela de n, queremos mostrar que obteremos n valores distintos de (i*(i+1))/2 (mod n) com i = 0 ... n-1.
2. Podemos provar isso por contradição. Suponha que haja menos de n valores distintos: se sim, deve haver pelo menos dois valores inteiros distintos para i no intervalo [0, n-1], de modo que (i*(i+1))/2 (mod n ) é o mesmo. Ligue para estes p e q, onde p <q.
3. ie (p * (p+1) / 2 = (q * (q+1)) / 2 (mod n)
4. => (P² + p) / 2 = (q² + q) / 2 (mod n)
5. => p² + p = q² + q (mod 2n)
6. => q² - p² + q - p = 0 (mod 2n)
7. Fatory => (q - p) (p + q + 1) = 0 (mod 2n)
8. (q - p) = 0 é o caso trivial p = q.
9. (p + q + 1) = 0 (mod 2n) é impossível: nossos valores de p e q estão no intervalo [0, n-1] e q> p, então (p + q + 1) deve estar em o intervalo [2, 2n-2].
10. Enquanto trabalhamos no módulo 2n, também devemos lidar com o caso complicado em que os dois fatores são diferentes de zero, mas multiplicar para dar 0 (mod 2n):
    • Observe que a diferença entre os dois fatores (q - p) e (p + q + 1) é (2p + 1), que é um número ímpar - portanto, um dos fatores deve ser par e o outro deve ser ímpar.
    • (q - p) (p + q + 1) = 0 (mod 2n) => (q - p) (p + q + 1) é divisível por 2n. Se n (e, portanto, 2n) é um poder de 2, isso exige que o fator par seja um múltiplo de 2N (porque todos os fatores primos de 2n são 2, enquanto nenhum dos fatores primos de nosso fator ímpar são).
    • Mas (q-p) possui um valor máximo de N-1 e (P + Q + 1) tem um valor máximo de 2N-2 (como visto na etapa 9), portanto nenhum pode ser um múltiplo de 2n.
    • Portanto, este caso também é impossível.
11. Portanto, a suposição de que existem menos de n valores distintos (na etapa 2) deve ser falsa.

(Se o tamanho da tabela for não Um poder de 2, isso desmorona na etapa 10.)