Aller au contenu

Note

J'ai repris l'organisation de ce chapitre cette année.

Les arbres binaires de recherche, y compris les arbres auto-équilibrants (arbres 2-3, arbres rouges et noirs), sont présentés dans le chapitre sur les arbres ; ce chapitre se contente d'en déduire une implémentation des dictionnaires.

Principe d'un dictionnaire

Définition

Un dictionnaire est une structure de données abstraite permettant de représenter une association entre des clés et des valeurs.

Par exemple, on pourrait imaginer que les clés soient des chaînes de caractères et les valeurs des nombres.

Plus précisément, si le type des clés est k et celui des valeurs v, un dictionnaire est la donnée d'un type t (dépendant de k et de v) et des opérations :

  • création d'un dictionnaire vide
  • ajout d'une correspondance entre une clé c et une valeur x
  • suppression d'une correspondance associée à une clé
  • test de la présence d'une correspondance vis-à-vis d'une clé
  • récupération de la valeur associée à une clé

On remarque qu'il est possible d'avoir une structure mutable ou non. Dans une structure mutable, le dictionnaire est modifié par les opérations alors que dans une structure immuable, les opérations renverront un nouveau dictionnaire.

Un point crucial des dictionnaires est d'avoir une relation d'égalité, ou même une relation d'ordre sur les clés.

Interfaces immuable et mutable

En OCaml, on peut écrire ces deux interfaces ainsi. On a choisi de fusionner le test de présence et la récupération de la valeur en une seule opération renvoyant une option : la clé est présente si et seulement si le résultat est de la forme Some v.

(* Interface immuable *)
type ('k, 'v) dico
val vide : ('k, 'v) dico
val ajout : ('k, 'v) dico -> 'k -> 'v -> ('k, 'v) dico
val suppression : ('k, 'v) dico -> 'k -> ('k, 'v) dico
val recherche : ('k, 'v) dico -> 'k -> 'v option

(* Interface mutable *)
type ('k, 'v) dico
val dico_creer : unit -> ('k, 'v) dico
val dico_ajout : ('k, 'v) dico -> 'k -> 'v -> unit
val dico_supprime : ('k, 'v) dico -> 'k -> unit
val dico_cherche : ('k, 'v) dico -> 'k -> 'v option

La spécification attendue est la suivante : une recherche de c renvoie Some v si la dernière opération portant sur c est un ajout de (c, v), et None s'il n'y en a pas ou si c'est une suppression. En particulier, ajouter une clé déjà présente remplace la valeur associée, et supprimer une clé absente ne fait rien.

On a des interfaces analogues pour les ensembles finis : il suffit de retirer les valeurs.

Lien avec les ensembles finis

On retrouve beaucoup de points communs entre cette structure de données abstraite et celle d'ensembles finis. En effet, il suffit de considérer un ensemble fini de couples (clé, valeur) et de ne faire porter les comparaisons entre éléments de l'ensemble uniquement sur la première composante, la clé.

Ainsi, dans l'ensemble { ("riri", 12), ("fifi", 14) } on pourra récupérer le couple de la forme ("fifi", *) pour obtenir la valeur qui lui est associée.

Si on sait implémenter des ensembles finis, on peut en déduire une implémentation des dictionnaires.

Pour cela, il suffit de considérer une interface sur les ensembles finis permettant de définir sa propre fonction de comparaison, égalité ou ordre selon les cas. On va donc chercher à implémenter la structure, immuable ou mutable, suivante :

  • création d'un ensemble vide
  • ajout d'un élément
  • suppression d'un élément
  • test et récupération d'un élément

La récupération de l'élément est cruciale dans le cas des dictionnaires. En effet, dans l'exemple précédent, on obtiendra le couple ("fifi", 14) en testant la valeur "fifi" grâce à la fonction de comparaison ne portant que sur la première composante.

Remarque

