Hash Tables : Collisions, Resizing, Hashing

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Hash-Tabellen verstehen

Ob Sie schon einmal von Wörterbüchern, Hash-Maps oder Hash-Tabellen gehört haben, im Wesentlichen sind sie alle gleich. In diesem Blog bezeichnen wir diese Datenstruktur der Einfachheit halber als Hash-Tabelle.

Beginnen wir mit der Definition, was eine Hash-Tabelle ist. EineHash-Tabelleist eine Datenstruktur, die Schlüssel Werten in Form vonSchlüssel-Wert-Paarenfür eine hocheffiziente Suche zuordnet. Es gibt mehrere Möglichkeiten, es umzusetzen.

Schlüsselkomponenten einer Hash-Tabelle

Mit einemArray verknüpfter Listenund einerHashing-Funktionkönnen wir eine Hash-Tabelle implementieren. Lassen Sie uns tiefer in die Funktionsweise einer Hashing-Funktion eintauchen.

Was ist eine Hashing-Funktion?

Eine Hashing-Funktion ist ein entscheidender Bestandteil einer Hash-Tabelle. Dabei handelt es sich um einen Algorithmus, typischerweise in Form einer Funktion, der eine Eingabe (oder einen „Schlüssel“) entgegennimmt und eine Bytefolge fester Größe zurückgibt, typischerweise in Form einer Ganzzahl. Die Ausgabe wird alsHash-Codeoder einfach als Hash bezeichnet.

Der Hauptzweck einer Hashing-Funktion im Kontext von Hash-Tabellen besteht darin, einen Hash-Code einem gültigen Index eines Arrays von Buckets/Slots zuzuordnen, aus dem der gewünschte Wert gefunden werden kann. Diese Buckets/Slots wären in unserem Fall verknüpfte Listen.

Eigenschaften einer guten Hashing-Funktion:

• Deterministisch: Für eine bestimmte Eingabe sollte immer die gleiche Hash-Ausgabe erzeugt werden.
• Gleichmäßige Verteilung: Es sollte die erwarteten Eingaben möglichst gleichmäßig über seinen Ausgabebereich abbilden.
• Effizient: Es sollte schnell zu berechnen sein.
• Avalanche-Effekt: Eine kleine Änderung in der Eingabe sollte zu einer deutlich anderen Hash-Ausgabe führen.

Warum ein Array verknüpfter Listen verwenden?

Die Verwendung eines Arrays verknüpfter Listen bei der Implementierung von Hash-Tabellen ist eine gängige Technik, die alsVerkettungbekannt ist. Dieser Ansatz bietet mehrere Vorteile:

1. Kollisionsbehandlung: Der Hauptgrund für die Verwendung eines Arrays verknüpfter Listen ist die effiziente Handhabung von Kollisionen. Wenn zwei Schlüssel gehasht und demselben Index zugeordnet werden, können wir das neue Schlüssel-Wert-Paar einfach zur verknüpften Liste an diesem Index hinzufügen.
2. Platzeffizienz: Dadurch kann die Hash-Tabelle mehr Elemente speichern, als das zugrunde liegende Array groß ist. Jeder Array-Slot kann über seine verknüpfte Liste mehrere Elemente enthalten.

Array: [0] -> (key1, value1) -> (key2, value2) [1] -> (key3, value3) [2] -> (key4, value4) -> (key5, value5) -> (key6, value6) [3] -> Empty [4] -> (key7, value7)

In diesem Beispiel hashen die Schlüssel 1 und 2 den Index 0, während die Schlüssel 4, 5 und 6 alle den Index 2 hashen.

Einfügen von Schlüssel-Wert-Paaren

Da wir nun ein gutes Verständnis für Hash-Funktionen haben und wissen, warum wir Verkettungen verwenden, gehen wir den Ablauf des Einfügens von Schlüssel-Wert-Paaren in eine Hash-Tabelle durch:

1. Beim Einfügen des Schlüssels (beliebiger Wert) berechnen wir zunächst denHash-Codedes Schlüssels (normalerweise ein int oder long).Es ist möglich, dass zwei verschiedene Schlüssel denselben Hash-Code haben, da es eine unendliche Anzahl von Schlüsseln und eine endliche Anzahl von Ints geben kann.

2. Ordnen Sie den Hash-Code einem Index im Array zu. Eine gängige Methode zum Zuordnen eines Hash-Codes zu einem Array ist die Verwendung desModulus-Operators. (z. B. hash(key) % array.length)).Es ist möglich, dass mit dieser Methode zwei verschiedene Hash-Codes demselben Index zugeordnet werden können.

3. An einem Index gibt es eine verknüpfte Liste von Schlüsseln und Werten. Speichern Sie das Schlüssel-Wert-Paar in diesem Index. Kollisionen treten auf, wenn Schlüssel dieselben Hash-Codes haben oder Hash-Codes denselben Indizes zugeordnet sind.

Auf Schlüssel-Wert-Paare zugreifen

Der Zugriff auf Schlüssel-Wert-Paare ist in einer Hash-Tabellenimplementierung äußerst effizient. Berechnen Sie einfach den Hash-Code aus dem Schlüssel, berechnen Sie dann den Index aus dem Hash-Code und durchsuchen Sie schließlich die verknüpfte Liste nach dem Wert mit diesem Schlüssel.

