Tableaux associatifs, hachage et sérialisation

Cours · informatique (MP2I/MPI), chapitre 12 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Une table de hachage : une fonction de hachage envoie chaque clé vers une case du tableau.

12.1 Indexer par autre chose qu'un entier

Un tableau associe une valeur à un entier compris entre $0$ et $n - 1$ , et l'accès est immédiat. Mais on veut souvent associer une valeur à un mot, à un nom, à une paire de coordonnées. C'est le tableau associatif : un ensemble de couples (clé, valeur), où la clé n'est plus un indice.

Trois réalisations ont déjà été rencontrées ou vont l'être, et elles se distinguent par un seul chiffre :

Réalisation	Recherche	Ce qu'elle exige de la clé	Chapitre
Liste de couples	$O (n)$	l'égalité	chap:sequentielles
Arbre de recherche	$O (lo g n)$	un ordre total	chap:tas
Table de hachage	$O (1)$ en moyenne	l'égalité, et une fonction de hachage	ici

La table de hachage est la plus rapide et la plus exigeante en garanties : son $O (1)$ est en moyenne, jamais dans le pire cas.

12.2 Le principe

Définition 12.1Fonction de hachage, table

Une fonction de hachage $h$ envoie une clé sur un entier de ${0, \dots, m - 1}$ , où $m$ est la taille du tableau sous-jacent. La valeur associée à la clé $c$ est rangée à l'indice $h (c)$ .

L'accès devient alors le calcul de $h (c)$ , puis un accès direct : $O (1)$ , si tout va bien.

ImportantCe que le programme exige, et ce qu'il n'exige pas

La phrase est explicite : « la construction d'une fonction de hachage et les méthodes de gestion des collisions éventuelles ne sont pas des exigibles du programme ».

On doit donc savoir utiliser une table de hachage, connaître son coût et ses limites. On n'a pas à savoir concevoir une bonne fonction de hachage, ni à connaître le détail des stratégies de résolution. Ce chapitre les présente néanmoins brièvement, parce qu'on ne peut pas juger un $O (1)$ « en moyenne » sans savoir de quoi il dépend.

12.3 Les collisions

Définition 12.2Collision

Deux clés distinctes $c_{1} \neq = c_{2}$ telles que $h (c_{1}) = h (c_{2})$ sont en collision.

Exercices du chapitre

Une mauvaise fonction de hachage, mesurée corrigé
Le facteur de charge, et ce qu'il permet de prévoir corrigé
Adressage ouvert : la suppression naïve casse la recherche corrigé
Le pire cas provoqué, chronométré corrigé
Problème — Le paradoxe des anniversaires, démontré et mesuré corrigé
Problème — L'aller-retour de la sérialisation d'un arbre corrigé

La suite du cours · Tous les exercices du chapitre