Previous Up Next

Chapitre 3  Associations — Tables de hachage

Ce chapitre aborde un problème très fréquemment rencontré en informatique : la recherche d’information dans un ensemble géré de façon dynamique. Nous nous plaçons dans le cadre où une information complète se retrouve normalement à l’aide d’une clé qui l’identifie. La notion se rencontre dans la vie de tous les jours, un exemple typique est l’annuaire téléphonique : connaître le nom et les prénoms d’un individu suffit normalement pour retrouver son numéro de téléphone. En cas d’homonymie absolue (tout de même rare), on arrive toujours à se débrouiller. Dans les sociétés modernes qui refusent le flou (et dans les ordinateurs) la clé doit identifier un individu unique, d’où, par exemple, l’idée du numéro de sécurité sociale,

Nous voulons un ensemble dynamique d’informations, c’est-à-dire aussi pouvoir ajouter ou supprimer un élément d’information. On en vient naturellement à définir un type abstrait de données, appelé table d’association qui offre les opérations suivantes.

La seconde opération mérite d’être détaillée. Lors de l’ajout d’une paire clé-information, nous précisons :

Il en résulte qu’il n’y a jamais dans la table deux informations distinctes associées à la même clé.

Il n’est pas trop difficile d’envisager la possibilité inverse, en ajoutant une nouvelle association à la table dans tous les cas, que la clé s’y trouve déjà ou pas. Il faut alors réviser un peu les deux autres opérations, afin d’identifier l’information concernée parmi les éventuellement multiples qui sont associées à une même clé. En général, on choisit l’information la plus récemment entrée, ce qui revient à un comportement de pile.

Enfin, il peut se faire que la clé fasse partie de l’information, comme c’est généralement le cas dans une base de données. Dans ce cas appelons enregistrement un élément d’information. Un enregistrement est composé de plusieurs champs (nom, prénom, numéro de sécurité sociale, sexe, date de naissance etc.) dont un certain nombre peuvent servir de clé. Il n’y a là aucune difficulté du moins en théorie. Il se peut aussi que l’information se réduise à la clé, dans ce cas la table d’association se réduit à l’ensemble (car il n’y a pas de doublons).

3.1  Statistique des mots

Nous illustrons l’intérêt de la table d’association par un exemple ludique : un programme Freq qui compte le nombre d’occurrences des mots d’un texte, dans le but de produire d’intéressantes statistiques. Soit un texte, par exemple notre hymne national, nous aurons

% java Freq marseillaise.txt
nous: 10
vous: 8
français: 7
leur: 7
dans: 6
liberté: 6
  …

3.1.1  Résolution par une table d’association

Le problème à résoudre se décompose naturellement en trois :

  1. Lire un fichier texte mot à mot.
  2. Compter les occurrences des mots.
  3. Produire un bel affichage, par exemple présenter les mots dans l’ordre décroissant du nombre de leurs occurrences.

Supposons les premier et troisième points résolus. Le troisième par un tri et le premier par une classe WordReader des flux de mots. Les objets de cette classe possèdent une méthode read qui renvoie le mot suivant du texte (un String) ou null à la fin du texte.

Une table d’association permet de résoudre facilement le deuxième point : il suffit d’associer mots et entiers. Un mot qui n’est pas dans la table est conventionnellement associé à zéro. À chaque mot lu m on retrouve l’entier i associé à m, puis on change l’association en m associé à i+1. Nous pourrions spécifier en français une version raffinée de table d’association (pas de suppression, information valant zéro par défaut). Nous préférons le faire directement en Java en définissant une interface Assoc.

interface Assoc {
  /* Créer/remplacer l'association key → val */
  void put(String key, int val) ;
  /* Trouver l'entier associé à key, ou zéro. */
  int get(String key) ;
}

La définition d’interface ressemble à une définition de classe, mais sans le code des méthodes. Cette absence n’empêche nullement d’employer une interface comme un type, nous pouvons donc parfaitement écrire une méthode count, qui compte les occurrences des mots du texte dans un Assoc t passé en argument, sans que la classe exacte de t soit connue1.

  static void count(WordReader in, Assoc t) {
    for (String word = in.read() ; word != null ; word = in.read()) {
      if (word.length() >= 4) {     // Retenir les mots suffisamment longs
        word = word.toLowerCase() ; // Minusculer le mot
        t.put(word, t.get(word)+1) ;
      }
    }
  }

(Voir B.6.1.3 pour les deux méthodes des String employées). Une fois remplie, la table est simplement affichée sur la sortie standard.

  Assoc t = … ;
  WordReader in = … ;
  count(in, t) ;
  System.out.println(t.toString()) ;

Les points de la création du WordReader et du tri de la table dans sa méthode toString sont supposés résolus, nous estimerons donc le programme Freq écrit dès que nous aurons implémenté la table d’association nécessaire.

