Numérique et sciences informatiques (spécialité) · Terminale · Structures de données

Dictionnaires et tables de hachage

• Un dictionnaire (tableau associatif) range des couples clé : valeur ; chaque clé est associée à une seule valeur au plus.
• Une table de hachage est une façon de l'implémenter : une fonction de hachage $h$ calcule, à partir de la clé, la position de la donnée dans un tableau.
• Deux clés différentes peuvent donner le même indice : c'est une collision, qu'il faut gérer (chaînage, adressage ouvert).
• Recherche et insertion coûtent $O(1)$ en moyenne, mais peuvent coûter $O(n)$ dans le pire des cas ; l'ordre des clés n'est pas conservé.