retour


Composant hash : Les tables de hashage

Introduction

Dans la série des problèmes récurrents, l'accès rapide à des données indexées par des chaînes de caractères est un grand classique. S'il touche principalement la gestion des bases de données, il est en fait si présent dans les développements que des langages tels que perl incluent directement le type hash (préfixé lors de sa définition par le caractère %).

Ce type particuliers ne se retrouve pas dans la STL (Standard Template Library) du C++, mais seulement dans quelques unes de ses extentions ou contreparties commerciales (RogueWave). Les implémentations en C sont généralement ad hoc, à l'instar de celle décrite dans « Le langage C » du Kernigan et Ritchie. La Glib inclut aussi son implémentation. Cependant, si cette dernière est générique, elle n'inclut pas de gestion de verrou nécessaire au multithreading.

Nous allons étudier une implémentation générique en C des tables de hashage en essayant de prendre en compte la gestion des verrous.

Principe

Intuitivement, la recherche d'une chaîne de caractère dans un tableau nécessite la lecture et chacune des cases du tableau et la comparaison avec la chaîne de référence. Cette technique ne pose aucun soucis sur de petites tables.

recherche systématique simple
Figure 1: recherche systématique

D'un point de vue macroscopique, l'algorithme est en ordre de n (statistiquement n/2), où n est le nombre d'éléments du tableau. A cet ordre, un coefficient multiplicateur correspondant à la méthode de comparaison des chaînes (strcmp()) doit être appliqué. Statistiquement, on trouvera la solution après n/2 * smoy comparaison de caractères, ou smoy est la taille moyenne d'une chaîne de caractères.

Afin diminuer l'ordre de l'algorithme de recherche, on cherche à déplacer le problème. Puisque les chaînes de caractères sont difficiles à comparer, nous allons supposer une fonction particulière qui transforme une chaîne de caractères en un nombre entier. Cette fonction est appelée fonction de hashage. Cette fonction nous permettra de ne plus avoir à comparer deux chaînes, mais deux entiers, ce qui est biensur beaucoup plus rapide.

En poussant le raisonnement un peu plus avant, on pourra même supposer que l'entier en question pourrait même servir d'index en réglant quelques détails techniques.

Hashage servant d'index
Figure 2: Fonction de hashage servant d'index

Il existe deux catéfories de fonctions de hashage. Si la fonction est une application, i.e. est injective, ou encore, si toute chaîne passée en entrée de cette fonction produit un nombre unique, alors la fonction de hashage est dite parfaite.
Toute fonction de hashage fournissant le même nombre à partir de deux chaînes différentes est dite imparfaite.

D'un point de vue général, on peut penser que les chaînes de caractères n'auront a priori pas toutes la même taille. Et à l'exemple du C, Il n'y a pas de taille maximale pour une chaîne. Cependant, un entier, lui, est limité en taille. S'il est codé sur 32 bits, il ne pourra stocker de manière unique que des chaînes d'au maximum 32 caractères. On peut biensur jongler avec le nombre de caractères réellement admis dans une chaîne de caractères réelle. Cependant, nous resterions dans le cadre du code ascii. Or, dans les chaînes de caractères modernes, un caractère n'est pas obligatoirement codé sur 8bits (comme le code UTF, par exemple).

A contrario, un codage sur 32bits nous donnerait un tableau final de 232 = 4 294 967 296 entrées. Par comparaison, un petit dictionnaire papier comporte de l'ordre de la dizaine de miliers de mots. Indexer dans ce cas un dictionnaire par cette méthode « parfaite » ne prendrait pas en compte les mots de plus de 32 caractères et consommerait 4 294 967 296 * la taille de chaque entrée. Dans l'hypothèse ou chaque case est un pointeur de taille 4 octets, nous devrions réserver 232 * 4 octets, soit 16 Go. Même si la RAM est peu onéreuse et que nos disques durs sont gargantuesques, ce nombre parait un peu éléve. A fortiori si l'on considère que seulement 40 000 mots sont réellement indexés, soit un taux d'occupation de 1 pour 10 000.

Il apparaît donc évident que hormis dans certains cas particuliers, l'utilisation d'une fonction de hashage parfaite n'est pas une bonne solution.
Cependant, si notre fonction de hashage ne peut pas être parfaite, nous allons devoir affronter des collisions. En effet, si 2 chaînes différentes produisent un même entier, notre index correspondra à 2 chaînes différentes, mais une seule case de tableau. Nous devons donc faire intervenir un système de chaînage (voir Composants, réutilisation et généricité : Une application aux listes doublement chaînées) afin d'augmenter la capacité du tableau dans une autre dimension.

Gestion des collisions
Figure 3: gestion des collisions

Les fonctions de hashage dans leur ensemble sont assez nombreuses et complexes. Elles nous viennent directement de l'univers de la sécurité où elles sont utilisées comme signatures électroniques ou encore comme base de clefs de chiffrement. Elles ont pour but de réduire l'information tout en conservant les traits caractère. Elles sont supposées ne pas avoir de fonction réciproque. Pour n'en citer que quelques unes, nous avons les Message Digest (MD4, MD5), les Secure Hash Algorithm (SHA-1, SHA-2), ou autre RIPEMD.

Cependant, pour implémenter une table de hashage, les nombreuses contraintes de sécurité ne sont pas nécessaires. En général, il suffit de s'assurer que pour l'ensemble des chaînes à indexer, la fonction doit être raisonnablement homogène et ne pas favoriser les collisions. Une fonction classiquement utilisée est la suivante :

int hash_classic(char *name) {
	int accum = 0;
	int len;
	len = strlen(name));
	accum = 0;
	for (;len > 0; len--) {
		accum <<= 1;
		accum += (unsigned) (*name++ & 0xFF);        
	}
	return accum;
}

Il est bien évident que la valeur retournée (accum) n'est pas directement utilisable. En effet, accum est un entier (signé ou non). Nous n'alloueront en général jamais un tableau indexable par un entier (232 ou 264 possibilités en fonction du codage de l'entier). Au contraire, nous réserverons un tableau de taille raisonable (nous reverrons cette notion plus loin). Admettons que nous considérions un tableau de 500 cases. Dans ce cas, il faudrait convertir accum pour qu'il ne retourne que des valeurs comprises entre 0 et 499. A cette fin, nous pouvons utiliser l'opération en modulo (%) La dernière ligne de notre fonction classique sera donc :

	return accum % 500;

Architecture du composant hash

Notes préliminaires

Contraintes primaires

Pas d'a priori sur le contenu

La notion de généricité nécessitent impérativement de ne pas avoir d'a priori sur le type des données à . Ce point peut être géré en C++ par l'utilisation de types paramétres ou « templates ». En C, il suffira d'utiliser la notion de type générique représentée par void * et de savoir ce que l'on en fait.

Contrainte secondaire structurante

Enfin, il est nécessaire de prendre en compte la possibilité de multithreading. Cette contrainte n'est pas une contrainte primaire, mais elle ajoute des restriction structurantes au programme.
Nous devons en effet tenir compte des verrous mutuellements exclusifs (mutex locks), et nous devons nous arranger pour empêcher toute opération directe sur la structure de données. Il est donc nécessaire de cacher la structure aux programmes utilisateurs et de définir toutes les méthodes modifiant ou lisant les paramètres « visibles » du composant.

Structuration des données

structure de données

L'interface

« Constructeur » et « destructeur »

/* Constructor: */
/* Destructor :*/

Ajout d'éléments


Récupération d'un élément du « tableau »


Information et supervision






Limitations

Conclusion