Was ist eine Hash-Tabelle und warum braucht man sie?
Eine Hash-Tabelle (Hash-Tabelle oder Hash-Map) ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert und einen sehr schnellen Zugriff auf Daten ermöglicht. Im Durchschnitt werden Such-, Einfüge- und Löschvorgänge in O (1) - konstanter Zeit ausgeführt. Dies bedeutet, dass unabhängig davon, ob 10 oder 10 Millionen Elemente in der Tabelle gespeichert sind, der Zugriff auf jedes Element ungefähr die gleiche Zeit in Anspruch nimmt.
Ein einfaches Beispiel aus dem Leben:
const userAges = {
"Alexey": 28,
"Maria": 25,
"Dmitry": 32
};
console.log(userAges["Maria"]); // 25 - sofortiger Zugang!In den meisten modernen Programmiersprachen sind Hash-Tabellen integriert: dict in Python, Map in JavaScript, HashMap in Java, map in Go.
Wie funktioniert eine Hash-Tabelle?
Unter der Haube ist eine Hash-Tabelle ein gewöhnliches Array. Die Magie geschieht dank Hash-Funktionen, die einen Schlüssel (Zeile, Zahl oder Objekt) in einen Array-Index umwandelt.
Arbeitsprozess:
Schlüssel-Hashing: Der Schlüssel (z. B. "Alexey") wird durch eine Hash-Funktion übergeben, die eine Zahl zurückgibt (z. B. 42)
Berechnung des Index: Das Hash-Ergebnis wird mit Hilfe der Modulo-Operation in einen Array-Index umgewandelt:
index = hash % array.lengthSpeichern des Wertes: Der Wert wird in der Zelle des Arrays mit diesem Index gespeichert
"Alexey" → hash("Alexey") → 1892374 → 1892374 % 10 → Index 4 Array: [_, _, _, _, {key: "Alexey", value: 28}, _, _, _, _, _]
Hash-Funktionen: das Herz des Systems
Eine gute Hash-Funktion sollte mehrere Eigenschaften haben:
Determinismus - Der gleiche Schlüssel gibt immer den gleichen Hash
Gleichmäßigkeit - Hashes sollten gleichmäßig über den gesamten Wertebereich verteilt sein
Schnelligkeit - Die Berechnung des Hashs sollte schnell sein
Minimierung von Kollisionen - Verschiedene Schlüssel müssen unterschiedliche Hashes ergeben
Beispiel einer einfachen Hash-Funktion für Zeichenfolgen:
function simpleHash(str, tableSize) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
}
return hash;
}
console.log(simpleHash("Alexey", 100)); // z.B. 67
console.log(simpleHash("Maria", 100)); // z.B. 23In realen Systemen werden komplexere Funktionen wie MurmurHash, CityHash oder kryptografische Funktionen wie SHA-256 (für spezielle Fälle) verwendet.
Kollisionen: Wenn zwei Schlüssel denselben Platz wollen
Kollision tritt auf, wenn zwei verschiedene Schlüssel nach dem Hashing denselben Index erhalten. Dies ist ein unvermeidliches Problem, da die Anzahl der möglichen Schlüssel normalerweise größer ist als die Größe des Arrays.
"Aleksey" → Index 4 "Dmitry" → Index 4 ← Kollision!
Kettenmethode (Chaining)
Die beliebteste Methode zur Lösung von Kollisionen. In jeder Zelle des Arrays wird nicht ein Wert gespeichert, sondern eine Liste (Kette) aller Werte mit demselben Index.
class HashTable {
constructor(size = 50) {
this.table = new Array(size);
this.size = size;
}
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
}
return hash;
}
set(key, value) {
const index = this._hash(key);
if (!this.table[index]) {
this.table[index] = [];
}
// Wir prüfen, ob es einen solchen Schlüssel bereits gibt
for (let item of this.table[index]) {
if (item[0] === key) {
item[1] = value; // Wert wird aktualisiert
return;
}
}
// Wir fügen ein neues Schlüssel-Wert-Paar hinzu
this.table[index].push([key, value]);
}
get(key) {
const index = this._hash(key);
const bucket = this.table[index];
if (!bucket) return undefined;
for (let item of bucket) {
if (item[0] === key) {
return item[1];
}
}
return undefined;
}
remove(key) {
const index = this._hash(key);
const bucket = this.table[index];
if (!bucket) return false;
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
return true;
}
}
return false;
}
}
// Anwendung
const users = new HashTable();
users.set("Alexey", { age: 28, city: "Moscow" });
users.set("Maria", { age: 25, city: "St. Petersburg" });
users.set("Dmitry", { age: 32, city: "Novosibirsk" });
console.log(users.get("Maria")); // { age: 25, city: "Sankt Petersburg" }users.remove("Alexey");
console.log(users.get("Alexey")); // undefinedOffene Adressierung (Open Addressing)
Anstatt Ketten zu erstellen, suchen wir bei einer Kollision nach einem anderen freien Zelle im Array gemäß einem bestimmten Algorithmus:
Lineares Stanzen - Wir überprüfen die folgenden Zellen nacheinander: index, index+1, index+2...
class HashTableOpenAddressing {
constructor(size = 50) {
this.table = new Array(size);
this.size = size;
this.count = 0;
}
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
}
return hash;
}
set(key, value) {
if (this.count / this.size > 0.7) {
this._resize(); // Wir vergrößern die Größe beim Füllen >70%
}
let index = this._hash(key);
let i = 0;
while (this.table[index] !== undefined && this.table[index].key !== key) {
i++;
index = (this._hash(key) + i) % this.size; // Lineares Stanzen
}
if (this.table[index] === undefined) {
this.count++;
}
this.table[index] = { key, value };
}
get(key) {
let index = this._hash(key);
let i = 0;
while (this.table[index] !== undefined) {
if (this.table[index].key === key) {
return this.table[index].value;
}
i++;
index = (this._hash(key) + i) % this.size;
}
return undefined;
}
_resize() {
const oldTable = this.table;
this.size *= 2;
this.table = new Array(this.size);
this.count = 0;
for (let item of oldTable) {
if (item !== undefined) {
this.set(item.key, item.value);
}
}
}
}Quadratisches Perforieren — wir prüfen: index, index+1², index+2², index+3²...
Doppeltes Hashing - Verwenden Sie die zweite Hash-Funktion, um den Schritt zu berechnen.
Leistung und Komplexität
Operation | Durchschnittlicher Fall | Schlimmster Fall |
|---|---|---|
Einfügen | O(1) | O(n) |
Suche | O(1) | O(n) |
Entfernung | O(1) | O(n) |
Load Factor (Auslastungsfaktor) = Anzahl der Elemente / Größe des Arrays
Bei einem Lastfaktor > 0,7 wird normalerweise ausgeführt rehashing — Erstellen eines neuen größeren Arrays und Verschieben aller Elemente.
Echte Anwendungsfälle
1. Zwischenspeichern von Ergebnissen
class Cache {
constructor() {
this.cache = new Map();
}
async fetchUser(userId) {
// Wir überprüfen den Cache
if (this.cache.has(userId)) {
console.log('Received from cache');
return this.cache.get(userId);
}
// Daten werden geladen
const user = await api.getUser(userId);
// Wird zwischengespeichert
this.cache.set(userId, user);
return user;
}
}2. Berechnung der Häufigkeit von Elementen
function countWords(text) {
const wordCount = new Map();
const words = text.toLowerCase().split(/\s+/);
for (let word of words) {
wordCount.set(word, (wordCount.get(word) || 0) + 1);
}
return wordCount;
}
const text = "JavaScript is a programming language JavaScript is popular";
console.log(countWords(text));
// Karte { 'javascript' => 2, 'ist' => 1, 'Sprache' => 1, ... }... }3. Suche nach Duplikaten
function hasDuplicates(arr) {
const seen = new Set();
for (let item of arr) {
if (seen.has(item)) {
return true;
}
seen.add(item);
}
return false;
}
console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true4. Indexierung in Datenbanken
Datenbanken verwenden Hash-Indizes, um Datensätze schnell nach Schlüssel zu suchen:
-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);
-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';5. Eindeutige Benutzerkennungen
class Session {
constructor() {
this.sessions = new Map();
}
createSession(userId) {
const sessionId = this.generateSessionId();
this.sessions.set(sessionId, {
userId,
createdAt: Date.now(),
data: {}
});
return sessionId;
}
getSession(sessionId) {
return this.sessions.get(sessionId);
}
destroySession(sessionId) {
this.sessions.delete(sessionId);
}
generateSessionId() {
return Math.random().toString(36).substring(2);
}
}6. Routing in Web-Frameworks
class Router {
constructor() {
this.routes = new Map();
}
addRoute(path, handler) {
this.routes.set(path, handler);
}
handleRequest(path) {
const handler = this.routes.get(path);
if (handler) {
return handler();
}
return 'Not Found';
}
}
const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');
console.log(router.handleRequest('/home')); // Home Page - O(1)!7. Anagramme und Gruppierung von Zeilen
function groupAnagrams(words) {
const groups = new Map();
for (let word of words) {
// Wir sortieren die Buchstaben als Schlüssel
const key = word.split('').sort().join('');
if (!groups.has(key)) {
groups.set(key, []);
}
groups.get(key).push(word);
}
return Array.from(groups.values());
}
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]Map vs. Object in JavaScript: Was soll man wählen?
JavaScript bietet zwei Möglichkeiten, mit Hash-Tabellen zu arbeiten:
Object:
const obj = {};
obj.name = "Alexey";
obj['age'] = 28;Map:
const map = new Map();
map.set('name', 'Alexey');
map.set('age', 28);Wann man Map verwendet:
Schlüssel sind keine Zeichenfolgen (Objekte, Zahlen, Funktionen)
Iteration in der Reihenfolge des Hinzufügens erforderlich
Häufige Hinzufügung/Entfernung von Elementen
Sie müssen die genaue Anzahl der Elemente kennen (
map.size)
Wann ist Object zu verwenden:
Schlüssel sind immer Strings
Benötigt JSON.stringify/parse
Einfache Konfigurationsstruktur
Praktische Tipps
1. Wählen Sie die richtige Anfangsgröße
// Wenn Sie wissen, dass es ~1000 Elemente geben wird
const map = new Map(); // Standardmäßig kleine Größe
// vs
const users = new HashTable(2000); // Wir vermeiden Rehashing2. Vorsicht bei Objekten wie Schlüsseln
const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };
map.set(key1, 'value1');
console.log(map.get(key2)); // undefined! Verschiedene Objekte3. Bereinigen Sie nicht verwendete Daten
// Verwenden Sie WeakMap für die automatische Reinigung
const cache = new WeakMap();
let user = { name: 'Alexey' };
cache.set(user, 'some data');
user = null; // Die Daten werden automatisch aus WeakMap gelöschtBefund
Hash-Tabellen sind eine grundlegende Datenstruktur, die überall verwendet wird: von Datenbanken bis zu Web-Frameworks, von Compilern bis zu Suchmaschinen. Wenn Sie deren Aufbau, Konfliktlösung und Leistung verstehen, werden Sie zu einem effektiveren Entwickler.
In Kodike Wir analysieren nicht nur Hash-Tabellen, sondern auch Dutzende anderer wichtiger Themen für Entwickler: von den Grundlagen bis hin zu fortgeschrittenen Techniken. Unsere Kurse umfassen praktische Aufgaben und reale Fälle aus der Industrie.
Treten Sie unserem Telegram-Kanal bei — Hier gibt es eine freundliche Entwickler-Community, jede Woche nützliche Materialien, Analysen interessanter Aufgaben und Antworten auf Fragen.
Wir wachsen zusammen! 🚀