Hashtabelle
Zuletzt aktualisiert
Eine Hashtabelle speichert Elemente in einem Array von Buckets. Um einen Schlüssel abzulegen oder zu finden, führt sie den Schlüssel durch eine Hashfunktion und nimmt das Ergebnis modulo der Anzahl der Buckets - das ergibt den Bucket-Index in O(1). Drücke oben auf Abspielen, um zu sehen, wie jeder Schlüssel zu einem Bucket gehasht und gespeichert wird und wie eine Suche dann direkt zum richtigen Bucket springt.
Wenn zwei Schlüssel im selben Bucket landen - eine Kollision - verwendet diese Visualisierung separate Verkettung: Jeder Bucket enthält eine kleine Liste, und kollidierende Schlüssel werden ihr angehängt. Solange die Tabelle nicht zu voll ist (ein niedriger Füllfaktor) und der Hash die Schlüssel gut verteilt, bleiben die Ketten kurz und Einfügen, Suchen und Löschen sind im Durchschnitt O(1).
Zeitkomplexität
| Operation | Durchschnitt | Schlechtester Fall |
|---|---|---|
| Einfügen | O(1) | O(n) (alle Schlüssel kollidieren) |
| Suchen | O(1) | O(n) |
| Löschen | O(1) | O(n) |
| Speicher | O(n) | O(n) |
Schlüsselkonzepte
| Begriff | Bedeutung |
|---|---|
| Hashfunktion | Bildet einen Schlüssel auf einen Bucket-Index ab |
| Kollision | Zwei Schlüssel landen im selben Bucket |
| Separate Verkettung | Jeder Bucket enthält eine Liste kollidierender Einträge |
| Offene Adressierung | Alternative: den nächsten freien Slot sondieren |
| Füllfaktor | Einträge / Buckets - steuert die Größenänderung |
Durchgerechnetes Beispiel
Einfügen der Schlüssel 20, 34, 9, 13 in eine Tabelle mit 7 Buckets, mit hash(k) = k % 7:
| Schritt | Struktur | Aktion |
|---|---|---|
20 einfügen | Bucket 6: [20] | 20 % 7 = 6, Bucket 6 leer, 20 speichern |
34 einfügen | Bucket 6: [20, 34] | 34 % 7 = 6, Kollision mit 20, 34 an die Kette anhängen |
9 einfügen | Bucket 2: [9] | 9 % 7 = 2, Bucket 2 leer, 9 speichern |
13 einfügen | Bucket 6: [20, 34, 13] | 13 % 7 = 6, Kollision, 13 an die Kette von Bucket 6 anhängen |
34 suchen | Bucket 6: [20, 34, 13] | 34 % 7 = 6, Kette durchlaufen: 20 nein, 34 passt - gefunden |
Wann eine Hashtabelle verwenden
| Verwende sie, wenn | Vermeide sie, wenn |
|---|---|
Du im Durchschnitt O(1) beim Einfügen, Suchen und Löschen nach Schlüssel brauchst | Du die Schlüssel sortiert halten musst - verwende einen ausgeglichenen BST |
| Die Schlüssel keine nützliche Ordnung haben und du nur exakte Zugehörigkeit prüfst | Du Bereichsabfragen oder Suchen nach dem nächstgelegenen Schlüssel brauchst |
| Du dir etwas zusätzlichen Speicher für Buckets und einen niedrigen Füllfaktor leisten kannst | Der Speicher extrem knapp ist und jedes Byte zählt |
| Eine gute Hashfunktion für deinen Schlüsseltyp existiert | Die Worst-Case-Latenz beschränkt sein muss - Kollisionen machen sie O(n) |
Hash Table-Code
Eine saubere, lauffähige Hash Table-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Hash Table-Code in 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])Hash Table-Code in 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"));Hash Table-Code in 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}Hash Table-Code in 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}Hash Table-Code in 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}Hashtabelle FAQ
Was ist eine Hash-Kollision und wie wird sie aufgelöst?
Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel im selben Bucket landen. Die beiden gängigen Lösungen sind separate Verkettung (jeder Bucket enthält eine Liste, und kollidierende Schlüssel werden angehängt - hier gezeigt) und offene Adressierung (den nächsten leeren Slot im Array sondieren). Beide halten die Suchen korrekt; sie unterscheiden sich im Speicher-Layout und in der Leistung bei hoher Last.
Was ist die Zeitkomplexität einer Hashtabelle?
Einfügen, Suchen und Löschen sind im Durchschnitt
O(1), wenn die Hashfunktion die Schlüssel gleichmäßig verteilt und der Füllfaktor niedrig gehalten wird. Im schlechtesten Fall - alle Schlüssel kollidieren in einem einzigen Bucket - verschlechtern sie sich zu O(n), weshalb eine gute Hashfunktion und Größenänderung wichtig sind.Was ist ein Füllfaktor?
Der Füllfaktor ist die Anzahl der gespeicherten Einträge geteilt durch die Anzahl der Buckets. Mit seinem Wachstum werden die Ketten länger und die Operationen langsamer, weshalb die meisten Hashtabellen die Größe ändern (in ein größeres Array umhashen), sobald er einen Schwellenwert wie 0.75 überschreitet.
Wann sollte ich eine Hashtabelle statt eines binären Suchbaums verwenden?
Verwende eine Hashtabelle, wenn du nur exakte Suchen brauchst und durchschnittliche
O(1)-Geschwindigkeit ohne Ordnungsanforderung willst. Verwende einen ausgeglichenen binären Suchbaum, wenn du sortierte Schlüssel, Bereichsabfragen oder Vorgänger-/Nachfolger-Suchen brauchst, was eine Hashtabelle nicht effizient kann. Ein BST bietet garantierte O(log n)-Operationen, während eine Hashtabelle diese Garantie gegen schnellere Durchschnittsleistung eintauscht.Was ist der Unterschied zwischen separater Verkettung und offener Adressierung?
Separate Verkettung speichert kollidierende Schlüssel in einer Liste pro Bucket, sodass ein Bucket viele Einträge enthalten kann und die Tabelle nie wirklich voll wird. Offene Adressierung hält alles im Array selbst und sondiert bei einer Kollision den nächsten freien Slot, was cache-freundlich ist, sich aber stark verschlechtert, wenn der Füllfaktor sich 1 nähert, und eine sorgfältige Behandlung des Löschens erfordert. Verkettung toleriert höhere Füllfaktoren; offene Adressierung nutzt den Speicher kompakter.
Warum kann ich mich nicht darauf verlassen, dass eine Hashtabelle meine Schlüssel in Einfüge- oder Sortierreihenfolge hält?
Eine Hashfunktion streut die Schlüssel absichtlich über die Buckets, um Clusterbildung zu vermeiden, sodass die Iterationsreihenfolge das Bucket-Layout widerspiegelt, nicht die Einfüge- oder Sortierreihenfolge. Wenn du eine Ordnung brauchst, verwende eine geordnete Map/einen Baum oder eine Struktur wie eine einfügereihenfolge-erhaltende Map (z. B. bewahrt Pythons
dict die Einfügereihenfolge, aber das ist eine Sprachgarantie, keine inhärente Eigenschaft der Hashtabelle). Nimm nie an, dass die Iterationsreihenfolge der Reihenfolge deiner Einfügungen entspricht, es sei denn, die Sprache verspricht es ausdrücklich.Verwandte Ressourcen
Mehr Visualisierungen
