Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Combiner vecteurs et listes associatives : les hash tables
Article mis en ligne le 17 décembre 2004
dernière modification le 24 novembre 2015

par Laurent Bloch

Nous voulons construire une structure de données qui possède les avantages des structures de type fluide, telles que les listes, et des structures de type rigide, telles que les vecteurs, sans en avoir les inconvénients.

 À une liste je peux toujours ajouter un élément, en Scheme en tête de la liste, on dit que la liste est un type fluide. Le prix à payer pour cette fluidité est que le temps d’accès moyen à un élément d’une liste de N éléments est N/2, et que le temps observé dépend de la position de l’élément dans la liste.

 L’accès à l’élément de rang n d’un vecteur de N éléments se fait en un temps constant, et plus court que pour une liste parce que l’organisation des vecteurs est calquée sur celle de la mémoire physique de l’ordinateur. Le prix à payer pour ce déterminisme et cette rapidité est que la taille d’un vecteur est fixée une fois pour toutes à sa création et que l’on ne peut pas lui ajouter de nousveaux éléments (sauf à les mettre à la place d’autres éléments, qui se trouvent ainsi « écrasés »). On dit que le type vecteur est un type de données rigide.

La solution que nous allons présenter, que l’on appelle, au choix, tables à adressage dispersé, tables associatives ou mémoires associatives, et en anglais hash-tables, est en quelque sorte un hybride de vecteurs et de listes. Lorsqu’elle est réalisée et utilisée judicieusement, elle combine les avantages des uns et des autres, sans trop souffrir de leurs inconvénients.

Listes associatives

En préalable rappelons ce que sont les listes associatives (a-listes). C’est une structure de données très simple et très utilisée, qui consiste à ranger dans une liste des doublets clé-valeur : chaque doublet associe une valeur (par exemple un numéro de téléphone, une séquence nucléotidique, un âge...) à une clé (un prénom, un Accession Number, un nom de famille).

Scheme fournit la procédure assoc qui reçoit comme arguments la valeur d’une clé et le nom d’une liste associative, et qui répond, si la clé est présente dans la liste, par le doublet correspondant, et #f si aucune clé n’est égale à la valeur soumise.

Ainsi :

  1. (define Liste-des-ages
  2.    (list (cons "Haddock" 50) (cons "Tintin" 20) (cons "Milou" 5)))
  3. ;
  4. Liste-des-ages
  5. -> ((Haddock . 50) (Tintin . 20) (Milou . 5))
  6. ;
  7. (assoc "Tintin" Liste-des-ages)
  8. -> (Tintin . 20)
  9. ;
  10. (assoc "Tournesol" Liste-des-ages)
  11. -> #f

Télécharger

Principes de la méthode

Nous allons illustrer la méthode d’adressage dispersé par la construction d’un annuaire téléphonique de village avec des doublets nom-numéro, pour des raisons de commodité, parce que des doublets Accession Number-séquence nucléotidique seraient d’une manipulation plus laborieuse, mais le principe serait exactement le même.

Notre annuaire sera contenu dans un vecteur de taille N. Pour insérer à sa place chaque doublet représentatif d’un couple nom-numéro, nous allons essayer de construire une fonction f qui à un nom fasse correspondre un entier compris entre 0 et N-1. Le nom est utilisé comme clé d’accès à la table. Pour une valeur c de la clé, l’entrée de l’annuaire sera rangée dans l’élément du vecteur de rang i = f(c) (on dit aussi case, ou alvéole).

Cette fonction permettra également de retrouver le doublet à chaque interrogation, et ce en un laps de temps constant, égal au temps de calcul de la fonction plus le temps d’accès à un élément de vecteur.

La fonction f s’appelle la fonction d’association, ou d’adressage dispersé, ou de dispersion, ou de hash-coding.

Dès lors que le nombre d’habitants du village est supérieur à N, il va arriver qu’il faille mettre plusieurs doublets dans la même case, ou pour le dire plus formellement, que plusieurs valeurs de c donnent si on les soumet à f la même valeur de i. C’est ce que l’on appelle une collision.

En cas de collision, un doublet va vouloir se ranger dans un élément de vecteur déjà occupé. Afin de faire face à cette situation inévitable, chaque élément de vecteur ne sera pas un doublet, mais une liste associative.

Si N est suffisamment grand par rapport à la population téléphonique du village, et si la fonction f, à laquelle nous donnerons désormais son nom informatique hash, est choisie de sorte que les clés donnent des valeurs de i réparties le plus uniformément possible entre 0 et N-1, chaque case du vecteur contiendra une petite liste associative, et la recherche dans la table sera relativement efficace.

Application

Pour illustrer l’usage des vecteurs par leur application à la construction de tables associatives (hash-tables), nous prendrons comme exemple la réalisation d’un programme d’annuaire électronique simplifié.

