Les tables de hachage (hash)

• Les hashtables sont une deuxième forme d’index qui est aussi fréquemment utilisée, mais plutôt pour des relations temporaires conservées en mémoire. Le principe d’une table “hash” est le suivant.
• Les enregistrements sont répartis entre des bacs regroupés dans un tableau. Un bac peut contenir un ou plusieurs enregistrements (chaînage).
• On prévoit un nombre de bacs qui est supérieur au nombre d’enregistrements prévus, ce qui donne un nombre moyen d’enregistrements par bac inférieur à 1.
• Le numéro de bac dans lequel un enregistrement est placé est calculé à partir de la clé de l’enregistrement par une fonction “hash”. Une fonction “hash” idéale répartirait les enregistrements uniformément entre les bacs.
• Pour avoir accès à un enregistrement, il suffit de calculer son numéro de bac à l’aide de la fonction “hash”.
• Les fonctions “hash” parfaites n’existent pas, mais il est possible de trouver des fonctions “hash” qui donnent d’excellents résultats en pratique.
• Le temps d’accès à un enregistrement dans une table “hash” comportant n enregistrements est O(1), c’est-à-dire borné indépendamment de n.