Associer des clés à des valeurs pour accéder rapidement aux informations

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• expliquer le principe qui associe une clé à un indice de table ;
• distinguer une clé, une valeur, une fonction de hachage et une case de stockage ;
• évaluer les qualités d’une fonction de hachage ;
• identifier une collision et choisir une stratégie de résolution appropriée ;
• implémenter le chaînage séparé et les principales variantes de l’adressage ouvert ;
• calculer le facteur de charge et prévoir un redimensionnement ;
• analyser les performances moyennes et défavorables des opérations ;
• concevoir une application utilisant un ensemble ou un dictionnaire fondé sur le hachage.

Prérequis

• Maîtrise des tableaux, des enregistrements et des listes chaînées.
• Connaissance des fonctions, procédures et types abstraits de données.
• Capacité à analyser une boucle et à utiliser les notations O, Ω et Θ.
• Compréhension des notions de clé de recherche, d’égalité et de comparaison.

Organisation proposée

Introduction

De nombreux programmes doivent retrouver une information à partir d’un identifiant : numéro d’inscription, adresse électronique, mot d’un dictionnaire, référence d’un produit ou résultat déjà calculé. Une recherche séquentielle coûte O(n), tandis qu’une structure ordonnée impose souvent un tri ou un arbre. La table de hachage propose une autre stratégie : transformer directement la clé en un indice de stockage.

Lorsque les clés sont bien réparties et que le taux d’occupation reste maîtrisé, la recherche, l’insertion et la suppression s’effectuent en temps moyen O(1). Cette performance n’est toutefois pas automatique. Elle dépend fortement de la fonction de hachage, de la stratégie de gestion des collisions et du redimensionnement de la table.

5.1 Principe du hachage

5.1.1 Clé et valeur

Une table de hachage stocke généralement des associations de la forme clé → valeur. La clé identifie l’information, tandis que la valeur contient les données qui lui sont associées. Dans un ensemble, seule la clé est nécessaire ; dans un dictionnaire, chaque clé correspond à une valeur.

5.1.2 Fonction de hachage

Une fonction de hachage produit un entier à partir d’une clé. Cet entier peut être très grand ou négatif selon le langage. Une opération de réduction le transforme ensuite en un indice valide compris entre 0 et m − 1, où m représente la taille de la table.

Schéma général

hashBrut <- Hacher(cle)
indice <- Normaliser(hashBrut) MOD m
Accéder à table[indice]

La fonction Hacher dépend du type de clé. Pour un entier, une transformation simple peut suffire. Pour une chaîne, il faut combiner les codes des caractères. Pour un enregistrement, plusieurs champs stables peuvent être intégrés.

5.1.3 Indice calculé et table de hachage

La table est composée de m positions, souvent appelées cases, alvéoles ou buckets. L’indice calculé désigne le bucket initial de la clé. Si plusieurs clés conduisent au même indice, une collision apparaît.

Exemple : pour une table de taille m = 7 et la fonction h(k) = k MOD 7 :

5.1.4 Représentation abstraite

Une table de hachage fournit souvent l’interface d’un dictionnaire. Son utilisateur ne doit pas dépendre de la représentation interne des buckets.

TAD Dictionnaire<Cle, Valeur>

Inserer(cle, valeur)
Rechercher(cle) : ValeurOuABSENT
Contient(cle) : Booleen
Supprimer(cle) : Booleen
Taille() : Entier
EstVide() : Booleen
FinTAD

Les coûts O(1) sont des coûts moyens sous l’hypothèse d’une bonne répartition. Dans le pire cas, toutes les clés peuvent se concentrer dans la même zone et conduire à un coût O(n).

5.1.5 Hachage et adressage direct

Dans l’adressage direct, chaque clé possible correspond à une case distincte. Cette approche est excellente si l’univers des clés est petit et dense, par exemple les jours du mois ou les codes compris entre 0 et 999. Elle devient gaspilleuse lorsque les clés possibles sont nombreuses mais que peu d’entre elles sont réellement présentes.

5.2 Propriétés d’une fonction de hachage

La fonction de hachage joue un rôle central. Une table correctement dimensionnée peut être inefficace si la fonction concentre les clés dans quelques buckets. À l’inverse, une fonction adaptée répartit les entrées et limite la longueur des recherches locales.

5.2.1 Déterminisme

Pour une même clé, la fonction doit toujours produire le même résultat tant que la table utilise les mêmes règles. Sans déterminisme, une clé insérée dans une case pourrait être recherchée dans une autre.

