Hachage par adressage ouvert

La table de hachage est implémentée par un tableau t dont les cases vont contenir les associations. Initialement, tous les éléments du tableau ont la valeur null. Puis des opérations d'insertion sont réalisées ; ni la clé ni l'information ne peut être nulle. Si une association de clé x doit être insérée, et que t[h(x)] est vide, c'est-à-dire contient la valeur nulle, alors l'insertion se fait à cette place ; si par contre t[h(x)] est déjà occupé, et que le contenu a une clé différente de x, alors on calcule des valeurs de hachage supplétives h₁(x), h₂(x), ...jusqu'à ce que l'on trouve t[h_i(x)] vide ou contenant une association de clé x. De même, pour chercher une association de clé x, on teste la clé de l'objet en t[h(x)], et éventuellement en t[h₁(x)], t[h₂(x)], etc, jusqu'à ce que la clé de l'objet qui s'y trouve soit égale à x, ou bien que la valeur soit nulle. Dans le cas où la table permet aussi des suppressions, il faut remplacer un objet supprimé par un objet spécial supprimé, distinct de la valeur nulle ; en insertion, on utilisera la première case vide ou supprimée, tandis qu'en recherche, on ne s'arrêtera qu'à la première case vide. On a choisit de représenter un objet supprimé par l'association d'une clé égale à la chaîne vide "" et d'une information nulle ; par conséquent, on doit interdire la chaîne vide en tant que clé pour l'insertion. La classe locale Association est donc légèrement différente de celle employée précédemment.

Pour générer ces nouvelles valeurs de hachage, la méthode la plus simple est le sondage linéaire,   qui choisit $h_i(x) = (h(x)+i) \mathop{\normalfont\mathrm{mod}}\nolimits N$, ce qui revient à essayer les cases suivant t[h(x)]. Il y a d'autres méthodes (sondage quadratique, double hachage, hachage uniforme) qui ont de meilleures capacités de dispersion.

 

class TableHachageOuvert implements Table {

  static class Association {
    Object clé = "";
    Object information;
    Association(Object clé, Object information) {
      if (clé == null || information == null)
        throw new NullPointerException();
      if (clé == "")
        throw new IllegalArgumentException("clé: \"\"");
      this.clé = clé;
      this.information = information;
    }
    // Garantit que supprimé ne sera utilisable qu'en interne
    private Association() {}
  }

  private Association[] tableau;
  private static final Association supprimé = new Association();
    
  private int taille;

  TableHachageOuvert(int taille) {
    tableau = new Association[n];
    this.taille = taille;
  }

  public boolean insérer(Object clé, Object information) {
    int v = clé.hashCode();
    for (int i=0; i<taille; i++) {
      int j = (v+i)%taille;
      if (tableau[j] == null || tableau[j] == supprimé) {
        // la clé n'est pas dans la table
        // on l'y insère avec l'info associée
        tableau[j] = new Association(clé, information);
        return true;
      } else if (tableau[j].clé.equals(clé)) {
        // la clé est déjà dans la table : 
        // mise à jour de l'info associée
        tableau[j].information = information;
        return true;
      }
    }
    // i == taille => la table était pleine
    return false;      
  }

  public Object rechercher(Object clé) {
    int v = clé.hashCode();
    for (int i=0; i<taille; i++) {
      int j = (v+i)%taille;
      if (tableau[j] == null) {
        return null;
      } else if (tableau[j].clé.equals(clé)) {
        return tableau[j].information;
      }
    }
    return null;
  }
  
  public boolean supprimer(Object clé) {
    int v = clé.hashCode();
    for (int i=0; i<taille; i++) {
      int j = (v+i)%taille;
      if (tableau[j] == null) {
        return false;
      } else if (tableau[j].clé != null && 
                 tableau[j].clé.equals(clé)) {
        tableau[j] = supprimé;
        return true;
      }
    }
    return false;
  }
}

 

 

Il est clair que la complexité dans le pire des cas est de Nopérations, N étant la taille de la table. On définit le taux de chargement d'une table de hachage de taille N contenant nobjets comme la fraction $\alpha = n/N$ ; on a toujours $0\le \alpha\le 1$. Pour donner une estimation asymptotique de la complexité des opérations, on fait tendre n et N vers l'infini, à $\alpha$ constant. On montre que, sous une hypothèse d'uniformité, le nombre moyen d'accès nécessaires pour une recherche infructueuse est d'au plus $1/(1-\alpha)$ et pour une recherche fructueuse de $\frac{1}{\alpha}\log \frac{1}{1-\alpha} + \frac{1}{\alpha}$. Par exemple pour une table à moitié pleine, on doit s'attendre à faire 2 accès pour la recherche d'un objet ne se trouvant pas dans la table, et à faire 3,387 accès s'il s'y trouve. Il s'agit bien d'un algorithme en $\Theta(1)$.