Hash tables · Tables de hachage
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
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é.
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
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
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
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.
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
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]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
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.
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
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).
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
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 index — gérer cela, par exemple par chaînage.
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
À 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 · Hachage vers un bucket
A hash function sends each key to a bucket · seau; clashes chain. · Une fonction de hachage envoie chaque clé à un bucket · seau ; les collisions chaînent.
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 to · à size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · Écrivez hash_key(key, size). Additionnez les codes caractères de key (utilisez ord(ch)) et retournez le total % size, pour que le résultat soit une case entre 0 et size - 1. Exemple : hash_key("AB", 10) est (65 + 66) % 10 = 1. La chaîne vide donne 0.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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. · hash_key est fourni. Écrivez insert(table, key) en utilisant l'adressage ouvert (linear probing) : allez à l'emplacement de hachage de la clé ; tant que cet emplacement est plein (pas None), passez à (slot + 1) % len(table) ; placez la clé dans le premier emplacement libre et retournez son index.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 empty · vides slot (key not there). Make sure it ends even if the table is full · plein — never loop forever. · hash_key est fourni. Écrivez find(table, key) qui retourne l'index de key, ou -1 s'il est absent. Commencez à l'emplacement de hachage et sondagez vers l'avant, en comparant chaque emplacement. Arrêtez-vous à un emplacement vide (clé absente). Assurez-vous qu'il se termine même si la table est pleine — ne bouclez jamais indéfiniment.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.