Hachage
Introduit| English | Sens |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | fonction de hachage |
| key/kiː/ | clé |
| address/əˈdres/ | adresse |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | deterministic : déterministe |
| collision/kəˈlɪʒn/ | collision |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | sonde linéaire |
| chaining/ˈtʃeɪnɪŋ/ | chaînage |
| load factor/ləʊd ˈfæktə/ | facteur de charge |
Trouver une ligne parmi cinquante millions sans regarder
- Un terminal de caisse de supermarché scanne un code-barres et le prix apparaît avant votre main quitte l'article. Le fichier produits contient cinquante millions de lignes.
- Rien ne les a cherchés. Le numéro de code-barres a passé par un court calcul qui a produit une position, et l'ordinateur a lu cette position : une lecture, aucune comparaison, le même temps que le fichier contienne cinquante lignes ou cinquante millions.
- Le calcul est une fonction de hachage 散列函数, et toute l'idée repose dessus : ne stockez pas les données là où elles tiennent, stockez-les là où leur propre clé dit qu'elles appartiennent.
- Cette leçon porte sur les algorithmes de hachage, ce qui se passe lorsque deux clés veulent la même case, et comment rechercher et insérer.
La fonction de hachage
- Une fonction de hachage, ou algorithme de hachage, prend la clé 键 d'un enregistrement et produit l'adresse 地址 à laquelle l'enregistrement est stocké.
- Une bonne fonction est rapide, déterministe 确定性 (la même clé donne toujours la même adresse), et répand les clés uniformément sur les cases disponibles.
- Pour $N$ cases, les trois que le programme attend : modulo,
address ← key MOD N; fractionnement, diviser la clé en morceaux, les additionner, puis MOD $N$ ; un hachage de chaîne, additionner les codes de caractères, puis MOD $N$.
Une fonction de hachage :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Une fonction de hachage mape une clé vers une adresse, permettant une recherche directe quasi instantanée.
Qu'est-ce qui rend une bonne fonction de hachage ? Sélectionnez toutes celles qui s'appliquent.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Rapide, déterministe et uniformément répartie. Aucune fonction de hachage réaliste n'évite totalement les collisions, c'est pourquoi chaque conception inclut une stratégie de résolution.
Exemple résolu : appliquer chaque algorithme
- Un fichier a 10 cases, numérotées de 0 à 9. Où va la clé 4517 ?
- Modulo : $4517 \bmod 10 = 7$, donc case 7.
- Fractionnement par paires : $45 + 17 = 62$, puis $62 \bmod 10 = 2$, donc case 2.
- Et la clé "CAB" par un hachage de chaîne ? $67 + 65 + 66 = 198$, puis $198 \bmod 10 = 8$, donc case 8.
- Montrez le calcul arithmétique. La note est pour le calcul, pas seulement pour le numéro de case.
En utilisant le hachage modulo address ← key MOD N avec key = 27 et N = 10, quelle adresse est produite ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
27 MOD 10 = 7 (le reste de la division de 27 par 10).
Un tableau a 10 cases. En utilisant le pliage par paires sur la clé 4517 (additionner 45 et 17, puis MOD 10), à quelle case va-t-il ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
45 + 17 = 62, et 62 MOD 10 = 2. La même clé sous un hachage modulo irait à la case 7 au lieu de cela.
Collisions
- Une collision 冲突 survient lorsque deux clés différentes hachent vers la même adresse. Avec n'importe quel hachage et n'importe quel fichier réaliste, les collisions sont inévitables, donc une stratégie pour elles fait partie de la conception, pas une après-pensée.
- Sondage linéaire 线性探测 place l'enregistrement dans la prochaine case libre, en revenant au début à la fin de la table. Simple, mais les enregistrements grappent : un bloc plein grandit et chaque clé atterrissant dedans prend plus de temps.
- Lien 链接法 fait de chaque case la tête d'une liste chaînée de tous les enregistrements qui y ont haché. Pas de grappement, mais mémoire supplémentaire pour les pointeurs et une courte marche le long de la liste.
- Re-hachage applique une deuxième fonction de hachage pour trouver une autre case, répandant mieux les clés au coût de plus de calculs.
Une collision se produit lorsque :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Deux clés mappant vers la même case constituent une collision ; elle doit être résolue par sondage, chaînage ou re-hachage.
Reliez chaque idée de gestion de collision à ce qu'elle fait.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Les collisions sont résolues par chaînage ou sondage ; maintenir un faible facteur de charge garde les recherches proches de O(1).
Recherche et insertion
- Pour insérer : hachez la clé. Si la case est libre, écrivez l'enregistrement là. Sinon, suivez la stratégie de résolution, la prochaine case libre pour le sondage linéaire, ou le début de la liste de cette case pour le lien.
- Pour rechercher : hachez la clé et lisez cette case. Si la clé stockée correspond, l'enregistrement est trouvé. Sinon, suivez la même stratégie, jusqu'à ce que les clés correspondent ou qu'une case vide prouve que l'enregistrement n'est pas dans le fichier.
- Les deux opérations utilisent la même stratégie. Une recherche qui s'arrête au premier désaccord manquerait tous les enregistrements qui ont été déplacés par une collision.
Exemple résolu : tracer une collision
- Une table de 10 cases utilise
key MOD 10avec sondage linéaire. Insérez 23, 33, 43 dans cet ordre, puis recherchez 43. - 23 hache vers 3 ; la case 3 est libre, donc elle y va. 33 hache vers 3 ; la case 3 est prise par 23, donc le sondage linéaire la place dans la case 4. 43 hache vers 3 ; les cases 3 et 4 sont prises, donc elle va dans la case 5.
- Rechercher 43 : hache vers 3, lisez la case 3, la clé est 23, pas de match, donc sondez ; la case 4 contient 33, pas de match ; la case 5 contient 43, trouvé, après trois lectures.
- Cette série croissante de trois est le grappement que cause le sondage linéaire.
Hachez chaque clé directement vers un bucket
Une fonction de hachage transforme une clé en un numéro de bucket, afin que vous sautiez directement vers l'enregistrement au lieu de rechercher. Quand deux clés atterrissent dans le même bucket, c'est une collision — elles forment une chaîne dans ce bucket.
Lors de la recherche dans une table de hachage, l'enregistrement n'est pas dans le fichier dès que la première case lue contient une clé différente.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
L'enregistrement peut avoir été déplacé par une collision. La recherche suit la même stratégie de résolution jusqu'à une correspondance ou une case vide.
Taux de charge
- Le taux de charge 装填因子 est le nombre d'enregistrements divisé par le nombre de cases. C'est le seul nombre qui prédit à quel point la table performera bien.
- En dessous d'environ 70 %, la recherche moyenne est proche d'une lecture. Au-dessus, les séquences de sondage s'allongent brusquement et les performances se dégradent vers une recherche linéaire.
- La solution est d'agrandir la table et de re-hacher chaque enregistrement dedans, ce qui explique pourquoi une table de hachage est dimensionnée pour les données qu'elle contiendra, pas pour celles qu'elle contient aujourd'hui.
Un tableau de 10 cases utilise key MOD 10 avec probing linéaire. Après insertion de 23, 33 et 43 dans cet ordre, quelle case contient 43 ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Tous trois hachent vers 3. 23 prend la case 3, 33 est sondé vers 4, et 43 vers 5. Trois clés consécutives sont exactement le regroupement causé par le probing linéaire.
Pièges qui font perdre des points
- Une collision est deux clés, une adresse. Ce n'est pas une erreur ni un enregistrement perdu ; c'est le cas normal qu'une stratégie gère.
- Une recherche doit suivre la même stratégie de résolution que l'insertion, et s'arrêter uniquement sur un match ou une case vide.
- Le sondage linéaire grappe ; le lien coûte de la mémoire. Donnez le compromis, pas seulement le mécanisme.
- Le taux de charge est records divisés par cases, et le seuil est d'environ 70 %, pas 100 %.
Pour maintenir la rapidité des recherches dans un hash, le facteur de charge (enregistrements ÷ emplacements) doit être maintenu :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Un facteur de charge plus faible signifie moins de collisions, donc les recherches restent proches de O(1).
Vous avez compris
- une fonction de hachage transforme une clé en une adresse : rapide, déterministe, répartition uniforme ; modulo, fractionnement et hachages de chaînes sont les trois à connaître
- une collision est deux clés hachant vers une adresse, résolue par sondage linéaire (prochaine case libre, grappes), lien (liste chaînée par case, plus de mémoire) ou re-hachage
- insertion et recherche suivent toutes deux la même stratégie ; une recherche se termine sur un match ou une case vide
- gardez le taux de charge, records divisés par cases, en dessous d'environ 70 % pour des recherches proches d'une seule lecture