3.1.2  Implémentation simple de la table d’association

La technique d’implémentation la plus simple d’une table d’associations est d’envisager une liste des paires clé-information. Dans l’exemple de la classe Freq, les clés sont des chaînes et les informations des entiers, nous définissons donc une classe simple des cellules de listes.

class AList {
  String key ; int val ;
  AList next ;

  AList (String key, int val, List next) {
    this.key = key ; this.val = val ; this.next = next ;
  }
}

Nous aurions pu définir d’abord une classe des paires, puis une classe des listes de paires, mais nous préférons la solution plus économe en mémoire qui consiste à ranger les deux composantes de la paire directement dans la cellule de liste.

Nous dotons la classe AList d’une unique méthode (statique, null étant une liste valide) destinée à retrouver une paire clé-information à partir de sa clé.

  static AList getCell(String key, AList p) {
    for ( ; p != null ; p = p.next)
      if (key.equals(p.key)) return p ;
    return null ;
  }

La méthode getCell renvoie la première cellule de la liste p dont le champ vaut la clé passée en argument. Si cette cellule n’existe pas, null est renvoyé. Notons que les chaînes sont comparées par la méthode equals et non pas par l’opérateur ==, c’est plus prudent (voir B.3.1.1). Cette méthode getCell suffit pour écrire la classe L des tables d’associations basée sur une liste d’association interne.

class L implements Assoc {

  private AList p ;

  L() { p = null ; }

  public int get(String key) {
    AList r = AList.getCell(key, p) ;
    if (r == null) { // Absent de la table
      return 0 ;
    } else {         // Présent dans la table
      return r.val ;
    }
  }

  public void put(String key, int val) {
    AList r = AList.getCell(key, p) ;
    if (r == null) {  // Absent de la table, créer une nouvelle association
      p = new AList (key, val, p) ;
    } else { // Présent dans la table, modifier l'ancienne association
      r.val = val ;
    }
  }
}

Les objets L encapsulent une liste d’association. Les méthodes get et put emploient toutes les deux la méthode AList.getCell pour retrouver l’information associée à la clé key passée en argument. La technique de l’encapsulage est désormais familière, nous l’avons déjà exploitée pour les ensembles, les piles et les files dans les chapitres précédents.

Mais il faut surtout noter une nouveauté : la classe L déclare implémenter l’interface Assoc (mot-clé implements). Cette déclaration entraîne deux conséquences importantes.

Notre programme Freq fonctionne, mais il n’est pas très efficace. En effet si la liste d’association est de taille N, une recherche par getCell peut prendre de l’ordre de N opérations, en particulier dans le cas fréquent où la clé n’est pas dans la liste. Il en résulte que le programme Freq est en O(n2) où n est le nombre de mots de l’entrée. Pour atteindre une efficacité bien meilleure, nous allons introduire la nouvelle notion de table de hachage.

3.2  Table de hachage

La table de hachage est une implémentation efficace de la table d’association. Appelons univers des clés l’ensemble U de toutes les clés possibles. Nous allons d’abord observer qu’il existe un cas particulier simple quand l’univers des clés est un petit intervalle entier, puis ramener le cas général à ce cas simple.

3.2.1  Adressage direct

Cette technique très efficace ne peut malheureusement s’appliquer que dans des cas très particuliers. Il faut que l’univers des clés soit de la forme {0, …, n−1}, où n est un entier pas trop grand, et d’autre part que deux éléments distincts aient des clés distinctes (ce que nous avons d’ailleurs déjà supposé). Il suffit alors d’utiliser un tableau de taille n pour représenter la table d’association.

Ce cas s’applique par exemple à la base de donnée des concurrents d’une épreuve sportive qui exclut les ex-æquos. Le rang à l’arrivée d’un concurrent peut servir de clé dans la base de données. Mais, ne nous leurrons pas un cas aussi simple est exceptionnel en pratique. Le fait pertinent est de remarquer que le problème de la recherche d’information se simplifie beaucoup quand les clés sont des entiers pris dans un petit intervalle.

3.2.2  Table de hachage

L’idée fondamentale de la table de hachage est de se ramener au cas de l’adressage direct, c’est-à-dire de clés qui sont des indices dans un tableau. Soit m, entier pas trop grand, à vrai dire entier de l’ordre du nombre d’éléments d’informations que l’on compte gérer. On se donne une fonction

h : U → {0, …, m−1}

