Le passage de palpage linéaire à Quadratic palpage (collisions de hachage)

Question

Ma mise en œuvre actuelle d'une table de hachage utilise linéaire Sonder et maintenant je veux passer à Quadratique Sonder (et plus tard à enchaînant et peut-être le double hachant trop). J'ai lu quelques articles, tutoriels, wikipedia, etc ... Mais je ne sais pas encore exactement ce que je dois faire.

linéaire Sonder, au fond, a une étape de 1 et qui est facile à faire. Lors de la recherche, l'insertion ou la suppression d'un élément de la table de hachage, je dois calculer un hachage et que je fais ceci:

index = hash_function(key) % table_size;

Ensuite, lors de la recherche, insérer ou de retirer la boucle I à travers la table jusqu'à ce que je trouve un seau libre, comme ceci:

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 */);

En ce qui concerne Quadratique Sonder, je pense ce que je dois faire est de changer la façon dont la taille de l'étape « index » est calculé, mais c'est ce que je ne comprends pas comment je devrais le faire. Je l'ai vu plusieurs morceaux de code, et tous sont quelque peu différentes.

En outre, j'ai vu certaines implémentations de Quadratique Probing où la fonction de hachage est modifiée pour loger que (mais pas tous). Est-ce que le changement a vraiment besoin ou puis-je éviter de modifier la fonction de hachage et utiliser encore Quadratique Sonder?

EDIT: Après la lecture de tout fait par Eli Bendersky ci-dessous, je pense que j'ai eu l'idée générale. Voici une partie du code 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   }

Il y a 2 choses que je ne comprends pas ... On dit que se fait généralement à l'aide du second degré de sondage c(i)=i^2. Cependant, dans le code ci-dessus, il fait quelque chose de plus comme c(i)=(i^2-i)/2

J'étais prêt à mettre en œuvre sur mon code, mais je voudrais simplement faire:

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

... et non:

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

Si quoi que ce soit, je le ferais:

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

... parce que je l'ai vu d'autres exemples de code plongée par deux. Bien que je ne comprends pas pourquoi ...

1) Pourquoi est-il soustrait l'étape
2) Pourquoi est-ce plongeon par 2?

Answer 1

Vous ne devez pas modifier la fonction de hachage pour du second degré de sondage. La forme la plus simple de palpage quadratique est vraiment juste en ajoutant des carrés conséquentes à la position calculée au lieu de linéaire 1, 2, 3.

Il y a une bonne ressource . Ce qui suit est tiré de là. Ceci est la forme la plus simple de second degré lorsque le sondage c(i) = i^2 simple, polynôme est utilisé:

Dans le cas plus général, la formule est la suivante:

Et vous pouvez choisir vos constantes.

Gardez, à l'esprit, cependant, que du second degré est utile de sondage que dans certains cas. Comme le entrée de Wikipedia états:

  

Quadratic fournit une bonne mémoire de sondage   la mise en cache, car elle préserve certains   localité de référence; cependant, linéaire   sondage a une plus grande localité et,   ainsi, une meilleure performance de cache.   Quadratique mieux sonder évite le   problème de regroupement qui peut se produire avec   linéaire sondage, bien qu'il ne soit pas   immunitaire.

---

EDIT: Comme beaucoup de choses dans la science informatique, les constantes exactes et polynômes de sondage du second degré sont heuristique. Oui, la forme la plus simple est i^2, mais vous pouvez choisir un autre polynôme. Wikipedia donne l'exemple avec h(k,i) = (h(k) + i + i^2)(mod m).

Par conséquent, il est difficile de répondre à votre question « pourquoi ». La seule « pourquoi » Voici pourquoi avez-vous besoin du second degré de sondage du tout? Ayant des problèmes avec d'autres formes de sondage et d'obtenir une table cluster? Ou est-ce juste un devoir à la maison ou l'auto-apprentissage?

Gardez à l'esprit que de loin la résolution de collision de la technique la plus courante pour les tables de hachage est soit linéaire chaînage ou de sondage. Quadratique est une option de sondage heuristique disponible pour des cas particuliers, et à moins que vous savez ce que vous faites très bien, je ne recommanderais pas l'utiliser.

Answer 2

Il est un moyen particulièrement simple et élégante pour mettre en œuvre du second degré de sondage si votre taille de la table est une puissance 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 */);

Au lieu de regarder offsets 0, 1, 2, 3, 4 ... à partir de l'index d'origine, cela se penchera sur les compensations 0, 1, 3, 6, 10 ... (i ^e sonde est à l'offset (i * (i + 1)) / 2, soit il est quadratique).

Ceci est garanti pour frapper chaque position dans la table de hachage (donc vous êtes assuré de trouver un seau vide s'il y a un) fourni la taille de la table est une puissance de 2.

---

Voici un croquis d'une preuve:

1. Compte tenu de la taille de la table de n, nous voulons montrer que nous allons obtenir n valeurs distinctes de (i * (i + 1)) / 2 (mod n) avec i = 0 ... n-1.
2. Nous pouvons le prouver par la contradiction. On suppose qu'il y a moins de n valeurs distinctes: si oui, il doit y avoir au moins deux valeurs entières distinctes pour i dans l'intervalle [0, n-1] de telle sorte que (i * (i + 1)) / 2 (mod n ) est le même. Appelons ces p et q, où p
3. i.e.. (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. Factoriser => (q - p) (p + q + 1) = 0 (mod 2n)
8. (q - p). = 0 est le cas trivial p = q
9. (p + q + 1) = 0 (2n mod) est impossible: les valeurs de p et q sont dans la plage [0, n-1], et q> p, de sorte que (p + q + 1) doit être dans l'intervalle [2, 2n-2].
10. Comme nous travaillons 2n modulo, il faut aussi traiter le cas délicat où les deux facteurs ne sont pas nuls, mais multiplier pour donner 0 (mod 2n):
    • Remarquez que la différence entre les deux facteurs (q - p) et (p + q + 1) est (2p + 1), qui est un nombre impair - si l'un des facteurs doit être même, et l'autre must impair.
    • (q - p) (p + q + 1) = 0 (mod 2n) => (q - p) (p + q + 1) est divisible par 2n. Si n (et donc 2n) est une puissance de 2 , cela nécessite le même facteur à être un multiple de 2n (parce que tous les facteurs premiers de 2n sont 2, alors qu'aucun des principaux facteurs de notre facteur impair).
    • Mais (q - p) a une valeur maximale de n-1, et (p + q + 1) a une valeur maximale de 2n-2 (comme on le voit à l'étape 9), de sorte qu'elle ne le peut être un multiple de 2n .
    • Donc, ce cas est impossible aussi bien.
11. Par conséquent, l'hypothèse selon laquelle il y a moins de n valeurs distinctes (à l'étape 2) doit être fausse.

(Si la taille de la table est pas une puissance de 2, cela tombe à part à l'étape 10.)