DS 6 (MP2I 2022-2023) — Table de hachage avec chaînage¶

Devoir surveillé · MP2I · 2022-2023 · partie 3 du DS 6 (4 h au total)

Autres parties : 1. Arbres n-aires en C · 2 et 4. Recherche trichotomique, médians

3. Table de hachage avec chaînage¶

On va réaliser dans cette partie une table de hachage avec chaînage pour gérer les collisions en OCaml.

On va utiliser ici la fonction Hashtbl.hash qui a le prototype suivant :

val hash : 'a -> int

et qui à toute valeur x va associer un entier strictement positif hash x. On a la garantie que si x = y alors hash x = hash y.

Ensemble¶

On considère le problème plus simple vu en classe consistant à représenter un ensemble fini de valeurs.

Question 13

Quelle relation entre ce problème et celui de la création d'un dictionnaire ?

Corrigé

Il suffit de rajouter des couples (clé,valeur) et de ne considérer que la clé pour le hachage.

On va réaliser ici une table de hachage où les cases contiennent des listes de valeurs pour gérer les collisions.

On considère donc le type suivant :

type 'a table = 'a list array

Question 14

Écrire une fonction

val contient : 'a table -> 'a -> bool

qui indique si un élément est dans la table.

Corrigé

L'entier hash x est quelconque : on le réduit modulo la taille de la table pour obtenir un indice valide.

let contient t x = List.mem x t.(hash x mod Array.length t)

Question 15

Écrire une fonction

val ajoute : 'a table -> 'a -> unit

qui rajoute un élément dans la table.

Corrigé

let ajoute t x =
  let h = hash x mod Array.length t in
  t.(h) <- x :: t.(h)

Dictionnaire¶

On considère ici le type précédent enrichi pour des dictionnaires associant des 'a à des 'b.

type ('a, 'b) dico = ('a * 'b) list array

On continue encore avec le même principe de chaînage en cas de collision mais on ne le fait que sur la première composante du couple.

Question 16

Écrire une fonction

val assoc : ('a * 'b) list -> 'a -> 'b

qui prend une liste de couples l et une valeur x et renvoie le premier y tel que (x,y) soit dans l.

Si l'élément n'est pas dedans, on fera une erreur.

Corrigé

let rec assoc l x =
  match l with
  | [] -> failwith "Non présent"
  | (y,v)::q ->
    if x = y
    then v
    else assoc q x

Question 17

En déduire une fonction

val dico_recherche : ('a, 'b) dico -> 'a -> 'b

qui prend un dico d et une valeur x et renvoie un y associé.

Corrigé

let dico_recherche d x = assoc d.(hash x mod Array.length d) x

Question 18

Quels sont les défauts de cette implémentation comparativement à l'adressage ouvert vu en TP ?

Corrigé

Le problème est la fragmentation mémoire induite par les listes chaînées. Sans mécanisme particulier, chaque collision risque d'engendrer des lenteurs d'accès mémoire qui sont évitées par un tableau qui peut tenir complètement dans le cache du processeur.