Les tables de hachage

Pour 47 stocké dans une table de 7 alvéoles, l'ordinateur va directement à l'alvéole 47 mod 7 = 5 au lieu de chercher dans toute la table.

Transformer une clé en position

Jusqu'ici, trouver une valeur voulait dire chercher : jusqu'à n étapes dans un tableau non trié ou une liste chaînée. Pourtant, les tableaux peuvent atteindre n'importe quelle position en une étape. Et si la clé elle-même indiquait la position ? Si tes clés étaient de petits nombres entiers, par exemple des numéros d'élèves de 0 à 99, tu pourrais garder un tableau de 100 cases et ranger l'élève k dans la case k. Les notes du MIT appellent cela un tableau à accès direct. Cela ne marche plus quand les clés possibles sont immenses, comme des numéros de téléphone ou des mots, car on ne peut pas se permettre une case pour chaque clé possible.

Une fonction de hachage résout ce problème en ramenant n'importe quelle clé dans une petite plage de positions, de 0 à m − 1. Une fonction simple pour les nombres entiers est h(k) = k mod m, le reste de la division par m. Le tableau de m cases est la table de hachage, et ses cases sont souvent appelées alvéoles (buckets). Pour stocker 47 avec m = 7, on calcule 47 mod 7 = 5 et on le range dans l'alvéole 5. Pour retrouver 47 plus tard, on refait le même calcul et on ne regarde que dans l'alvéole 5.

Collisions et chaînage

Il y a un problème. Avec 7 alvéoles et plus de 7 clés possibles, certaines clés doivent partager une alvéole : 12, 33 et 47 donnent toutes le reste 5. C'est ce qu'on appelle une collision, et les notes du MIT font remarquer qu'elle est inévitable, d'après le principe des tiroirs. Le remède habituel est le chaînage : chaque alvéole contient une petite liste, une chaîne, de toutes les clés hachées vers elle. Trouver 47 coûte alors 1 étape pour le hachage plus une comparaison pour chaque clé vérifiée dans la chaîne 5. Si 12 et 33 sont devant lui, cela fait 1 + 3 = 4 étapes.

Quelle est la longueur des chaînes ? Si les clés se répartissent uniformément, chaque chaîne contient environ n/m clés, un nombre appelé facteur de charge (taux de remplissage). Garde m à peu près aussi grand que n et les chaînes restent courtes : trouver, insérer et supprimer prennent alors en moyenne un nombre constant d'étapes. Le danger, c'est une mauvaise répartition. Si toutes les clés sont hachées vers la même alvéole, une seule chaîne contient les n clés et la table ne vaut pas mieux qu'une liste chaînée. Dans le labo, choisis 7 alvéoles et insère 14, 21 et 28 : elles atterrissent toutes dans l'alvéole 0.

Les tables de hachage en JavaScript

On écrit rarement une table de hachage soi-même, car JavaScript dispose de Map et de Set. La spécification ECMAScript dit qu'ils « doivent être implémentés à l'aide de tables de hachage ou d'autres mécanismes qui, en moyenne, offrent des temps d'accès sous-linéaires par rapport au nombre d'éléments ». Autrement dit, map.get(key) et set.has(x) doivent être plus rapides qu'une recherche dans toute la collection. MDN ajoute qu'une Map garde les clés dans l'ordre d'insertion et, contrairement à un objet ordinaire, ne contient aucune clé par défaut qui pourrait entrer en conflit avec les tiennes.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, sans parcourir la liste
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true