5.2.2 Rapidité

La fonction est évaluée à chaque recherche, insertion ou suppression. Elle doit donc rester beaucoup moins coûteuse que le traitement évité. Pour une chaîne de longueur L, un coût O(L) est habituel, car les caractères utilisés doivent être lus au moins une fois.

• Éviter des conversions ou allocations inutiles.
• Ne pas trier les composants d’une clé pour calculer son hash.
• Mettre en cache le hash d’un objet immuable si le langage et le contexte le permettent.
• Limiter le nombre de champs hachés aux champs qui définissent réellement l’identité.

5.2.3 Répartition uniforme

Une bonne fonction distribue des clés réalistes sur l’ensemble des indices. Elle doit exploiter les différences entre les clés, y compris lorsque celles-ci suivent un motif régulier : numéros multiples de 10, identifiants partageant un préfixe ou mots proches.

5.2.4 Limitation des collisions

Aucune fonction ne peut supprimer toutes les collisions lorsque le nombre de clés possibles dépasse le nombre de cases. Ce résultat découle du principe des tiroirs : au moins deux clés doivent partager un bucket. L’objectif est donc de rendre les collisions rares et équilibrées.

5.2.5 Exemple de hachage d’une chaîne

Une méthode pédagogique consiste à parcourir les caractères et à accumuler un résultat polynomial. La constante multiplicative, souvent un petit nombre premier, propage l’influence des caractères précédents.

Fonction de hachage polynomial

Fonction HacherChaine(s, m) : Entier
   h <- 0
   Pour chaque caractere c de s Faire
       h <- (h * 31 + Code(c)) MOD m
   FinPour
   Retourner h
FinFonction

Le modulo effectué à chaque étape empêche la croissance excessive de h. Dans une bibliothèque réelle, on utilise généralement la fonction de hachage fournie par le langage, car elle est testée, optimisée et cohérente avec les règles d’égalité du type.

5.2.6 Évaluer expérimentalement une fonction

Un test simple consiste à insérer un échantillon représentatif, puis à mesurer la taille de chaque bucket. Une distribution parfaite n’est pas nécessaire, mais les écarts extrêmes doivent alerter.

5.2.7 Hachage de table et hachage cryptographique

5.3 Gestion des collisions

Lorsque deux clés différentes obtiennent le même indice initial, la table doit conserver les deux associations et vérifier l’égalité des clés lors de la recherche. Deux grandes familles de solutions sont utilisées : le chaînage séparé et l’adressage ouvert.

5.3.1 Chaînage séparé

Chaque bucket contient une collection, souvent une liste chaînée, de toutes les entrées dont l’indice initial est identique. La table stocke alors m références de tête de liste.

Exemple pour h(k) = k MOD 7 après insertion des clés 19, 26, 12, 20 et 8 :

Recherche par chaînage

Fonction Rechercher(T, cle) : ValeurOuABSENT
   i <- Hacher(cle) MOD T.capacite
   courant <- T.buckets[i]
   TantQue courant != NULL Faire
       Si courant.cle = cle Alors
            Retourner courant.valeur
       FinSi
       courant <- courant.suivant
   FinTantQue
   Retourner ABSENT
FinFonction

Insertion ou mise à jour

Procedure Inserer(T, cle, valeur)
   i <- Hacher(cle) MOD T.capacite
   courant <- T.buckets[i]
   TantQue courant != NULL Faire
       Si courant.cle = cle Alors
            courant.valeur <- valeur
            Retourner
       FinSi
       courant <- courant.suivant
   FinTantQue
   nouveau <- NouveauNoeud(cle, valeur)
   nouveau.suivant <- T.buckets[i]
   T.buckets[i] <- nouveau
   T.taille <- T.taille + 1
FinProcedure

Suppression

Fonction Supprimer(T, cle) : Booleen
   i <- Hacher(cle) MOD T.capacite
   precedent <- NULL
   courant <- T.buckets[i]
   TantQue courant != NULL ET courant.cle != cle Faire
       precedent <- courant
       courant <- courant.suivant
   FinTantQue
   Si courant = NULL Alors Retourner FAUX
   Si precedent = NULL Alors
       T.buckets[i] <- courant.suivant
   Sinon
       precedent.suivant <- courant.suivant
   FinSi
   T.taille <- T.taille - 1
   Retourner VRAI
FinFonction

5.3.2 Adressage ouvert