Eine gute Implementierung vorausgesetzt, dauert der Zugriff auf Schlüssel-Wert-Paare (auch Einfügen und Löschen) $O(1\#\; \#)O(1)$O(1).

What Makes a Hash Table Implementation "Good"?

A well-implemented hash table should balance efficiency, space utilization, and collision handling. Here are the key factors that contribute to a good hash table implementation:

A Good Hash Function

The heart of any hash table is its hash function. A good hash function should:

• Be quick to compute
• Minimize collisions

Optimal Load Factor

Theload factoris the ratio of filled slots to total slots in the hash table. Maintaining an appropriate load factor is crucial:

A typicalsweet spotis between 0.6 and 0.75

• Too low (< 0.5): Wastes space
• Too high (> 0.8): Increases collision risk

Collision Resolution Techniques

Two primary methods for handling collisions are:

1. Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.

2. Open Addressing: If a collision occurs, look for the next available slot. Keeps all data in the table but requires careful implementation to avoid clustering of stored data.

Note that chaining and open-addressing cannot coexist easily. Logically, it would not make sense to look for the next available slot but store collided items at a specific index.

Dynamic Resizing

As the number of elements grows, the hash table should resize to maintain performance:

Typically, the table size is doubled when the load factor exceeds a threshold. All elements need to be rehashed into the new, larger table.

This operation is expensive but infrequent, keeping the amortized time complexity at O(1).

JavaScript Implementation

This implementation will utilize resizing and chaining for collision resolution. We will assume that our keys are integers.

For the hash function + mapping, we will keep it very simple and simply perform the following given a key:

Classical OOP

class HashNode { constructor(key, value) { this.key = key; this.value = value; this.next = null; } } class HashTable { constructor(capacity = 16) { this.capacity = capacity; this.size = 0; this.buckets = new Array(this.capacity).fill(null); this.threshold = 0.75; } hash(key) { return key % this.capacity; } insert(key, value) { const index = this.hash(key); if (!this.buckets[index]) { this.buckets[index] = new HashNode(key, value); this.size++; } else { let currentNode = this.buckets[index]; while (currentNode.next) { if (currentNode.key === key) { currentNode.value = value; return; } currentNode = currentNode.next; } if (currentNode.key === key) { currentNode.value = value; } else { currentNode.next = new HashNode(key, value); this.size++; } } if (this.size / this.capacity >= this.threshold) { this.resize(); } } get(key) { const index = this.hash(key); let currentNode = this.buckets[index]; while (currentNode) { if (currentNode.key === key) { return currentNode.value; } currentNode = currentNode.next; } return undefined; } remove(key) { const index = this.hash(key); if (!this.buckets[index]) { return false; } if (this.buckets[index].key === key) { this.buckets[index] = this.buckets[index].next; this.size--; return true; } let currentNode = this.buckets[index]; while (currentNode.next) { if (currentNode.next.key === key) { currentNode.next = currentNode.next.next; this.size--; return true; } currentNode = currentNode.next; } return false; } resize() { const newCapacity = this.capacity * 2; const newBuckets = new Array(newCapacity).fill(null); this.buckets.forEach(head => { while (head) { const newIndex = head.key % newCapacity; const next = head.next; head.next = newBuckets[newIndex]; newBuckets[newIndex] = head; head = next; } }); this.buckets = newBuckets; this.capacity = newCapacity; } getSize() { return this.size; } getCapacity() { return this.capacity; } }

Functional OOP

function createHashTable(initialCapacity = 16) { let capacity = initialCapacity; let size = 0; let buckets = new Array(capacity).fill(null); const threshold = 0.75; function hash(key) { return key % capacity; } function resize() { const newCapacity = capacity * 2; const newBuckets = new Array(newCapacity).fill(null); buckets.forEach(function(head) { while (head) { const newIndex = head.key % newCapacity; const next = head.next; head.next = newBuckets[newIndex]; newBuckets[newIndex] = head; head = next; } }); buckets = newBuckets; capacity = newCapacity; } return { insert: function(key, value) { const index = hash(key); const newNode = { key, value, next: null }; if (!buckets[index]) { buckets[index] = newNode; size++; } else { let currentNode = buckets[index]; while (currentNode.next) { if (currentNode.key === key) { currentNode.value = value; return; } currentNode = currentNode.next; } if (currentNode.key === key) { currentNode.value = value; } else { currentNode.next = newNode; size++; } } if (size / capacity >= threshold) { resize(); } }, get: function(key) { const index = hash(key); let currentNode = buckets[index]; while (currentNode) { if (currentNode.key === key) { return currentNode.value; } currentNode = currentNode.next; } return undefined; }, remove: function(key) { const index = hash(key); if (!buckets[index]) { return false; } if (buckets[index].key === key) { buckets[index] = buckets[index].next; size--; return true; } let currentNode = buckets[index]; while (currentNode.next) { if (currentNode.next.key === key) { currentNode.next = currentNode.next.next; size--; return true; } currentNode = currentNode.next; } return false; }, getSize: function() { return size; }, getCapacity: function() { return capacity; } }; }

The above is the detailed content of Hash Tables : Collisions, Resizing, Hashing. For more information, please follow other related articles on the PHP Chinese website!