Hashing · Hachage
| English | Français |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | fonction de hachage |
| key/kiː/ | clé |
| address/əˈdres/ | adresse |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | 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 |
Finding one row in fifty million without looking
- A supermarket till scans a barcode and the price appears before your hand leaves the item. The product file holds fifty million lines.
- Nothing searched them. The barcode number went through a short calculation that produced a position, and the computer read that position: one read, no comparisons, the same time whether the file holds fifty rows or fifty million.
- The calculation is a hash function 散列函数, and the whole idea rests on it: do not store data where it will fit, store it where its own key says it belongs.
- This lesson is hashing algorithms, what happens when two keys want the same slot, and how to search and insert.
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.
The hash function
- A hash function, or hashing algorithm, takes a record's key 键 and produces the address 地址 at which the record is stored.
- A good one is fast, deterministic 确定性 (the same key always gives the same address), and spreads keys evenly across the available slots.
- For $N$ slots, the three the syllabus expects: modulo,
address ← key MOD N; folding, split the key into pieces, add them, then MOD $N$; a string hash, add the character codes, then MOD $N$.
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$.
A hash function: · Une fonction de hachage :
A hash function maps a key to an address, enabling near-instant direct lookup. · Une fonction de hachage mape une clé vers une adresse, permettant une recherche directe quasi instantanée.
What makes a hash function a good one? Select all · tout that apply. · Qu'est-ce qui rend une bonne fonction de hachage ? Sélectionnez toutes celles qui s'appliquent.
Fast, deterministic and evenly spread. No realistic hash avoids collisions entirely, which is why every design includes a resolution strategy. · 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.
Worked example: apply each algorithm
- A file has 10 slots, numbered 0 to 9. Where does key 4517 go?
- Modulo: $4517 \bmod 10 = 7$, so slot 7.
- Folding in pairs: $45 + 17 = 62$, then $62 \bmod 10 = 2$, so slot 2.
- And the key "CAB" by a string hash? $67 + 65 + 66 = 198$, then $198 \bmod 10 = 8$, so slot 8.
- Show the arithmetic. The mark is for the calculation, not the slot number alone.
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.
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced? · En utilisant le hachage modulo address ← key MOD N avec key = 27 et N = 10, quelle adresse est produite ?
27 MOD 10 = 7 (the remainder when 27 is divided by 10). · 27 MOD 10 = 7 (le reste de la division de 27 par 10).
A table has 10 slots. Using folding in pairs on key 4517 (add 45 and 17, then MOD 10), which slot does it go to? · 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 ?
45 + 17 = 62, and 62 MOD 10 = 2. The same key under a modulo hash would go to slot 7 instead. · 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
- A collision 冲突 happens when two different keys hash to the same address. With any hash and any realistic file, collisions are certain, so a strategy for them is part of the design, not an afterthought.
- Linear probing 线性探测 puts the record in the next free slot, wrapping round to the start at the end of the table. Simple, but records cluster: a full patch grows and every key landing in it takes longer.
- Chaining 链接法 makes each slot the head of a linked list of all the records that hashed there. No clustering, but extra memory for the pointers and a short walk along the list.
- Rehashing applies a second hash function to find another slot, spreading keys better at the cost of more computation.
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.
A collision occurs when: · Une collision se produit lorsque :
Two keys mapping to the same slot is a collision; it must be resolved by probing, chaining or rehashing. · Deux clés mappant vers la même case constituent une collision ; elle doit être résolue par sondage, chaînage ou re-hachage.
Match each collision-handling idea to what it does. · Reliez chaque idée de gestion de collision à ce qu'elle fait.
Collisions are resolved by chaining or probing; keeping the load factor low keeps lookups near O(1). · Les collisions sont résolues par chaînage ou sondage ; maintenir un faible facteur de charge garde les recherches proches de O(1).
Searching and inserting
- To insert: hash the key. If the slot is free, write the record there. If not, follow the resolution strategy, the next free slot for linear probing, or the front of that slot's list for chaining.
- To search: hash the key and read that slot. If the stored key matches, the record is found. If it does not, follow the same strategy, until either the keys match or an empty slot proves the record is not in the file.
- Both operations use the same strategy. A search that stops at the first mismatch would miss every record that was ever displaced by a collision.
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.
Worked example: trace a collision
- A table of 10 slots uses
key MOD 10with linear probing. Insert 23, 33, 43 in that order, then search for 43. - 23 hashes to 3; slot 3 is free, so it goes there. 33 hashes to 3; slot 3 is taken by 23, so linear probing puts it in slot 4. 43 hashes to 3; slots 3 and 4 are taken, so it goes in slot 5.
- Searching for 43: hash to 3, read slot 3, key is 23, not a match, so probe on; slot 4 holds 33, not a match; slot 5 holds 43, found, after three reads.
- That growing run of three is the clustering that linear probing causes.
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.
Hash each key straight to a bucket · Hachez chaque clé directement vers un bucket
A hash function turns a key into a bucket number, so you jump straight to the record instead of searching. When two keys land in the same bucket that is a collision — they chain together in that 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.
When searching a hash table, the record is not in the file as soon as the first slot read holds a different key. · 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.
The record may have been displaced by a collision. The search follows the same resolution strategy until a match or an empty slot. · 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.
Load factor
- The load factor 装填因子 is the number of records divided by the number of slots. It is the single number that predicts how well the table performs.
- Below about 70% the average lookup is near one read. Above it, probe sequences lengthen sharply and performance degrades towards a linear search.
- The fix is to make the table larger and rehash every record into it, which is why a hash table is sized for the data it will hold, not the data it holds today.
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.
A 10-slot table uses key MOD 10 with linear probing. After inserting 23, 33 and 43 in that order, which slot holds 43? · 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 ?
All three hash to 3. 23 takes slot 3, 33 is probed to 4, and 43 to 5. Three keys in a row is exactly the clustering linear probing causes. · 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.
Marks that slip away
- A collision is two keys, one address. It is not an error and not a lost record; it is the normal case a strategy handles.
- A search must follow the same resolution strategy as the insert, and stop only on a match or an empty slot.
- Linear probing clusters; chaining costs memory. Give the trade-off, not just the mechanism.
- The load factor is records divided by slots, and the threshold is about 70%, not 100%.
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 %.
To keep hash lookups fast, the load factor (records ÷ slots) should be kept: · Pour maintenir la rapidité des recherches dans un hash, le facteur de charge (enregistrements ÷ emplacements) doit être maintenu :
A lower load factor means fewer collisions, so lookups stay close to O(1). · Un facteur de charge plus faible signifie moins de collisions, donc les recherches restent proches de O(1).
You've got it
- a hash function turns a key into an address: fast, deterministic, evenly spread; modulo, folding and string hashes are the three to know
- a collision is two keys hashing to one address, resolved by linear probing (next free slot, clusters), chaining (a linked list per slot, more memory) or rehashing
- insert and search both follow the same strategy; a search ends on a match or an empty slot
- keep the load factor, records divided by slots, below about 70% for near one-read lookups
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