Dans l’adressage ouvert, toutes les entrées sont stockées directement dans le tableau. Lorsqu’une case est occupée, une suite d’indices, appelée séquence de sondage, est examinée jusqu’à trouver la clé ou une case disponible.

Chaque case doit distinguer au moins trois états : VIDE, OCCUPÉE et SUPPRIMÉE. L’état SUPPRIMÉE, souvent appelé marqueur ou tombe, est indispensable pour ne pas interrompre une recherche qui doit poursuivre son sondage.

Recherche générique par adressage ouvert

Fonction Rechercher(T, cle) : ValeurOuABSENT
   Pour j allant de 0 a T.capacite - 1 Faire
       i <- IndiceSondage(cle, j, T.capacite)
       Si T[i].etat = VIDE Alors Retourner ABSENT
       Si T[i].etat = OCCUPEE ET T[i].cle = cle Alors
            Retourner T[i].valeur
       FinSi
   FinPour
   Retourner ABSENT
FinFonction

Insertion générique

Procedure Inserer(T, cle, valeur)
   premiereTombe <- AUCUNE
   Pour j allant de 0 a T.capacite - 1 Faire
       i <- IndiceSondage(cle, j, T.capacite)
       Si T[i].etat = OCCUPEE ET T[i].cle = cle Alors
            T[i].valeur <- valeur
            Retourner
       FinSi
       Si T[i].etat = SUPPRIMEE ET premiereTombe = AUCUNE Alors
            premiereTombe <- i
       FinSi
       Si T[i].etat = VIDE Alors
            cible <- i si premiereTombe = AUCUNE sinon premiereTombe
            EcrireEntree(T[cible], cle, valeur)
            T.taille <- T.taille + 1
            Retourner
       FinSi
   FinPour
   Signaler TABLE_PLEINE
FinProcedure

5.3.3 Sondage linéaire

Le sondage linéaire examine les cases consécutives :

indice(j) = (h(cle) + j) MOD m, pour j = 0, 1, 2, …

Avec m = 7 et les clés 19, 26, 12, 20, 8, la suite d’insertions devient :

5.3.4 Sondage quadratique

Le sondage quadratique augmente progressivement l’écart entre les cases examinées :

indice(j) = (h(cle) + c1·j + c2·j²) MOD m

Cette méthode réduit le regroupement primaire, mais deux clés ayant le même indice initial suivent encore la même séquence. De plus, selon m, c1 et c2, toutes les cases ne sont pas nécessairement visitées. Le dimensionnement et les constantes doivent donc être choisis avec soin.

5.3.5 Double hachage

Le double hachage utilise une seconde fonction pour calculer le pas de sondage :

indice(j) = (h1(cle) + j · h2(cle)) MOD m

Pour parcourir toutes les cases, le pas h2(cle) doit être premier avec m. Une pratique fréquente consiste à choisir m premier et à définir h2(cle) entre 1 et m − 1.

Exemple de fonctions

h1(cle) <- cle MOD m
h2(cle) <- 1 + (cle MOD (m - 1))
indice(j) <- (h1(cle) + j * h2(cle)) MOD m

Le double hachage réduit fortement les regroupements, car deux clés partageant h1 ont de bonnes chances d’utiliser des pas différents.

5.3.6 Suppression et marqueurs

Dans une table à adressage ouvert, remettre immédiatement une case supprimée à l’état VIDE peut rendre certaines clés introuvables. Une recherche s’arrête sur VIDE ; elle doit au contraire continuer au-delà d’une case SUPPRIMÉE.

Un nombre excessif de marqueurs dégrade les recherches. Un redimensionnement ou une reconstruction périodique permet de les éliminer.

5.3.7 Comparaison des stratégies

5.4 Facteur de charge

5.4.1 Définition

Le facteur de charge mesure le rapport entre le nombre n d’entrées et la capacité m de la table :

α = n / m

Avec chaînage, α représente la longueur moyenne théorique des chaînes. Il peut dépasser 1. Avec adressage ouvert, α est la proportion de cases occupées et doit rester strictement inférieure à 1.

5.4.2 Influence sur les performances

Lorsque α augmente, les collisions deviennent plus fréquentes. Avec chaînage uniforme, une recherche coûte approximativement O(1 + α). Avec adressage ouvert, le nombre de sondages augmente très rapidement lorsque la table approche de la saturation.

5.4.3 Redimensionnement

