Tables de hachage : fonction de hachage, gestion des collisions, dictionnaires

En 30 secondes

• Table de hachage : la fonction de hachage transforme une clé en indice, pour un accès en moyenne en O(1).
• Collision : deux clés au même indice. Le chaînage les range ensemble dans une liste chaînée à cet indice.
• Facteur de charge élevé = plus de collisions = complexité qui se dégrade vers O(n) dans le pire des cas.

Ce que tu sauras faire

• Décrire le rôle d'une fonction de hachage dans une table de hachage.
• Expliquer ce qu'est une collision et comment le chaînage la résout.
• Évaluer la complexité moyenne et la complexité dans le pire des cas des opérations sur un dictionnaire fondé sur une table de hachage.

Les mots à connaître

Table de hachage

une structure qui associe des clés à des valeurs, en utilisant une fonction de hachage pour déterminer l'indice de rangement de chaque clé.

Fonction de hachage

une fonction qui transforme une clé en un indice, c'est-à-dire un nombre entier compris dans les bornes de la table de hachage.

Indice

la position, dans la table de hachage, à laquelle une clé est rangée d'après le résultat de la fonction de hachage.

Le piège classique

Croire qu'une table de hachage garantit toujours un accès en O(1) : ce n'est vrai qu'en moyenne, quand les collisions restent rares.

L'astuce

Fonction de hachage = « range-clé » : elle calcule directement où ranger chaque clé dans la table.