Réciproquement, si on sait implémenter des dictionnaires, on en déduit une implémentation des ensembles finis : un ensemble d'éléments de type 'a est un dictionnaire de type ('a, unit) dico, l'élément étant la clé et la valeur associée étant toujours ().

Implémentation immuable : ABR

Dans cette implémentation, on utilise les arbres binaires de recherche (ABR) vus dans le chapitre sur les arbres et dont on sait qu'ils peuvent représenter des ensembles finis de valeurs pour lesquelles on a un ordre total.

Pour implémenter un dictionnaire, on considère un ensemble \(C\) totalement ordonné de clés et un ensemble \(V\) de valeurs. On va représenter un dictionnaire par un ABR étiqueté par \(C \times V\). Pour effectuer des opérations sur l'arbre, on se contente de regarder la première composante. Lors d'une recherche, on peut renvoyer la valeur.

On a alors ajout, suppression et recherche en \(O(h)\) où \(h\) est la hauteur de l'arbre, soit \(O(\log n)\) où \(n\) est le nombre d'entrées sous réserve de bon équilibrage des ABR (sinon \(h\) peut valoir \(n-1\)) : c'est le cas par exemple avec les arbres rouges et noirs.

L'implémentation se déduit alors très naturellement de celle des arbres binaires de recherche :

type ('a, 'b) dico = Nil
  | Noeud of ('a, 'b) dico * ('a * 'b) * ('a, 'b) dico

let rec recherche dico cle =
  match dico with
  | Nil -> None
  | Noeud(_, (y,v), _) when cle = y -> Some v
  | Noeud(g, (y,_), _) when cle < y -> recherche g cle
  | Noeud(_, _, d) -> recherche d cle

Pour l'ajout, on procède comme pour l'insertion dans un ABR, à une différence près : si la clé est déjà présente, on remplace la valeur associée au lieu d'ajouter un nouveau nœud, conformément à la spécification des dictionnaires.

let vide = Nil

let rec ajout dico cle v =
  match dico with
  | Nil -> Noeud(Nil, (cle, v), Nil)
  | Noeud(g, (y, w), d) ->
    if cle = y then Noeud(g, (cle, v), d)
    else if cle < y then Noeud(ajout g cle v, (y, w), d)
    else Noeud(g, (y, w), ajout d cle v)

La suppression est exactement la suppression dans un ABR (remplacement d'un nœud ayant deux enfants par la plus petite entrée de son sous-arbre droit), en ne comparant que les clés. Comme pour l'insertion, ces opérations reconstruisent uniquement les \(O(h)\) nœuds du chemin de la racine à la clé et partagent tous les autres sous-arbres avec l'arbre initial : l'ancienne version du dictionnaire reste utilisable, c'est une structure immuable.

Enfin, un parcours infixe d'un ABR énumère ses entrées par ordre croissant des clés (voir l'exercice du chapitre sur les arbres). On obtient donc en \(O(n)\) la liste triée des associations, ce qu'une table de hachage ne permet pas.

let vers_liste dico =
  let rec aux dico acc =
    match dico with
    | Nil -> acc
    | Noeud(g, e, d) -> aux g (e :: aux d acc)
  in
  aux dico []

Pour garantir une hauteur en \(O(\log n)\), on peut utiliser les arbres 2-3 ou les arbres rouges et noirs : il suffit d'y remplacer les étiquettes par des couples (clé, valeur) comparés selon leur première composante.

Implémentation mutable : les tables de hachage

Hachage

Le principe du hachage (hashing en anglais) est, étant donné un ensemble de valeurs \(E\) et un entier \(n\), de réaliser une bonne fonction

\[ h : E \rightarrow \range{0}{n-1} \]

Que veut-on dire par bonne fonction ? Naturellement, avec \(E\) infini ou de cardinal très grand devant \(n\), il est illusoire d'imaginer pouvoir réaliser une fonction injective. Cependant, on peut faire en sorte que deux valeurs proches aient des valeurs associées, on parle de hachés, différents. Cela représenterait ainsi une forme d'injectivité locale.

Quand \(x\neq y\) et \(h(x) = h(y)\), on dit que la paire \(\{x,y\}\) est une collision pour \(h\).

Exemple

Si \(E \subset \N\), on peut considérer le reste modulo \(n\) comme fonction de hachage. Des éléments consécutifs auront ainsi des hachés distincts.

Toutes les paires \(\{ k n + r, l n + r\}\), où \(k \neq l\) et \(r \in \range{0}{n-1}\), sont des collisions.

Ainsi, cette fonction est très prévisible.

Remarque

Dans un contexte cryptographique, par exemple pour stocker un mot de passe, on souhaite éviter de remonter du haché à la valeur. En effet, en cas de compromission des accès, il suffirait d'inverser \(h\) pour retrouver le mot de passe de l'utilisateur.

La fonction de l'exemple précédent est ainsi peu sécurisée.

Il existe des fonctions de hachage cryptographiques comme SHA-256 (SHA-1 est aujourd'hui considérée comme cassée) qui sont sécurisées mais peuvent être mal utilisées : en hachant tous les mots du dictionnaire, on peut constituer sa propre table de correspondance entre hachés et mots de passe (les rainbow tables en sont une version compacte). Une manière simple de s'en prémunir est de ne pas stocker les hachés des mots de passe mais ceux de la concaténation d'un mot de passe et d'une donnée générée par le serveur pour chaque utilisateur : le sel.

Tables de hachage pour un ensemble fini

L'idée première des tables de hachage pour stocker des éléments de \(E\) est d'utiliser un tableau de \(n\) cases et une fonction de hachage \(h : E \rightarrow \range{0}{n-1}\). Ainsi, pour stocker \(x \in E\), on le place dans le tableau à l'adresse \(h(x)\).

Naturellement, cette idée est très naïve en raison des collisions éventuelles. Tout l'intérêt des tables de hachage est donc de gérer les collisions. Il y a plusieurs stratégies plus ou moins efficaces en machine.

Pour chacune de ces stratégies, il sera donc nécessaire de faire plus de travail qu'un simple accès dans une case. En général, on a des stratégies qui sont linéaires dans le nombre d'éléments en collision. En pire cas, ce nombre est celui du nombre d'éléments. Mais, en pratique, si les collisions sont peu probables, trois éléments entrant en collision le seront encore moins, ce qui fait qu'on peut supposer que le nombre de collisions est faible devant le nombre d'éléments. On pourra donc faire l'hypothèse que les accès sont en \(O(1)\).

Plus précisément, sous l'hypothèse (idéale) que la fonction de hachage répartit les éléments uniformément et indépendamment dans les \(n\) cases, le nombre moyen d'éléments en collision avec un élément donné, pour \(m\) éléments stockés, est de l'ordre du facteur de charge \(\alpha = m/n\). Le coût moyen d'un accès est alors en \(O(1 + \alpha)\), donc en \(O(1)\) tant que \(m = O(n)\), ce que l'on garantit en agrandissant la table lorsqu'elle devient trop chargée.

On va montrer ici l'implémentation de différentes stratégies en utilisant un même cadre : on cherche à représenter un ensemble fini d'éléments de type 'a où on a une fonction de hachage hache : 'a -> int et un test de comparaison eq : 'a -> 'a -> bool testant l'égalité.

On considère aussi définie une constante n et l'assurance que hache x soit dans \(\range{0}{n-1}\).

Listes de collisions

La stratégie la plus simple de gestion des collisions est de ne pas stocker des éléments dans chaque case mais une liste chaînée d'éléments.

Cette stratégie a le désavantage de fragmenter la mémoire car il faut descendre le long des maillons.

type 'a htbl = 'a list array

let htbl_creer () = Array.make n []

let htbl_cherche t x =
  let found = ref None in
  List.iter (fun y -> if eq x y then found := Some y) t.(hache x);
  !found

let htbl_ajout t x =
  let h = hache x in
  if not (List.exists (eq x) t.(h)) then
    t.(h) <- x :: t.(h)

let htbl_supprime t x =
  let h = hache x in
  t.(h) <- List.filter (fun y -> not (eq x y)) t.(h)

Sondage linéaire

Pour éviter les listes chaînées, on peut stocker les éléments directement dans le tableau. Chaque case est alors libre ou occupée par un élément. Pour ajouter x, on calcule son haché \(i\), c'est-à-dire hache x. Si la case \(i\) est libre, on y range x. Sinon, on teste successivement les cases \(i+1 \bmod n\), \(i+2 \bmod n\), \(\dots\) jusqu'à trouver une case libre, dans laquelle on range x. On parle de sondage linéaire (ou de recherche linéaire), et plus généralement d'adressage ouvert (open addressing) puisque l'élément n'est pas forcément rangé à l'adresse donnée par son haché.

Pour rechercher x, on sonde de même les cases à partir de hache x : si on trouve x, il est présent, et si on tombe sur une case libre, il est absent, car il aurait sinon été rangé au plus tard dans cette case.

Exemple

Avec \(n = 4\) et hache x = x mod 4, on ajoute \(1492\), \(1515\) puis \(1939\) à une table vide. On a hache 1492 = 0 et \(1492\) est rangé en case \(0\). On a hache 1515 = 3 et \(1515\) est rangé en case \(3\). Enfin hache 1939 = 3, la case \(3\) est occupée, la case \(0\) aussi en revenant au début du tableau, et \(1939\) est rangé en case \(1\).

case 0 1 2 3
contenu 1492 1939 libre 1515

La suppression est plus délicate : on ne peut pas simplement libérer la case. Dans l'exemple précédent, si on supprime \(1515\) en libérant la case \(3\), une recherche de \(1939\) commence en case \(3\), la trouve libre, et conclut à tort que \(1939\) est absent.

On marque donc la case d'un élément supprimé comme une pierre tombale : lors d'une recherche, on passe par-dessus comme pour une case occupée, mais lors d'un ajout, on peut la réutiliser comme une case libre.

type 'a case = Vide | PierreTombale | Element of 'a

type 'a htbl_lin = 'a case array

let htbl_lin_creer () = Array.make n Vide

(* Renvoie Some (i, y) si t.(i) contient y égal à x, None sinon *)
let htbl_lin_trouve t x =
  let h = hache x in
  let rec aux k =
    if k = n then None
    else
      let i = (h + k) mod n in
      match t.(i) with
      | Vide -> None
      | Element y when eq x y -> Some (i, y)
      | _ -> aux (k + 1)
  in
  aux 0

let htbl_lin_cherche t x =
  match htbl_lin_trouve t x with
  | None -> None
  | Some (_, y) -> Some y

let htbl_lin_supprime t x =
  match htbl_lin_trouve t x with
  | None -> ()
  | Some (i, _) -> t.(i) <- PierreTombale

let htbl_lin_ajout t x =
  if htbl_lin_trouve t x = None then begin
    let h = hache x in
    let rec aux k =
      if k = n then failwith "Erreur : table pleine"
      else
        let i = (h + k) mod n in
        match t.(i) with
        | Element _ -> aux (k + 1)
        | Vide | PierreTombale -> t.(i) <- Element x
    in
    aux 0
  end

La correction repose sur l'invariant suivant : si un élément x est rangé dans la case \((\texttt{hache x} + k) \bmod n\), aucune des cases \((\texttt{hache x} + j) \bmod n\) pour \(j < k\) n'est Vide. L'ajout le préserve, car il range x dans la première case non occupée par un élément, et la suppression aussi, car elle ne crée jamais de case Vide. La recherche de x ne peut donc pas s'arrêter avant d'avoir atteint sa case.

Remarque

  • Avec cette stratégie, on stocke au plus \(n\) éléments : le facteur de charge \(\alpha\) est toujours inférieur à \(1\). Les éléments ont tendance à former des blocs de cases consécutives occupées, ce qui allonge les recherches quand \(\alpha\) se rapproche de \(1\). En pratique, on maintient \(\alpha\) assez petit, par exemple \(\alpha \le 2/3\), et le coût moyen d'un accès est alors en \(O(1)\) (admis).
  • Les pierres tombales ne disparaissent jamais et ralentissent les recherches. On s'en débarrasse en reconstruisant la table, ce qu'on fait de toute manière lors d'un redimensionnement.
  • L'intérêt de cette stratégie est que les cases parcourues sont contiguës en mémoire, ce qui est bien plus efficace en machine que de suivre des maillons dispersés.

Redimensionnement

On a supposé jusqu'ici que la taille \(n\) de la table était fixée. Si le nombre \(m\) d'éléments stockés devient grand devant \(n\), le facteur de charge \(\alpha = m/n\) augmente et les accès ne sont plus en temps constant. Comme on ne connaît pas en général \(m\) à l'avance, on fait grossir la table au fur et à mesure, comme pour un tableau dynamique : lorsque \(\alpha\) dépasse un seuil, on alloue une table deux fois plus grande et on y réinsère tous les éléments.

Il faut alors que la fonction de hachage dépende de la taille de la table. On se donne pour cela une fonction renvoyant un entier positif quelconque, comme Hashtbl.hash en OCaml, et on prend son reste modulo la taille courante. Les éléments changent donc de case lors d'un redimensionnement : on ne peut pas recopier le tableau tel quel, il faut réinsérer chaque élément.

Propriété

Si on double la taille de la table dès que le nombre d'éléments atteint la taille avant un ajout, une suite de \(m\) opérations partant d'une table de taille \(n_0\) effectue des redimensionnements de coût total \(O(n_0 + m)\). Le coût amorti d'un redimensionnement par opération est donc en \(O(1)\), et on a toujours \(\alpha \le 1\).

Preuve

Un redimensionnement depuis une table de taille \(s\) coûte \(O(s)\) : il faut allouer la nouvelle table et réinsérer les \(s\) éléments présents. Les tailles successives sont \(n_0, 2 n_0, 4 n_0, \dots, 2^p n_0\). Le dernier redimensionnement, depuis la taille \(2^{p-1} n_0\), a lieu quand la table contient \(2^{p-1} n_0\) éléments, donc après au moins autant d'ajouts, d'où \(2^{p-1} n_0 \le m\). Le coût total est alors en

\[ O\left(\sum_{i=0}^{p-1} 2^i n_0 \right) = O(2^p n_0) = O(n_0 + m) \]

Enfin, avant un ajout, soit le nombre d'éléments est strictement inférieur à la taille, soit il lui est égal et on double la taille : dans les deux cas, après l'ajout, le nombre d'éléments est au plus égal à la taille.

Implémentation d'un dictionnaire

Comme expliqué au début de ce chapitre, on obtient un dictionnaire à partir d'une table de hachage pour les ensembles finis en stockant des couples (cle, valeur), la fonction de hachage et le test d'égalité ne portant que sur la clé. Avec des listes de collisions, chercher la valeur associée à une clé dans une liste de couples, c'est exactement ce que fait List.assoc_opt, et List.remove_assoc supprime le couple associé à une clé.

On en déduit une implémentation de l'interface mutable avec redimensionnement. Ici, hache_cle renvoie un entier positif quelconque, par exemple let hache_cle = Hashtbl.hash, et on compare les clés avec = comme pour les ABR.

type ('k, 'v) dico = {
  mutable donnees : ('k * 'v) list array;
  mutable nb : int; (* nombre d'associations *)
}

let indice t c = hache_cle c mod Array.length t.donnees

let dico_creer () = { donnees = Array.make 8 []; nb = 0 }

let dico_cherche t c = List.assoc_opt c t.donnees.(indice t c)

let redimensionne t =
  let anciennes = t.donnees in
  t.donnees <- Array.make (2 * Array.length anciennes) [];
  Array.iter
    (List.iter (fun (c, v) ->
         let i = indice t c in
         t.donnees.(i) <- (c, v) :: t.donnees.(i)))
    anciennes

let dico_supprime t c =
  let i = indice t c in
  if List.mem_assoc c t.donnees.(i) then begin
    t.donnees.(i) <- List.remove_assoc c t.donnees.(i);
    t.nb <- t.nb - 1
  end

let dico_ajout t c v =
  dico_supprime t c;
  if t.nb = Array.length t.donnees then redimensionne t;
  let i = indice t c in
  t.donnees.(i) <- (c, v) :: t.donnees.(i);
  t.nb <- t.nb + 1

On a supprimé l'ancienne association avant l'ajout pour qu'une clé n'apparaisse qu'une fois, ce qui garantit que nb est bien le nombre de clés et qu'ajouter une clé présente remplace sa valeur. D'après la propriété précédente, on a toujours \(\alpha \le 1\) et, sous l'hypothèse d'un hachage uniforme, chaque opération est en \(O(1)\) en moyenne et en amorti.

Remarque

Le module Hashtbl d'OCaml fournit une telle table de hachage mutable, avec redimensionnement automatique : Hashtbl.create, Hashtbl.find_opt, Hashtbl.remove et Hashtbl.replace. Attention, Hashtbl.add n'a pas la même spécification que dico_ajout : si la clé est déjà présente, il ajoute une nouvelle association qui masque l'ancienne sans la supprimer, et celle-ci réapparaît après un Hashtbl.remove. C'est Hashtbl.replace qui remplace la valeur.