Lorsque le seuil est dépassé, la table est remplacée par une table plus grande. Il ne suffit pas de copier les cases aux mêmes indices : comme l’indice dépend de m, toutes les entrées doivent être rehachées.

Procédure de redimensionnement

Procedure Redimensionner(T, nouvelleCapacite)
   ancienneTable <- T.buckets
   T.buckets <- TableauVide(nouvelleCapacite)
   T.capacite <- nouvelleCapacite
   T.taille <- 0
   Pour chaque entree occupee de ancienneTable Faire
       InsererSansRedimensionner(T, entree.cle, entree.valeur)
   FinPour
FinProcedure

1. Choisir une nouvelle capacité, souvent environ deux fois plus grande.

2. Créer une table vide avec la nouvelle capacité.

3. Parcourir toutes les anciennes entrées.

4. Recalculer leur indice avec la nouvelle capacité.

5. Insérer les entrées sans déclencher un nouveau redimensionnement.

5.4.4 Choix de la capacité

• Avec une fonction modulo simple, une capacité première peut limiter certains motifs.
• Avec une puissance de deux, le calcul d’indice est rapide mais exige un bon mélange des bits.
• La capacité doit laisser une marge par rapport au nombre attendu d’entrées.
• Le rétrécissement peut être envisagé lorsque la table devient durablement très vide.
• Deux seuils distincts d’agrandissement et de réduction évitent des oscillations répétées.

5.4.5 Complexités récapitulatives

Applications guidées

Application 1 — Annuaire

On souhaite associer une adresse électronique à une fiche contenant le nom et le numéro de téléphone. La clé est l’adresse normalisée, par exemple convertie en minuscules et débarrassée des espaces inutiles.

Opérations principales

Inserer(annuaire, email, fiche)
fiche <- Rechercher(annuaire, email)
Supprimer(annuaire, email)
Contient(annuaire, email)

Une mise à jour réutilise la même clé et remplace la fiche. Il faut définir clairement si les adresses sont sensibles à la casse et appliquer la même normalisation lors de toutes les opérations.

Application 2 — Dictionnaire de mots

Un dictionnaire peut associer chaque mot à une définition, une fréquence, une catégorie grammaticale ou une liste de traductions. Les recherches exactes utilisent efficacement une table de hachage. En revanche, les recherches par préfixe sont mieux adaptées à un trie, qui sera étudié dans un niveau ultérieur.

Recherche d’un mot

mot <- Normaliser(LireChaine())
Si dictionnaire.Contient(mot) Alors
   Afficher(dictionnaire.Rechercher(mot))
Sinon
   Afficher("Mot absent")
FinSi

Application 3 — Comptage des occurrences

Chaque élément rencontré devient une clé et sa valeur représente le nombre d’occurrences. Cette technique remplace souvent une double boucle O(n²) par un parcours moyen O(n).

Comptage des mots

D <- DictionnaireVide()
Pour chaque mot du texte Faire
   mot <- Normaliser(mot)
   Si D.Contient(mot) Alors
       D[mot] <- D[mot] + 1
   Sinon
       D.Inserer(mot, 1)
   FinSi
FinPour

Application 4 — Détection de doublons

Un ensemble haché conserve les valeurs déjà rencontrées. Dès qu’un élément appartient à l’ensemble, un doublon est détecté.

Détecter un doublon

Fonction ContientDoublon(T) : Booleen
   vus <- EnsembleVide()
   Pour chaque x de T Faire
       Si vus.Contient(x) Alors Retourner VRAI
       vus.Ajouter(x)
   FinPour
   Retourner FAUX
FinFonction

Application 5 — Mise en cache de résultats

Une cache mémorise le résultat d’un calcul associé à ses paramètres. Avant de recalculer, le programme consulte le dictionnaire. Cette technique, appelée mémoïsation dans un contexte algorithmique, évite les sous-problèmes répétés.

Fibonacci mémoïsé

Fonction Fibonacci(n, cache) : Entier
   Si n <= 1 Alors Retourner n
   Si cache.Contient(n) Alors Retourner cache[n]
   resultat <- Fibonacci(n-1, cache) + Fibonacci(n-2, cache)
   cache.Inserer(n, resultat)
   Retourner resultat
FinFonction

La table de hachage assure l’accès rapide aux résultats. Une cache réelle doit aussi définir une capacité, une politique d’expiration ou d’éviction et éventuellement une synchronisation entre plusieurs tâches.

Bonnes pratiques et erreurs fréquentes

Travaux dirigés

