On a vu que le sondage linéaire simple causait des problèmes de clustering secondaire. Est-ce qu'il y a moyen de résoudre le problème ? Si, plutôt que d'avancer de 1 à chaque fois, nous avancions d'un incrément quelconque ?

Cet incrément doit cependant être judicieusement choisi. Il ne peut pas être quelconque, parce que si cet incrément avait un facteur commun avec m, la taille de la table, il ne pourrait pas visiter toutes les cases! Cet incrément, disons γ, doit être un nombre relativement premier à m. Est-ce qu'un nombre premier pour γ pourrait faire ? oui, pourvu qu'il ne soit pas un diviseur de m. Il n'est donc pas nécessaire de trouver un nombre premier, mais seulement un nombre qui est relativement premier par rapport à m.

Comment cela transforme-t-il la fouille? Soit a₀=H₁(k), la première adresse à examiner. Si la clef que nous cherchons se trouve à l'adresse a₀, la fouille se termine avec succès. Si cette adresse ne contient pas la clef recherchée, nous allons procéder à l'examen d'autres adresses. On examine, au t ^ième essai l'adresse

On boucle jusqu'à ce que l'on trouve la clef, auquel cas le sondage termine avec succès, ou jusqu'à ce que nous atteignions une case vide, ou encore que nous ayons t = m, alors le sondage termine avec échec.

Quels sont les bons choix pour γ? Nous savons déjà qu'il doit être relativement premier à m, mais parmis tous les nombres relativement premiers à m, existe-t-il de meilleurs choix?

Souvenez vous, à la section sur les fonctions de hash primaire sur les entiers, nous avons parlé de φ, le nombre d'or, dont les multiples ont la propriété de diviser successivement l'intervalle 0...m-1 de façon à couper le plus grand segment encore non-exploré.

Les partitions générées par les multiples de φ

Maintenant, comment choisir γ? Nous trouvons simplement un nombre relativement premier à m le plus près possible de (1-φ) m. Donc,

L'algorithme nécessaire pour trouver γ n'est pas très compliqué. Rappelons encore que nous ne cherchons pas un nombre premier mais seulement un nombre relativement premier à m. Alors nous commençons à (1-φ) m et trouvons le nombre entier relativement premier à m le plus près de (1-φ) m.

 const double PHI = 1.6180339887498948482;

 ////////////////////////////////////////
 //
 // plus grand commun diviseur, méthode
 // d'Euclide
 //
 inline unsigned gcd(unsigned u, unsigned v)
  {
   while (v)
    { 
     unsigned r=u % v;
     u=v;
     v=r;
    }

   return u;
  }

 ////////////////////////////////////////
 //
 // pour des i > 2 ?
 //
 inline unsigned Phi( unsigned i )
  {
   const double phi = i * (PHI-1.0);

   bool found = false;

   unsigned p=(unsigned)phi;
   unsigned d=0,v;

   while (!found)
    {
     bool g1 = gcd( p + d, i) == 1;
     bool g2 = gcd( p - d, i) == 1;

     if (g1 && g2)
          {
           found = true;

           if ((p+d-phi) < (phi-p+d))
                v = (p+d);
           else v = (p-d);
          }
     else if (g1 || g2)
               {
                found = true;

                v = (g1) ? (p + d) : (p - d);
               }
          else ; // rien

     d++;
    }
   
   return v;
  }

Bien qu'avec cette méthode nous devons trouver un γ approprié — une opération peu coûteuse que nous ne faisons qu'au moment de la création de la table — elle élimine en grande partie le clustering secondaire. Le coût de la fonction elle-même est insignifiant: on peut remplacer le produit par des additions successives.