Notre programme d’annuaire devra répondre aux messages suivants :

 pour introduire des données dans l’annuaire :

  1. 1:=> (cet-annuaire 'peupler)
  2. Entrez nom et numéro : "Edgar" 87
  3. Entrez nom et numéro : "Toto" 12
  4. Entrez nom et numéro : "Lili" 28
  5. Entrez nom et numéro : "Héloïse" 45
  6. Entrez nom et numéro : "" 0
  7. #f

Télécharger

Attention : les chaînes de caractères doivent être tapées entre guillemets.

 pour interroger l’annuaire :

  1. 1:=> (cet-annuaire 'interrogation "Toto")
  2. 12
  3. 1:=> (cet-annuaire 'interrogation "Albert")
  4. Pas d'abonné au numéro demandé
  5. 1:=> (cet-annuaire 'interrogation "Héloïse")
  6. 45

Télécharger

Pour améliorer le temps de réponse aux interrogations, ce programme gardera en mémoire l’ensemble de l’annuaire. La première idée qui vient à l’esprit sera de construire une liste d’associations : chaque personne identifiée dans l’annuaire sera représentée par un doublet dont le car sera une chaîne de caractères donnant son nom et le cdr son numéro de téléphone.

Ce programme naïf donnerait peut-être satisfaction si l’annuaire est petit, mais si les effectifs sont importants l’usage direct des listes d’associations aura vite deux inconvénients :

* à chaque ajout d’un nom dans l’annuaire, une nouvelle liste est créée par l’appel de cons, ce qui sera vite insupportable ;

* la consultation par assoc parcourt séquentiellement l’annuaire à chaque fois, ce qui va finir par prendre trop de temps, plus précisément le temps moyen d’accès à un élément de l’annuaire est une fonction linéaire de la taille de la liste.

Comment surmonter ces inconvénients ?

L’adressage associatif

Nous allons utiliser la méthode décrite ci-dessus.

L’idéal serait que la fonction f soit injective, c’est-à-dire que chaque valeur de i corresponde à une seule valeur possible de c. C’est malheureusement irréalisable. Même si on imagine pouvoir inventer une fonction telle que deux clés différentes ne puissent pas donner une même valeur de i, un exercice difficile et même insoluble dans le cas général, il faudrait avoir un vecteur dont la taille serait au moins égale au nombre de clés possibles, qui est immense.

Plusieurs valeurs de c peuvent donc donner par f la même valeur de i, c’est ce que l’on appelle une collision, ou une synonymie. En cas de collision, un doublet va vouloir se ranger dans un élément de vecteur déjà occupé. Afin de faire face à cette situation inévitable, chaque élément de vecteur ne sera pas un doublet, mais une liste associative.

Nous allons choisir une fonction f telle que chaque indice i corresponde à un ensemble de clés ci1, ci2, ... cij ..., cip d’effectifs sensiblement voisins ; s’il y a P individus dans notre annuaire, la longueur de chaque liste sera de l’ordre de P/N. Le choix judicieux de N et de f devrait assurer une efficacité raisonnable à l’algorithme. La théorie dit que c’est bien que N soit un nombre premier, nous prendrons donc 23.

Adressage associatif

Une façon simple d’associer un nombre à un nom, c’est d’aditionner les codes ASCII des caractères du nom :

  1. 1:=> (char->integer #\A)
  2. 65
  3. 1:=> (char->integer #\a)
  4. 97
  5. 1:=> (string->list "Edgar")
  6. (E d g a r)
  7. 1:=> (map char->integer (string->list "Edgar"))
  8. (69 100 103 97 114)
  9. 1:=> (apply + (map char->integer (string->list "Edgar")))
  10. 483

Télécharger

Ce nombre n’est pas compris entre 0 et N-1, mais le reste de sa division par N l’est :

  1. (remainder (apply + (map char->integer (string->list "Edgar")))  23)
  2. 0
  3. ;
  4. (remainder (apply + (map char->integer (string->list "Héloïse")))  23)
  5. 22

Télécharger

Voici donc la fonction d’association que nous utiliserons :

  1. (define (hash nom taille-table)
  2.     (remainder
  3.       (apply + (map char->integer (string->list nom)))
  4.       taille-table))

Télécharger

et le programme de création de l’annuaire :

  1. (define (make-annuaire)
  2.   (let* ((N 23) ; nombre d'éléments du vecteur
  3.          (un-annuaire (make-vector N '())))
  4.     (lambda message
  5.       (case (car message)
  6.         ((peupler)
  7.           (let boucle ()
  8.              (display "Entrez nom et numéro : ")
  9.              (let* ((le-nom (read))
  10.                     (numero (read)))
  11.                 (if (not (string=? le-nom ""))
  12.                     (begin
  13.                        (vec!:ajouter le-nom
  14.                                        numero
  15.                                        un-annuaire)
  16.                        (boucle))))))
  17. ;
  18.         ((interrogation)
  19.           (let* ((le-nom (cadr message))
  20.                  (la-case (hash le-nom N))
  21.                  (reponse
  22.                     (assoc le-nom (vector-ref
  23.                              un-annuaire la-case))))
  24.             (if reponse
  25.                (cdr reponse)
  26.                "Pas d'abonné au numéro demandé")))
  27.         ((donner)
  28.            un-annuaire)
  29.         ((afficher)
  30.          (vector:for-each print un-annuaire))))))

Télécharger

et quelques procédures auxiliaires :

  1. (define (vector:for-each proc V)
  2.   (let ((longueur (vector-length V)))
  3.     (let boucle ((index 0))
  4.        (if (not (= index longueur))
  5.           (begin
  6.              (proc (vector-ref V index))
  7.              (boucle (+ index 1)))))))
  8. ;
  9. (define (assoc!:ajouter nom numero liste)
  10.   (cons (cons nom numero) liste))
  11. ;
  12. (define (vec!:ajouter nom numero vecteur)
  13.   (let* ((N (vector-length vecteur))
  14.          (une-case (hash nom N))
  15.          (elem (vector-ref vecteur une-case)))
  16.     (vector-set! vecteur une-case
  17.                  (assoc!:ajouter nom numero elem))))

Télécharger