TD 1 — Vocabulaire et calcul d’indices

On utilise une table de taille 11 avec h(k) = k MOD 11. Pour les clés 24, 35, 18, 29, 46 et 57 :

• calculer l’indice initial de chaque clé ;
• identifier les collisions ;
• représenter la table avec chaînage séparé, en insérant en tête.

TD 2 — Qualité d’une fonction

On souhaite stocker les matricules 20260010, 20260020, 20260030, … dans une table de taille 10. Étudier h1(k) = k MOD 10, puis proposer une amélioration et justifier le choix.

TD 3 — Chaînage séparé

Insérer les clés 14, 21, 28, 6, 13, 20 dans une table de taille 7 avec h(k) = k MOD 7. Effectuer ensuite la recherche de 13, la recherche de 15 et la suppression de 21. Donner les listes après chaque étape importante.

TD 4 — Sondage linéaire

Dans une table de taille 11, insérer 22, 1, 13, 11, 24, 33 avec h(k) = k MOD 11 et sondage linéaire. Indiquer les cases testées et le nombre total de sondages.

TD 5 — Suppression en adressage ouvert

À partir de la table du TD 4, supprimer 22 puis rechercher 33. Expliquer pourquoi l’état SUPPRIMÉE est nécessaire et montrer l’erreur obtenue si la case de 22 devient VIDE.

TD 6 — Sondage quadratique et double hachage

Pour m = 13 et les clés 18, 31, 44 et 57, comparer :

• le sondage quadratique indice(j) = (h(k) + j²) MOD 13 ;
• le double hachage avec h1(k) = k MOD 13 et h2(k) = 1 + (k MOD 12).

TD 7 — Facteur de charge

Une table à adressage ouvert possède une capacité de 64 cases et contient 43 entrées. Calculer α. Un seuil de 0,70 est utilisé : déterminer si la prochaine insertion doit provoquer un redimensionnement. Proposer une nouvelle capacité et expliquer le rehachage.

TD 8 — Fréquences de mots

Concevoir un algorithme qui lit une liste de mots, ignore la casse, compte les occurrences et affiche les mots apparaissant au moins trois fois. Donner la complexité moyenne.

TD 9 — Annuaire

Définir le TAD d’un annuaire indexé par adresse électronique. Préciser les règles de normalisation, les préconditions, les erreurs possibles et les tests minimaux.

TD 10 — Choix d’une stratégie

Pour chacun des contextes suivants, proposer une stratégie et justifier :

• grand nombre d’insertions et suppressions, taille difficile à prévoir ;
• table compacte, principalement des recherches, capacité connue ;
• données sensibles à la localité mémoire ;
• fonction de hachage imparfaite produisant des groupes de clés.

Corrigés indicatifs des travaux dirigés

Correction du TD 1

Les collisions concernent le bucket 2 (24, 35, 46, 57) et le bucket 7 (18, 29). Avec insertion en tête : bucket 2 = 57 -> 46 -> 35 -> 24 et bucket 7 = 29 -> 18.

Correction du TD 2

Tous les matricules se terminent par 0, donc h1(k) = 0 pour toutes les clés : la fonction est très mauvaise sur ces données. Une amélioration consiste à diviser par 10 avant le modulo ou, de préférence, à utiliser un mélange de tous les chiffres puis un modulo avec une capacité non liée au motif, par exemple un nombre premier.

Exemple pédagogique

h2(k) <- ((k DIV 10) * 2654435761) MOD m

L’objectif n’est pas la constante particulière, mais la rupture du motif régulier des derniers chiffres.

Correction du TD 3

Les clés 14, 21 et 28 vont dans le bucket 0 ; les clés 6, 13 et 20 vont dans le bucket 6. Avec insertion en tête :

La recherche de 13 parcourt 20 puis trouve 13. La recherche de 15 examine le bucket 1, vide. Après suppression de 21, le bucket 0 devient 28 -> 14.

Correction du TD 4

Le nombre total de sondages est 1 + 1 + 1 + 4 + 3 + 6 = 16. L’exemple met en évidence un regroupement primaire dans les cases 0 à 5.

Correction du TD 5

La case 0 est marquée SUPPRIMÉE. Pour rechercher 33, on ne s’arrête donc pas en 0 : les cases 1, 2, 3, 4 puis 5 sont examinées et 33 est trouvé. Si la case 0 était marquée VIDE, la recherche conclurait immédiatement à l’absence de 33, ce qui serait faux.

