Passer du sondage linéaire au sondage quadratique (collisions de hachage)

Question

Mon implémentation actuelle d'une table de hachage utilise le sondage linéaire et maintenant je veux passer au sondage quadratique (et plus tard au chaînage et peut-être au double hachage). J'ai lu quelques articles, tutoriels, wikipédia, etc ... Mais je ne sais toujours pas exactement ce que je devrais faire.

Linear Sondage, fondamentalement, a un pas de 1 et c'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:

index = hash_function(key) % table_size; 

Ensuite, lors de la recherche, l'insertion ou la suppression boucle I à 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 */); 

Quant à quadratique Sonder, je pense que 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. J'ai vu divers morceaux de code, et tous sont quelque peu différents.

En outre, j'ai vu quelques implémentations de sondage quadratique où la fonction de hachage est modifiée pour accommoder cela (mais pas tous). Est-ce que ce changement est vraiment nécessaire ou est-ce que je peux éviter de modifier la fonction de hachage et d'utiliser Quadratic Probing? Après avoir lu tout ce qui a été souligné par Eli Bendersky ci-dessous, je pense que j'ai eu l'idée générale. Voilà 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 plonger par deux. Bien que je ne comprends pas pourquoi ...

1) Pourquoi soustraire l'étape?
2) Pourquoi est-ce qu'il plonge par 2?

Answer 1

Il n'est pas nécessaire de modifier la fonction de hachage pour le sondage quadratique. La forme la plus simple de sondage quadratique consiste simplement à ajouter des carrés consécutifs à la position calculée au lieu de 1, 2, 3.

Il existe une bonne ressource here. Ce qui suit est tiré de là.C'est le sondage sous forme de quadratique simple lorsque le c(i) = i^2 simple, polynôme est utilisé:

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

Et vous pouvez choisir vos constantes. Gardez toutefois à l'esprit que le sondage quadratique n'est utile que dans certains cas. Comme les États Wikipedia entry:

Quadratique bonne mémoire fournit sondage la mise en cache, car il conserve une localité de référence; cependant, le sondage linéaire a une plus grande localité et, , de meilleures performances de cache. Sondage quadratique évite mieux le problème de clustering qui peut se produire avec sondage linéaire, 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 n'importe quel 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». Le seul "pourquoi" ici est pourquoi avez-vous besoin d'un sondage quadratique du tout? Avoir des problèmes avec d'autres formes de sondage et obtenir une table en cluster? Ou est-ce juste une tâche de devoirs ou d'auto-apprentissage? Gardez à l'esprit que la technique de résolution de collision la plus courante pour les tables de hachage est de loin le chaînage ou le sondage linéaire. Le sondage quadratique est une option heuristique disponible pour des cas spéciaux, et à moins que vous sachiez ce que vous faites très bien, je ne recommanderais pas de 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, les offsets 0, 1, 3, 6, 10 ... (la i ^th est à l'offset (i * (i + 1))/2, c'est-à-dire 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.

---

ici est une esquisse d'une preuve:

1. Compte tenu de la taille de la table de n, nous voulons montrer que nous obtiendrons des valeurs n distinctes: (i * (i + 1))/2 (mod n) avec i = 0 ... n-1.
2. Nous pouvons le prouver par contradiction. Supposons qu'il y ait moins de n valeurs distinctes: si c'est le cas, il doit y avoir au moins deux valeurs entières distinctes pour i dans l'intervalle [0, n-1] tel que (i * (i + 1))/2 (mod n) est le même.Appelez ces p et q, où p < q.
3. -à-dire (p * (p + 1))/2 = (q * (q + 1))/2 (mod n)
4. => (p + p)/2 = (q + q)/2 (mod n)
5. => p + p = q + q (2n mod)
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 (mod 2n) est impossible: nos valeurs de p et q sont dans l'intervalle [0, n-1], et q> p, donc (p + q + 1) doit être dans la plage [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 (2n mod):
    • Observons que la différence entre les deux facteurs (q - p) et (p + q + 1) est (2p + 1), qui est un nombre impair - donc un des facteurs doit être pair, et l'autre doit être impair. (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, il faut que le facteur pair soit un multiple de 2n (car tous les facteurs premiers de 2n sont 2, alors qu'aucun des facteurs premiers de notre facteur impair n'est) . Mais (q - p) a une valeur maximale de n-1, et (p + q + 1) a une valeur maximale de 2n-2 (comme vu à l'étape 9), donc aucun ne peut être un multiple de 2n .
    • Donc, ce cas est également impossible.
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.)