Tables de hachage
Tables de hachage : recherche rapide
- Une table de hachage stocke des éléments pour les trouver très rapidement — généralement en une seule étape.
- C'est une liste de cases. Une fonction de hachage transforme une clé en un numéro de case.
- Au lieu de chercher chaque élément, vous sautez directement à la case où appartient la clé.
Une fonction de hachage
- Une fonction de hachage prend une clé et retourne un index de case de
0àsize - 1. - La même clé donne toujours la même case, afin de pouvoir la retrouver plus tard.
- Une simple variante : additionner les codes des caractères, puis prendre
% sizepour rester dans la plage.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Collisions
- Deux clés différentes peuvent hacher vers la même case. C'est une collision.
- Une table ayant un nombre limité de cases, les collisions sont inévitables lorsqu'elle se remplit.
- Nous avons besoin d'une règle pour gérer le cas où la case souhaitée est déjà occupée.
Sondaire linéaire
- Sondaire linéaire : si une case est pleine, essayez la prochaine case, puis la suivante, en effectuant une boucle.
- Continuez à avancer
(slot + 1) % sizejusqu'à trouver une case libre. - Ci-dessous,
AetFveulent tous deux la case 0, doncFest repoussé à la case 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Rechercher une clé
- Pour trouver une clé : hachez-la, puis sondez vers l'avant, en comparant chaque case à la clé.
- Arrêtez et retournez l'index lorsque vous la trouvez.
- Si vous reach an empty slot (or check every slot), the key is not there — return
-1.
Pourquoi les tables de hachage sont rapides
- Avec peu de collisions, l'insertion et la recherche prennent environ une étape — nous appelons cela
O(1). - À mesure que la table se remplit, la sonde devient plus longue, il est donc sage de laisser quelques cases libres.
- Dans le cas pire (tout entre en collision), cela ralentit à un balayage linéaire,
O(n).
Erreurs courantes
- Une fonction de hachage mape une clé vers un index dans la table.
- Deux clés peuvent entrer en collision au même indice. Gérer cela, comme le fait cette leçon, par sondage linéaire ; le chaînage est l'autre méthode courante.
À vous maintenant
- Construire les trois parties : la fonction de hachage, l'insertion avec sonde, et la recherche.
- Chaque tâche vérifie votre fonction sur les cas de collision et de dépassement de limite.
- Appuyez sur Vérifier la réponse pour tester.
Hashing to a bucket
A hash function sends each key to a seau; clashes chaîne.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 à size - 1. Example: hash_key("AB", 10) est (65 + 66) % 10 = 1. The empty string gives 0.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an vides slot (key not there). Make sure it ends even if the table is plein — never loop forever.
Cliquez sur Exécuter pour voir le résultat ici.