Quel est le principe de fonctionnement d'une table de hachage?

Une table de hachage (ou tableau associatif) stocke des paires "clé-valeur". Le principe de fonctionnement repose sur l'utilisation d'une fonction de hachage, qui transforme la clé en un indice numérique (hachage), indiquant l'emplacement du valeur dans le tableau (panier).

Étapes:

1. Calcul du hachage: Pour une clé donnée, le hachage est calculé.

   <?php
   $key = "example";
   $hash = crc32($key); // Exemple d'une fonction de hachage simple
   

2. Détermination de l'indice: Le hachage est transformé en un indice du tableau, généralement en utilisant l'opération modulo de la taille du tableau.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Accès au panier: On accède au panier correspondant dans le tableau en utilisant l'indice calculé.
4. Résolution des collisions: Comme différents clés peuvent avoir le même hachage (collision), le panier peut contenir plusieurs paires "clé-valeur". Pour résoudre les collisions, différentes méthodes sont utilisées:
   • Méthode de chaînage (Separate Chaining): Chaque panier stocke une liste (par exemple, une liste chaînée) de paires "clé-valeur" dont les hachages correspondent.
   • Méthode d'adressage ouvert (Open Addressing): En cas de collision, une recherche répétée d'une cellule libre dans le tableau est effectuée selon une règle déterminée (sondage linéaire, quadratique, double hachage).

Opérations:

• Insertion: Le hachage de la clé est calculé, l'indice est déterminé, et la paire "clé-valeur" est placée dans le panier correspondant. En cas de collision, elle est ajoutée à la liste (chaînage) ou un emplacement libre est recherché (adressage ouvert).
• Recherche: Le hachage de la clé est calculé, l'indice est déterminé. Dans le panier correspondant, la valeur est recherchée par la clé. En méthode de chaînage, les éléments de la liste sont parcourus; en adressage ouvert, une recherche séquentielle est effectuée.
• Suppression: Le hachage de la clé est calculé, l'indice est déterminé. Dans le panier correspondant, la paire est trouvée et supprimée par la clé.

Avantages:

• Accès rapide aux éléments (en moyenne O(1)).
• Utilisation efficace de la mémoire.

Inconvénients:

• La performance peut se dégrader avec un grand nombre de collisions.
• La taille du tableau peut nécessiter un ajustement (rehashing) pour maintenir l'efficacité.