appelée fonction de hachage. L’idée est de ranger l’élément de clé k non pas dans une case de tableau t[k], comme dans l’adressage direct (cela n’a d’ailleurs aucun sens si k n’est pas un entier) , mais dans t[h(k)]. Nous reviendrons en 3.3 sur le choix, relativement délicat, de la fonction de hachage. Mais nous devons affronter dès à présent une difficulté. En effet, il devient déraisonnable d’exclure le cas de clés (distinctes) k et k′ telles que h(k) = h(k′). La figure 3.1 illustre la survenue d’une telle collision entre les clés k1 et k3 distinctes qui sont telles que h(k1) = h(k3).


Figure 3.1: Une collision dans une table de hachage.

Précisons un peu le problème, supposons que la collision survient lors de l’ajout de l’élément d’information v3 de clé k3, alors qu’il existe déjà dans la table une clé k1 avec h(k1) = h(k3). La question est alors : où ranger l’information associée à la clé k3 ?

3.2.3  Résolution des collisions par chaînage

La solution la plus simple pour résoudre les collisions consiste à mettre tous les éléments d’information dont les clés ont même valeur de hachage dans une liste. On parle alors de résolution des collisions par chaînage. Dans le cas de l’exemple de collision de la figure 3.1, on obtient la situation de la figure 3.2.


Figure 3.2: Résolution des collisions par chaînage.

On remarque que les éléments de la table t sont tout bêtement des listes d’association, la liste t[i] regroupant tous les éléments d’information (k,v) de la table qui sont tels que h(k) vaut l’indice i.

Nous proposons une nouvelle implémentation H des tables d’associations Assoc, en encapsulant cette fois une table de hachage.

class H implements Assoc {
  final static int SIZE=1024 ; // Assez grand ?
  private AList [] t ; // Tableau interne de listes d'associations.

  H() { t = new AList [SIZE] } ;

  private int hash(String key) { return Math.abs(key.hashCode()) % t.length ;}

  public int get(String key) {
    int h = hash(key) ;
    AList r = AList.getCell(key, t[h]) ;
    if (r == null) {
      return 0 ;
    } else {
      return r.val ;
    }
  }

  public void put(String key, int val) {
    int h = hash(key) ;
    AList r = AList.getCell(key, t[h]) ;
    if (r == null) {
      t[h] = new AList(key, val, t[h]) ;
    } else {
      r.val = val ;
    }
  }
}

Le code de la fonction de hachage hash est en fait assez simple, parce qu’il utilise la méthode de hachage des chaînes fournie par Java (toute la complexité est cachée dans cette méthode) dont il réduit le résultat modulo la taille du tableau interne t, afin de produire un indice valide. La valeur absolue Math.abs est malheureusement nécessaire, car pour n négatif, l’opérateur « reste de la division euclidienne » % renvoie un résultat négatif (misère).

Il est surtout important de remarquer :

