Les structures de données pour effectuer des recherches rapides ne manquent pas. Nous avons les arbres, lesquels viennent en plusieurs variétés dont les arbres simples, AVL, splay, rouge-noir, etc. Les arbres garantissent, pour la plupart, des temps de recherche espérés de O(m lg n), où n est le nombre de clefs, et m est le coût moyen de comparaison des clefs. Les arbres AVL uniformisent la profondeur des feuilles de façon à assurer un temps de recherche en pire cas de O(m lg n). Les arbres AVL ne tiennent pas compte de la distribution des accès; toutes les clefs sont supposées également probables. Les arbres splay tiennent compte de la distribution des clefs en propulsant la dernière clef accédée à la racine de l'arbre. Cette tactique est généralement sous-optimale, sauf pour certains types de distributions.

Une technique de recherche qui est souvent laissée pour compte, mais qui est très intéressante, c'est la table de hash, de « hachage » ou table à adressage dispersé.

Qu'est-ce qu'une table de hash? C'est une structure de données qui permet les recherches, insertions et suppressions en temps constant. Mais comment cela est-il possible, puisque les autres techniques sont en temps logarithmique? Les autres techniques (comme les arbres et la recherche dicotomique) sont basées sur la comparaison entre les clefs, où à chaque comparaison on élimine essentiellement la moitié des clefs, ce qui mène à un temps logarithmique, soit O(lg n). Une table de hash est une technique basée sur la transformation d'adresse.

L'idée de base d'une table de hash est d'associer à chaque clef (un entier, une chaîne de caractères, un record, etc.) une signature que l'on souhaite unique, le hash, qu'on utilise comme adresse dans un tableau. Le hashing consiste donc en la transformation d'une clef d'un type quelconque en un nombre d'apparence aléatoire. Pour minimiser la probabilité d'une collision, c'est-à-dire que deux clefs distinctes se voient attribué le même hash, on utilisera une table beaucoup plus grande que le nombre de clefs qu'on voudra y insérer. Comme les clefs seront disséminées dans la table, comme les valeurs hashées paraissent aléatoires, on parlera de table à adressage dispersé.

Quand on dit O(1), c'est bien entendu modulo le coût de calcul de la fonction de hash. Si m est la longueur de la clef (en bits, en octets) il faudra que la fonction de hash soit calculable en O(m) ou moins. Elle devra aussi être efficace dans un sens que nous definirons à la prochaine section

Enfin, puisqu'on accède aux éléments du tableau de façon apparemment aléatoire, il est primordial que l'on puisse avoir un accès très rapide aux cases du tableau, indépendamment de l'ordre dans lequel elles sont visitées. Il est préférable que la table tienne en mémoire centrale, ce qui assurerait un accès rapide et de coût égal à toutes les cases du tableau. Il n'est cependant pas impensable de maintenir la table sur disque, car le nombre espéré d'accès à la table pour trouver une clef demeure constant — une propriété que nous ne démontrerons pas ici.

Il arrive malheureusement que le hash ne soit pas unique, que deux clefs reçoivent la même adresse dans le tableau. On parle alors d'une collision. Il existe plusieurs façons de gérer les collisions, nous en verrons trois: l'adressage ouvert, la résolution chaînée et les buckets.

Nous verrons aussi quelles sont les propriétés souhaitables d'une fonction de hash et pourquoi une table de hash devrait être relativement ténue. Nous verrons quelques fonctions de hash primaires, et quelles sont les techniques que nous pouvons utiliser pour gérer les collisions, dont les fonction de hash secondaires.

Notez que cette petite introduction ne parle pas des fonctions de hash cryptographiques ayant pour but de fournir une signature sécuritaire pour l'authentification de documents ou d'individus. Ces algorithmes sont généralement très dispendieux à calculer, ce qui leur ôte tout intérêt pour les tables de hash. En effet, pour les tables de hash, on s'intéresse aux algorithmes qui produisent relativement peu de bits — 32 plutôt que, disons, 1024 — et qui le font très rapidement.

Notez aussi que cette introduction n'est pas exhaustive. Je ne parlerai pas de tables multi-niveaux, ni de hashing extensible. Je ne parlerai pas non plus de considérations de programmation concurrente où il serait nécessaire d'utiliser des mécanismes d'exclusion mutuelle pour gérer les accès à la table. Bien qu'intéressant, ce sujet est hors de la portée de cette introduction. Vous ne trouverez pas, non plus, de démonstrations mathématiques poussées; tout au plus une connaissance élémentaire des mathématiques est requise pour la lecture de cette introduction aux tables de hash.