Table de Hachage
Dernière mise à jour
Une table de hachage stocke les éléments dans un tableau de seaux. Pour placer ou trouver une clé, elle passe la clé dans une fonction de hachage et prend le résultat modulo le nombre de seaux - cela donne l'indice du seau en O(1). Appuyez sur lecture ci-dessus pour voir chaque clé être hachée vers un seau et stockée, puis une recherche sauter directement vers le bon seau.
Lorsque deux clés tombent dans le même seau - une collision - cette visualisation utilise le chaînage séparé : chaque seau contient une petite liste, et les clés en collision y sont ajoutées. Tant que la table n'est pas trop pleine (un faible facteur de charge) et que le hachage répartit bien les clés, les chaînes restent courtes et l'insertion, la recherche et la suppression sont en O(1) en moyenne.
Complexité temporelle
| Opération | Moyenne | Pire cas |
|---|---|---|
| Insertion | O(1) | O(n) (toutes les clés entrent en collision) |
| Recherche | O(1) | O(n) |
| Suppression | O(1) | O(n) |
| Espace | O(n) | O(n) |
Concepts clés
| Terme | Signification |
|---|---|
| Fonction de hachage | Associe une clé à un indice de seau |
| Collision | Deux clés tombent dans le même seau |
| Chaînage séparé | Chaque seau contient une liste des entrées en collision |
| Adressage ouvert | Alternative : sonder le prochain emplacement libre |
| Facteur de charge | entrées / seaux - déclenche le redimensionnement |
Exemple résolu
Insertion des clés 20, 34, 9, 13 dans une table de 7 seaux, avec hash(k) = k % 7 :
| Étape | Structure | Action |
|---|---|---|
Insérer 20 | seau 6 : [20] | 20 % 7 = 6, seau 6 vide, stocker 20 |
Insérer 34 | seau 6 : [20, 34] | 34 % 7 = 6, collision avec 20, ajouter 34 à la chaîne |
Insérer 9 | seau 2 : [9] | 9 % 7 = 2, seau 2 vide, stocker 9 |
Insérer 13 | seau 6 : [20, 34, 13] | 13 % 7 = 6, collision, ajouter 13 à la chaîne du seau 6 |
Rechercher 34 | seau 6 : [20, 34, 13] | 34 % 7 = 6, parcourir la chaîne : 20 non, 34 correspond - trouvé |
Quand utiliser une table de hachage
| À utiliser quand | À éviter quand |
|---|---|
Vous avez besoin d'insertion, recherche et suppression par clé en O(1) moyen | Vous devez garder les clés triées - utilisez un ABR équilibré |
| Les clés n'ont pas d'ordre utile et vous ne testez que l'appartenance par correspondance exacte | Vous avez besoin de requêtes par intervalle ou de recherches de la clé la plus proche |
| Vous pouvez vous permettre un peu de mémoire supplémentaire pour les seaux et un faible facteur de charge | La mémoire est extrêmement limitée et chaque octet compte |
| Une bonne fonction de hachage existe pour votre type de clé | La latence du pire cas doit être bornée - les collisions la rendent O(n) |
Code de Hash Table
Une implémentation propre et exécutable de Hash Table en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Hash Table en Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Code de Hash Table en JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Code de Hash Table en Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Code de Hash Table en C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Code de Hash Table en C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}FAQ sur la table de hachage
Qu'est-ce qu'une collision de hachage et comment est-elle résolue ?
Une collision se produit lorsque deux clés différentes tombent dans le même seau. Les deux solutions courantes sont le chaînage séparé (chaque seau contient une liste et les clés en collision y sont ajoutées - montré ici) et l'adressage ouvert (sonder le prochain emplacement vide du tableau). Les deux gardent les recherches correctes ; ils diffèrent par l'agencement de la mémoire et les performances sous forte charge.
Quelle est la complexité temporelle d'une table de hachage ?
L'insertion, la recherche et la suppression sont en
O(1) en moyenne lorsque la fonction de hachage répartit les clés uniformément et que le facteur de charge reste faible. Dans le pire cas - toutes les clés entrant en collision dans un seul seau - elles se dégradent en O(n), d'où l'importance d'une bonne fonction de hachage et du redimensionnement.Qu'est-ce qu'un facteur de charge ?
Le facteur de charge est le nombre d'entrées stockées divisé par le nombre de seaux. À mesure qu'il augmente, les chaînes s'allongent et les opérations ralentissent, c'est pourquoi la plupart des tables de hachage se redimensionnent (re-hachage vers un tableau plus grand) une fois qu'il dépasse un seuil comme 0.75.
Quand dois-je utiliser une table de hachage plutôt qu'un arbre binaire de recherche ?
Utilisez une table de hachage lorsque vous n'avez besoin que de recherches par correspondance exacte et que vous voulez une vitesse
O(1) moyenne sans exigence d'ordre. Utilisez un arbre binaire de recherche équilibré lorsque vous avez besoin de clés triées, de requêtes par intervalle ou de recherches de prédécesseur/successeur, ce qu'une table de hachage ne peut pas faire efficacement. Un ABR offre des opérations O(log n) garanties, tandis qu'une table de hachage échange cette garantie contre des performances moyennes plus rapides.Quelle est la différence entre le chaînage séparé et l'adressage ouvert ?
Le chaînage séparé stocke les clés en collision dans une liste par seau, de sorte qu'un seau peut contenir de nombreuses entrées et que la table ne se remplit jamais vraiment. L'adressage ouvert garde tout dans le tableau lui-même et sonde le prochain emplacement libre lors d'une collision, ce qui est favorable au cache mais se dégrade fortement lorsque le facteur de charge approche 1 et nécessite une gestion soignée de la suppression. Le chaînage tolère des facteurs de charge plus élevés ; l'adressage ouvert utilise la mémoire de manière plus compacte.
Pourquoi ne puis-je pas compter sur une table de hachage pour garder mes clés dans l'ordre d'insertion ou de tri ?
Une fonction de hachage disperse délibérément les clés entre les seaux pour éviter les regroupements, de sorte que l'ordre d'itération reflète l'agencement des seaux, et non l'ordre d'insertion ou de tri. Si vous avez besoin d'un ordre, utilisez une carte/un arbre ordonné ou une structure comme une carte à ordre d'insertion (par exemple, le
dict de Python préserve l'ordre d'insertion, mais c'est une garantie du langage, pas une propriété inhérente de la table de hachage). Ne supposez jamais que l'ordre d'itération correspond à la façon dont vous avez inséré les clés, sauf si le langage le promet explicitement.Ressources associées
Plus de visualisations