Estimons le coût de put et de get pour une table qui contient N éléments d’information. On suppose que le coût du calcul de la fonction hachage est en O(1), et que hachage est uniforme, c’est-à-dire que la valeur de hachage d’une clé vaut h ∈ [0…m[ avec une probabilité 1/m. Ces deux hypothèses sont réalistes. Pour la première, en supposant que le coût de calcul de la fonction de hachage est proportionnel à la longueur des mots, nous constatons que la longueur des mots d’un texte ordinaire de N mots est faible et indépendante de N.2 La seconde hypothèse traduit simplement que nous disposons d’une « bonne » fonction de hachage, faisons confiance à la méthode hashCode des String.

Sous ces deux hypothèses, la recherche d’un élément se fait en moyenne en temps Θ(1+α), où α = n/m est le facteur de charge (load factor) de la table (n est le nombre de clés à ranger et m est la taille du tableau). Plus précisément une recherche infructueuse dans la table parcourt en moyenne α cellules de listes, et une recherche fructueuse 1 + α/2 − 1/(2m) cellules, coûts auquels on ajoute le coût du calcul de la fonction de hachage. Ce résultat est démontré dans [2, section 12.2], contentons nous de remarquer que α est tout simplement la longueur moyenne des listes d’associations t[h].

Peut-être faut il remarquer que le coût d’une recherche dans le cas le pire est O(n), quand toutes les clés entrent en collision. Mais employer les tables de hachage suppose de faire confiance au hasard (hachage uniforme) et donc de considérer plus le cas moyen que le cas le pire. Une façon plus concrète de voir les choses est de considérer que, par exemple lors du comptage des mots d’un texte, on insère et recherche de nombreux mots uniformément hachés, et que donc le coût moyen donne une très bonne indication du coût rencontré en pratique.

Dans un premier temps, pour notre implémentation simple de H qui dimensionne le tableau t initialement, nous pouvons interpréter le résultat de complexité en moyenne d’une recherche en Θ(1 + α), en constatant que si la taille du tableau interne est de l’ordre de n, alors nous avons atteint un coût (en moyenne) de put et get en temps constant. Il peut sembler que nous nous sommes livrés à une suite d’approximations et d’à-peu-près, et c’est un peu vrai. Il n’en reste pas moins, et c’est le principal, que les tables de hachage sont efficaces en pratique, essentiellement sous réserve que pour une exécution donnée, les valeurs de hachage des clés se répartissent uniformément parmi les indices du tableau interne correctement dimensionné, mais aussi que le coût du calcul de la fonction de hachage ne soit pas trop élevé. Dans cet esprit pragmatique, on peut voir la table de hachage comme un moyen simple de diviser le coût des listes d’association d’un facteur n, au prix de l’allocation d’un tableau de taille de l’ordre de n.

3.2.3.1  Complément : redimensionnement dynamique

Dans un deuxième temps, il est plus convenable, et ce sera aussi plus pratique, de redimensionner dynamiquement la table de hachage afin de maintenir le facteur de charge dans des limites raisonnables. Pour atteindre un coût amorti en temps constant pour put, il suffit de deux conditions (comme pour push dans le cas des piles, voir 2.2.1)

Définissons d’abord une constante alpha qui est notre borne supérieure du facteur de charge, et une variable d’instance nbKeys qui compte le nombre d’associations effectivement présentes dans la table.

  final static double alpha = 4.0 ;
  private int nbKeys = 0 ;
  final static int SIZE = 16 ;

Nous avons aussi changé la valeur de la taille par défaut de la table, afin de ne pas mobiliser une quantité conséquente de mémoire a priori. C’est aussi une bonne idée de procéder ainsi afin que le redimensionnement ait effectivement lieu et que le code correspondant soit testé.

La méthode de redimensionnement resize, à ajouter à la classe H double la taille du tableau interne t.

  private void resize() {
    int old_sz = t.length ;     // Ancienne taille
    int new_sz = 2*old_sz ;     // Nouvelle taille
    AList [] oldT = t ;         // garder une référence sur l'ancien tableau
    t = new AList [new_sz] ;    // Allouer le nouveau tableau
    /* Insérer toutes les paires clé-information de oldT
       dans le nouveau tableau t */

    for (int i = 0 ; i < old_sz ; i++) {
      for (AList p = oldT[i] ; p != null ; p = p.next) {
        int h = hash(p.key) ;
        t[h] = new AList (p.key, p.val, t[h]) ;
      }
    }
  }

Il faut noter que la fonction de hachage hash qui transforme les clés en indices du tableau t dépend de la taille de t (de fait son code emploie this.t.length). Pour cette raison, le nouveau tableau est directement rangé dans le champ t de this et une référence sur l’ancien tableau est conservée dans la variable locale oldT, le temps de parcourir les paires clé-information contenues dans les listes de l’ancien tableau pour les ajouter dans le nouveau tableau t. Le redimensionnement n’est pas gratuit, il est même assez coûteux, mais il reste bien proportionnel au nombre d’informations stockées — sous réserve d’un calcul en temps constant de la fonction de hachage.

C’est la méthode put qui tient à jour le compte nbKey et appelle le méthode resize quand le facteur de charge nbKeys/t.length dépasse alpha.

  public void put(String key, int val) {
    int h = hash(key) ;
    AList r = AList.getCell(key, t[h]) ;
    if (r == null) {
      t[h] = new AList(key, val, t[h]) ;
      nbKeys++ ;
      if (t.length * alpha < nbKeys) {
        resize() ;
      }
    } else {
      r.val = val ;
    }
  }

Notez que le redimensionnement est, le cas échéant, effectué après ajout d’une nouvelle association. En effet, la valeur de hachage h n’est valide que relativement à la longueur de tableau t.

3.2.4  Adressage ouvert

Dans le hachage à adressage ouvert, les éléments d’informations sont stockés directement dans le tableau. Plus précisément, la table de hachage est un tableau de paires clé-information. Le facteur de charge α est donc nécessairement inférieur à un. Étant donnée une clé k on recherche l’information associée à k d’abord dans la case d’indice h(k), puis, si cette case est occupée par une information de clé k′ différente de k, on continue la recherche en suivant une séquence d’indices prédéfinie, jusqu’à trouver une case contenant une information dont la clé vaut k ou une une case libre. Dans le premier cas il existe un élément de clé k dans la table, dans le second il n’en existe pas. La séquence la plus simple consiste à examiner successivement les indices h(k), h(k)+1, h(k)+2 etc. modulo m taille de la table. C’est le sondage linéaire (linear probing).

Pour ajouter une information (k,v), on procède exactement de la même manière, jusqu’à trouver une case libre ou une case contenant la paire (k, v′). Dans les deux cas, on dispose d’une case où ranger (k,v), au besoin en écrasant la valeur v′ anciennement associée à k. Selon cette technique, une fois entrée dans la table, une clé reste à la même place dans le tableau et est accédée selon la même séquence, à condition de ne pas supprimer d’informations, ce que nous supposons.

Pour coder une nouvelle implémentation O de la table d’association Assoc, qui utilise le hachage avec adressage ouvert. Nous définissons d’abord une classe des paires clé-information.

class Pair {
  String key ; int val ;

  Pair(String key, int val) { this.key = key ; this.val = val ; }
}

Les objets O possèdent en propre un tableau d’objets Pair. Le code de la classe O est donné par la figure 3.3.


Figure 3.3: Implémentation d’une table de hachage à adressage ouvert
class O implements Assoc {
  private final static int SIZE = 1024 ; // Assez grand ?
  private Pair [] t ;     // Tableau interne de paires

  O() { t = new Pair[SIZE] ; }

  private int hash(String key) { return Math.abs(key.hashCode()) % t.length ; }

  /* Méthode de recherche de la case associée à key */
  private int getSlot(String key) {
    int h0 = hash(key) ;
    int h = h0 ;
    do {
      /* Si t[h] est « vide » ou contient la clé key, on a trouvé */
      if (t[h] == null || key.equals(t[h].key)) return h ;
      /* Sinon, passer à la case suivante */
      h++ ;
      if (h >= t.length) h = 0 ;
    } while (h != h0) ;
    throw new Error ("Table pleine") ; // On a fait le tour complet
  }

  public int get(String key) {
    Pair p = t[getSlot(key)] ;
    if (p == null) {
      return 0 ;
    } else {
      return p.val ;
    }
  }

  public void put(String key, int val) {
    int h = getSlot(key) ;
    Pair p = t[h] ;
    if (p == null) {
      t[h] = new Pair(key, val) ;
    } else {
      p.val = val ;
    }
  }
}

Dans le constructeur, les cases du tableau new Pair [SIZE] sont implicitement initialisées à null (voir B.3.6.2), qui est justement la valeur qui permet à getSlot d’identifier les cases « vides ». La méthode getSlot, chargée de trouver la case où ranger une association en fonction de la clé, est appelée par les deux méthodes put et get. La relative complexité de getSlot justifie cette organisation. La méthode getSlot peut échouer, quand la table est pleine — notez l’emploi de la boucle do, voir B.3.4, ce qui rend la question du dimensionnement du tableau interne plus critique que dans le cas du chaînage.

Exercice 3.1   Modifier le code de la classe O afin de redimensionner automatiquement le tableau interne, dès que le facteur de charge dépasse une valeur critique alpha.
  final static double alpha = 0.5 ;
Solution. Comme dans le cas du chaînage, nous allons écrire une méthode privée resize chargée d’agrandir la table quand elle devient trop chargée. La méthode put est modifiée pour gérer le compte nbKeys des informations effectivement présentes dans la table, et appeler resize si besoin est.
  private int nbKeys = 0 ;

  public void put(String key, int val) {
    int h = getSlot(key) ;
    Pair p = t[h] ;
    if (p == null) {
      nbKeys++ ;
      t[h] = new Pair(key, val) ;
      if (t.length * alpha < nbKeys) resize() ;
    } else {
      p.val = val ;
    }
  }
La méthode resize fait appel à getSlot pour transférer les informations de l’ancienne à la nouvelle table. C’est le meilleur moyen de garantir des ajouts compatibles avec les méthodes put et get.
  private void resize() {
    int old_sz = t.length ;
    int new_sz = 2*old_sz ;
    Pair [] oldT = t ;

    t = new Pair[new_sz] ;
    for (int k = 0 ; k < old_sz ; k++) {
      Pair p = oldT[k] ;
      if (p != null) t[getSlot(p.key)] = p ;
      }
    }
  }
Il faut, comme dans le cas du chaînage, prendre la précaution de ranger le nouveau tableau dans la variable d’instance t avant de commencer à calculer les valeurs de hachage dans le nouveau tableau. On note aussi que oldT[k] peut valoir null et qu’il faut en tenir compte. □

On démontre [6, section 6.4] qu’une recherche infructueuse entraîne en moyenne l’examen d’environ 1/2·(1 + 1/(1−α)2) cases et une recherche fructueuse d’environ 1/2·(1 + 1/(1−α)), où α est le facteur de charge et sous réserve de hachage uniforme. Ces résultats ne sont stricto sensu plus valables pour α proche de un, mais les formules donnent toujours un majorant. Bref, pour un facteur de charge de 50 % on examine en moyenne pas plus de trois cases.

Le sondage linéaire provoque des phénomènes de regroupement (en plus des collisions). Considérons par exemple la table ci-dessous, où les cases encore libres sont en blanc :

En supposant que h(k) soit distribué uniformément, la probabilité pour que la case i soit choisie à la prochaine insertion est la suivante

     
  P(0)= 1/19    P(2)= 2/19    P(3)= 1/19    P(8)= 5/19    P(9)= 1/19  
P(12)= 3/19    P(13)= 1/19    P(14)= 1/19    P(16)= 2/19    P(18)= 2/19  

Comme on le voit, la case 8 a la plus grande probabilité d’être occupée, ce qui accentuera le le regroupement des cases 4–7. Ce phénomène se révèle rapidement quand des clés successives sont hachées sur des entiers successifs, un cas qui se présente en pratique avec le hachage modulo (voir 3.3), quand les clés sont par exemple les valeurs successives d’un compteur, ou, dans des applications plus techniques, des adresses d’objets qui se suivent dans la mémoire.

Plusieurs solutions ont été proposées pour éviter ce problème. La meilleure solution consiste à utiliser un double hachage. On se donne deux fonctions de hachage h : U → {0, …, m−1} et h′ : U → {1, …, r−1} (r < m). Ensuite le sondage est effectué selon la séquence h(k) + h′(k), h(k) + 2h′(k), h(k) + 3h′(k), etc. Les regroupements ne sont plus à craindre essentiellement parce que l’incrément de la séquence est lui aussi devenu une fonction uniforme de la clé. En particulier en cas de collision selon h, il n’y a aucune raison que les sondages se fassent selon le même incrément. Pour que le sondage puisse parcourir toute la table on prend h′(k) > 0 et h′(k) premier avec m taille de la table. Pour ce faire on peut prendre m égal à une puissance de deux et h′(k) toujours impair, ou m premier et h′(k) strictement inférieur à m (par exemple pour des clé entières h(k) = k modm et h′(k) = 1 + (k mod(m−2))

Dans [6, section 6.4] D. Knuth montre que, sous des hypothèses de distribution uniforme et d’indépendance des deux fonctions de hachage, le nombre moyen de sondages pour un hachage double est environ −ln(1−α)/α en cas de succès et à 1/(1−α) en cas d’échec.3 Le tableau ci-dessous donne quelques valeurs numériques :

Facteur de charge50 %80 %90 %99 %
Succès1.392.012.564.65
Echec2.005.0010.00100.00

Comme on le voit α = 80 % est un excellent compromis. Insistons sur le fait que les valeurs de ce tableau sont indépendantes de n. Par conséquent, avec un facteur charge de 80 %, il suffit en moyenne de deux essais pour retrouver un élément, même avec dix milliards de clés ! Notons que pour le sondage linéaire cet ordre de grandeur est atteint pour des tables à moitié pleines. Tandis que pour le chaînage on peut aller jusqu’à un facteur de charge d’environ 4.

En fixant ces valeurs de facteur de charge pour les trois techniques, nous égalisons plus ou moins les temps de recherche. Examinons alors la mémoire occupée pour n associations. Nous constatons que le chaînage consomme un tableau de taille n/4 plus n cellules de listes à trois champs, soit 3 + n/4 + 5·n cases de mémoire en Java, en tenant compte de deux cases supplémentaires par objet (voir 2.4). Tandis que le sondage linéaire consomme 3 + 2·n + 4·n (tableau et paires), et le double hachage 3 + 5/4·n + 4·n (tableau et paires encore). Le gain des deux dernières techniques est donc minime, mais on peut coder avec moins de mémoire (par exemple en gérant deux tableaux, un pour les clés, un pour les valeurs). L’espace mémoire employé devient alors respectivement 6 + 4·n et 6 + 5/2·n, soit finalement une économie de mémoire conséquente pour le double hachage.

3.2.5  Tables de hachage de la libraire

Il aurait été étonnant que la libraire de Java n’offre pas de table de hachage, tant cette structure est utile. La classe HashMap est une classe générique HashMap<K,V> paramétrée par les classes des clés K et des informations V (voir 2.2.3). On écrit donc une dernière implémentation, très courte, de notre interface Assoc.

import java.util.* ;
class Lib implements Assoc {
  private HashMap<String,Integer> t ;

  H() { t = new HashMap<String,Integer> () ; }

  public int get(String key) {
    Integer val = t.get(key) ;
    if (val == null) {
      return 0 ;
    } else {
      return val ;
    }
  }

  public void put(String key, int val) { t.put(key,val) ; }
}

La table de hachage t est construite avec la taille initiale et le facteur de charge par défaut (respectivement 16 et 0.75). Les méthodes t.put et t.get sont celles des HashMap, qui se comportent comme les nôtres. À ceci près que clés et informations sont obligatoirement des objets et que l’appel t.get(key) renvoie null quand la clé key n’est pas dans la table t, fait que nous exploitons directement dans notre méthode get. On note la conversion automatique d’un Integer en int (return val dans le corps de get) et d’un int en Integer (appel t.put(key,val) dans put).

3.2.6  Performance

Nous nous livrons à une expérience consistant à appliquer le programme Freq à une série de fichiers contenant du source Java. Nous mesurons le temps cumulé d’exécution de la méthode count (celle qui lit les mots un par un et accumule les comptes dans la table d’association Assoc, section 3.1.1), pour les quatre implémentations des tables d’associations.

Toutes les tables de hachage sont redimensionnées automatiquement.


Figure 3.4: temps d’exécution de la méthode count

Les résultats (figure 3.4) font clairement apparaître que les listes d’associations sont hors-jeu et que les tables de hachage ont le comportement linéaire attendu et même que toutes les implémentations des tables de hachages se valent, au moins dans le cadre de cet expérience.

En dernière analyse, l’efficacité des tables de hachage repose sur l’uniformité de la fonction de hachage des chaînes de Java, c’est donc surtout cette dernière qui se montre performante ici. En voici pour preuve (figure 3.5) l’histogramme des effectifs des longueurs des listes de collisions à la fin de l’expérience H (tableau de taille m = 4096, nombre d’associations n = 16092). Cette figure montre par exemple qu’il y a un peu plus de 800 listes de collisions de longueur trois.


Figure 3.5: Répartition des collisions

En conclusion l’intérêt en pratique des tables de hachage est très important, compte tenu des performances atteintes pour une difficulté de réalisation particulièrement faible (surtout si on utilise la bibliothèque).

Si cela vous intéresse, le source complet de la classe Freq est donné comme une archive (source count.tar). Attention quand même, ces programmes dépassent largement le cadre du cours. Vous pouvez regarder en particulier, la classe WordReader (source WordReader.java) réalisée avec un Scanner (voir B.5.5.2), et le tri final, par emploi du tri des List de la classe Collections effectué dans la classe Sort (source Sort.java). L’objet List est fabriqué par la méthode toString des tables d’associations, voir par exemple celle des objets de la classe L (source L.java) des tables d’association implémentées par les listes (source AList.java).

3.3  Choix des fonctions de hachage

3.3.1  En théorie

Rappelons qu’une fonction de hachage est une fonction h: U → {0, … m−1}. Une bonne fonction de hachage doit se rapprocher le plus possible d’une répartition uniforme. Formellement, cela signifie que si on se donne une probabilité P sur U et que l’on choisit aléatoirement chaque clé k dans U, on ait pour tout j avec 0 ≤ jm−1,

 
{k ∣ h(k) = j}
 P(k) = 
1
m

En pratique, on connaît rarement la probabilité P et on se limite à des heuristiques. En particulier, on veut souvent que des clés voisines donnent des valeurs de hachages très distinctes.

Le cas que nous traitons ci-dessous est celui où l’univers U est un sous-ensemble des entiers naturels, car on peut toujours se ramener à ce cas. Par exemple, si les clés sont des chaînes de caractères, on peut interpréter chaque caractère comme un chiffre d’une base B et la chaîne comme un entier écrit dans cette base. C’est à dire que la chaîne a0a1an−1 est l’entier a0·Bn−1 + a1· Bn−2 + ⋯ + an−1. Si les caractères sont quelconques on a B = 216 en Java et B = 28 en C ; si les caractères des clés sont limités à l’alphabet minuscule, on peut prendre B=26 ; etc.

Nous pouvons donc revenir aux fonctions de hachage sur les entiers. Une technique courante consiste à prendre pour h(k) le reste de la division de k par m :

h(k) = k mod m

Mais dans ce cas, certaines valeurs de m sont à éviter. Par exemple, si on prend m = 2r, h(k) ne dépendra que des r derniers bits de k. Ce qui veut dire, par exemple, que le début des chaînes longues (vues comme des entiers en base B = 2p) ne compte plus, et conduit à de nombreuses collisions si les clés sont par exemple des adverbes (se terminant toutes par ment). Dans le même contexte, si on prend m = B−1, l’interversion de deux caractères passera inaperçue. En effet, comme (a·B + b) − (b·B + a) = (ab)(B −1), on a

a·B + b ≡ b·B + a (mod m ) 

En pratique, une bonne valeur pour m est un nombre premier tel que Bk ± a n’est pas divisible par m, pour des entiers k et a petits.

Une autre technique consiste à prendre

h(k) = ⌊ m (Ck − ⌊ Ck ⌋) ⌋

C est une constante réelle telle que 0 < C < 1. Cette méthode a l’avantage de pouvoir s’appliquer à toutes les valeurs de m. Il est même conseillé dans ce cas de prendre m = 2r pour faciliter les calculs. Pour le choix de la constante C, Knuth recommande le nombre d’or, C = (√5 − 1)/ 2 ≈ 0,618.

3.3.2  En pratique

Continuons de considérer les chaînes comme des entiers en base 216. Ces entiers sont très vite grands, ils ne tiennent plus dans un int dès que la chaîne est de taille supérieure à 2. On ne peut donc pas (pour un coût raisonnable, il existe des entiers en précision arbitraire) d’abord transformer la chaîne en entier, puis calculer h. Dans le cas du hachage modulo un nombre premier, il reste possible de calculer modulo m. Mais en fait ce n’est pas très pratique : la fonction de hachage (méthode hashCode) des chaînes de Java est indépendante de la tailles des tableaux internes des tables, puisqu’elle est définie dans la classe des chaînes et ne prend pas une taille de tableau en argument. À toute chaîne elle associe un int qui est ensuite réduit en indice. Selon la documentation, l’appel hashCode() de la chaîne a0a1an−1 renvoie a0·31n−1 + a1·31n−2 + ⋯ + an−2·31 + an−1. Autrement dit le code de hashCode pourrait être celui-ci :

public int hashCode() {
  int h = 0 ;
  for (int k = 0 ; k < this.length ; k++)
    h = 31 * h + this.charAt(k) ;
  return h ;
}

Dans nos tables de hachage nous avons ensuite simplement réduit cet entier modulo la taille du tableau interne.

Le calcul h = 31 * h + this.charAt(k) effectue un mélange entre une valeur courante de h (qui est la valeur de hachage du préfixe de la chaîne) et la valeur de hachage d’un caractère de la chaîne qui est le caractère lui-même, c’est-à-dire son code en Unicode (voir B.3.2.3). Le multiplicateur 31 est un nombre premier, et ce n’est pas un hasard. L’expérience nous a montré que ce mélange simple fonctionne en pratique, sur un ensemble de clés qui sont les mots que l’on trouve dans des sources Java (voir en particulier la figure 3.5). Pour des clés plus générales cette façon de mélanger est critiquée [8], mais nous allons nous en tenir à elle.

Car il faut parfois construire nos propres fonction de hachage, ou plus exactement redéfinir nos propres méthodes hashCode. Notre table de hachage H appelle d’abord la méthode hashCode d’une clé (pour trouver un indice dans le tableau interne, section 3.2.3), puis la méthode equals de la même clé (pour par exemple trouver sa place dans une liste de collision, section 3.1.2). La table de hachage de la librairie procède similairement. Or, même si tous les objets possèdent bien des méthodes hashCode et equals (comme ils possèdent une méthode toString), les méthodes par défaut ne conviennent pas. En effet equals par défaut exprime l’égalité physique des clés (voir B.3.1.1), tandis que hashCode renvoie essentiellement l’adresse en mémoire de l’objet ! Il faut redéfinir ces deux méthodes, comme nous avons déjà parfois redéfini la méthode toString (voir B.2.3). La classe String ne procède pas autrement, son hashCode et son equals se basent non pas sur l’adresse en mémoire de la chaîne, mais sur le contenu des chaînes.

Supposons donc que nous voulions nous servir de paires d’entiers comme clés, c’est à dire d’objets d’une classe Pair.

class Pair {
  int x, y ;
  Pair (int x, int y) { this.x = x ; this.y = y ; }
}

Pour redéfinir hashCode nous utilisons tout simplement le mélangeur multiplicatif.

  public int hashCode() { return x * 31 + y ; }

La méthode redéfinie est déclarée public comme la méthode d’origine. Il importe en fait de respecter toute la signature de la méthode d’origine. Or, la signature de la méthode equals des Object (celle que nous voulons redéfinir) est :

  public boolean equals(Object o)

Nous écrivons donc (dans la classe Pair) :

  public boolean equals(Object o) {
    Pair p = (Pair)o ; // Conversion de type, échoue si o n'est pas un Pair
    return this.x == p.x && this.y == p.y ;
  }

Pour la conversion de type, voir B.3.2.2. Évidemment, pour que les tables de hachage fonctionnent correctement il faut que l’égalité selon equals (l’appel p1.equals(p2) renvoie true) entraîne l’égalité des code de hachage (p1.hashCode() == p2.hashCode()), ce que la documentation de la bibliothèque appelle le contrat général de hashCode.


1
Vous noterez la différence avec les classes Fifo et Stack du chapitre précédent
2
Un autre argument est de dire qu’il existe de l’ordre de N = K mots de taille inférieure à ℓ, où K est le nombre de caractères possibles. Dans ce cas le coût du calcul de la fonction de hachage est en O(log N), réputé indépendant de n pour nN.
3
Ces valeurs proviennent d’un modèle simplifié, et ont été vérifiées expérimentalement.

Previous Up Next