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 :

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 :

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

– pour interroger l’annuaire :

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 c_i1, c_i2, ... c_ij ..., c_ip 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.

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

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

Voici donc la fonction d’association que nous utiliserons :

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

et quelques procédures auxiliaires :