29. Hachage et Résolution de Collisions

Nous avons appris que les Hash Tables offrent une complexité temporelle moyenne O(1). Cette efficacité dépend entièrement de la gestion des collisions — situations où la fonction de hachage mappe deux clés différentes au même index de tableau.

Stratégie de Résolution de Collisions 1 : Chaînage (Chaining)

• Concept : Au lieu de stocker un seul élément à un index, l'index stocke une référence à une linked list (ou à un tableau dynamique).
• Fonctionnement : Lorsqu'une collision se produit, la nouvelle paire clé/valeur est simplement ajoutée à la liste chaînée à cet index.
• Compromis : Le temps de recherche reste O(1) en moyenne, mais si trop de collisions se produisent, la liste chaînée s'allonge, dégradant la performance vers O(N) (recherche linéaire au sein de la liste).

Stratégie 2 : Adressage Ouvert (Open Addressing / Probing)

• Concept : Si une collision se produit, rechercher le prochain emplacement ouvert disponible dans le tableau principal.
  • Linear Probing : Vérifier l'index suivant (index + 1, index + 2, etc.).
  • Quadratic Probing : Utiliser un pas quadratique (index + 1, index + 4, index + 9, etc.).
• Compromis : Nécessite une gestion minutieuse des suppressions et peut entraîner un « clustering » (regroupement) s'il n'est pas bien implémenté.