Correction du TD 6

Toutes les clés ont h1(k) = 5. Avec sondage quadratique, les positions successives sont 5, 6, 9 et 1 pour les quatre clés. Avec double hachage, les pas diffèrent :

Le double hachage répartit les clés sur des séquences différentes, ce qui limite le regroupement secondaire.

Correction du TD 7

α = 43 / 64 = 0,671875. Après une insertion, α = 44 / 64 = 0,6875, encore inférieur à 0,70. La prochaine insertion ne déclenche donc pas nécessairement le redimensionnement. La 45e entrée donnerait 45 / 64 ≈ 0,703, ce qui franchit le seuil. Une capacité de 128 ou une capacité première voisine peut être choisie. Toutes les entrées doivent être rehachées avec la nouvelle capacité.

Correction du TD 8

Comptage et filtrage

D <- DictionnaireVide()
Pour chaque mot lu Faire
   mot <- Minuscules(mot)
   D[mot] <- D.ObtenirOuDefaut(mot, 0) + 1
FinPour
Pour chaque (mot, compteur) de D Faire
   Si compteur >= 3 Alors Afficher(mot, compteur)
FinPour

Le premier parcours coûte O(n) en moyenne. Le parcours du dictionnaire coûte O(u + m), où u est le nombre de mots distincts et m la capacité interne ; on retient généralement O(n + u) dans une analyse abstraite.

Correction du TD 9

La clé est l’adresse normalisée en minuscules, après suppression des espaces externes. L’interface minimale contient InsererOuModifier, Rechercher, Supprimer, Contient et Taille. Une adresse vide est refusée ; une recherche absente retourne ABSENT ou déclenche une erreur documentée. Les tests portent sur une insertion, une mise à jour, une collision, une suppression, une adresse absente et deux écritures différentes d’une même adresse normalisée.

Correction du TD 10

Travail pratique — Implémenter une table de hachage

Objectif

Réaliser un dictionnaire générique fondé sur le chaînage séparé, puis comparer ses performances avec une variante à adressage ouvert. L’implémentation peut être traduite en Python, C, Java ou dans un autre langage étudié.

Spécification minimale

• Créer une table avec une capacité initiale configurable.
• Insérer une association clé-valeur et mettre à jour une clé existante.
• Rechercher et supprimer une clé.
• Retourner la taille et le facteur de charge.
• Agrandir automatiquement la table à partir d’un seuil.
• Conserver des statistiques : collisions, longueur maximale des chaînes ou nombre de sondages.
• Fournir un programme de démonstration utilisant un annuaire ou un compteur de mots.

Étapes proposées

1. Définir les types Entrée et TableHachage.

2. Implémenter une fonction d’indice à partir du hash de la clé.

3. Écrire Inserer, Rechercher, Contient et Supprimer.

4. Ajouter le calcul du facteur de charge.

5. Implémenter Redimensionner et vérifier que toutes les entrées restent accessibles.

6. Instrumenter le code pour compter les collisions.

7. Tester avec des clés aléatoires et avec des clés provoquant volontairement des collisions.

8. Rédiger une analyse de complexité et une courte conclusion expérimentale.

Jeux de tests obligatoires

Extension — Variante à adressage ouvert

• Utiliser les états VIDE, OCCUPÉE et SUPPRIMÉE.
• Implémenter le sondage linéaire ou le double hachage.
• Mesurer le nombre moyen de sondages pour plusieurs facteurs de charge.
• Comparer la consommation mémoire, le temps et la simplicité avec le chaînage.

Grille d’évaluation indicative

Synthèse du chapitre

• Une table de hachage transforme une clé en un indice de stockage.
• Une fonction de hachage doit être déterministe, rapide et bien répartir les clés.
• Les collisions sont normales et doivent être gérées sans confondre les clés.
• Le chaînage séparé stocke une collection par bucket ; l’adressage ouvert sonde d’autres cases.
• Le sondage linéaire est simple mais crée des regroupements ; le double hachage les réduit.
• La suppression en adressage ouvert nécessite un état SUPPRIMÉE.
• Le facteur de charge α = n/m influence directement les performances.
• Le redimensionnement rehache toutes les entrées et permet de conserver un coût moyen O(1).
• Les tables de hachage sont adaptées aux annuaires, dictionnaires, ensembles, compteurs et caches.
• Le pire cas reste O(n), notamment si les clés sont mal réparties.

Glossaire

Auto-évaluation