Qu'est-ce qu'une table de hachage?

Une table de hachage est une structure de données qui implémente un tableau associatif (dictionnaire). Elle stocke des paires "clé-valeur", où les clés sont uniques.

Principes de base:

• Fonction de hachage: Transforme la clé en un nombre (code de hachage ou indice). Cet indice indique l'emplacement du stockage de la valeur dans le tableau (caisse).
• Tableau (caisses): Stockage réel des paires "clé-valeur".
• Collisions: Situation où différentes clés génèrent le même code de hachage.

Solution aux collisions:

• Méthode de chaînage (Separate chaining): Chaque caisse contient une liste (ou une autre structure de données) d'éléments ayant le même code de hachage.
• Adressage ouvert (Open addressing): En cas de collision, la recherche d'une caisse libre se fait en utilisant différentes stratégies (sondage linéaire, sondage quadratique, double hachage).

Caractéristiques:

• Accès rapide: En cas idéal O(1) pour les opérations d'insertion, de recherche et de suppression.
• Dépendance de la fonction de hachage: La qualité de la fonction de hachage et la stratégie de résolution des collisions influencent fortement la performance.
• Utilisation de la mémoire: Nécessite de la mémoire supplémentaire pour le tableau de caisses.

Utilisation en QA:

• Stockage de données de test (clé - nom du paramètre, valeur - valeur attendue ou réelle).
• Vérification de l'unicité des éléments (par exemple, ID des utilisateurs).
• Implémentation de caches.