Verwendung von Hashmaps in JavaScript: Zuordnung von Keys zu Values in Datenstrukturen

Was sind Hashmaps?

Hashmaps sind eine Datenstruktur, die Schlüssel-Wert-Paare speichert, wobei jeder Schlüssel einzigartig ist und auf einen Wert verweist. Der Schlüssel wird verwendet, um den Wert zu indizieren, was eine schnelle Abfrage des zugehörigen Werts ermöglicht. Hashmaps verwenden eine Hash-Funktion, um einen Index für die Speicherung und Abfrage von Werten zu berechnen. Die Hash-Funktion nimmt den Schlüssel als Eingabe und generiert einen eindeutigen Hash-Code, der dann verwendet wird, um den Index zu bestimmen, an dem der Wert im Array oder Bucket gespeichert wird.

Hashmaps vs JavaScript-Objekte

JavaScript-Objekte können ebenfalls Schlüssel-Wert-Paare speichern, ähnlich wie Hashmaps. Allerdings bieten Hashmaps Vorteile gegenüber Objekten:

1. Schlüsseltypen: Hashmaps erlauben jeden Datentyp als Schlüssel, einschließlich Objekte, Arrays und Funktionen. JavaScript-Objekte sind auf die Verwendung von Strings und Symbolen als Schlüssel beschränkt.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Ungültig: Objekte können nicht als Schlüssel in Objekten verwendet werden

2. Beibehaltung der Reihenfolge: Hashmaps behalten die Einfügereihenfolge der Elemente bei, das heißt, die Reihenfolge, in der Schlüssel-Wert-Paare zur Hashmap hinzugefügt werden, bleibt erhalten. JavaScript-Objekte garantieren keine bestimmte Reihenfolge ihrer Eigenschaften.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Ausgabe: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Ausgabe: ['a', 'b', 'c'] (Nicht garantiert)

3. Größenverfolgung: Hashmaps bieten Methoden wie size(), um die Anzahl der in der Hashmap gespeicherten Elemente zu erhalten. Bei JavaScript-Objekten müssten Sie die Anzahl der Eigenschaften manuell verfolgen oder Object.keys(obj).length verwenden, um die Größe zu bestimmen.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Ausgabe: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Ausgabe: 2

Zeitkomplexität von Hashmap-Operationen

Einer der Hauptvorteile von Hashmaps ist ihre Zeitkomplexität für grundlegende Operationen. Hashmaps bieten eine konstante Zeitkomplexität, bezeichnet als O(1), für die folgenden Operationen:

1. Einfügen: Das Hinzufügen eines neuen Schlüssel-Wert-Paars zur Hashmap ist eine O(1)-Operation. Die Hash-Funktion wird verwendet, um den Index zu berechnen, und das Schlüssel-Wert-Paar wird an diesem Index im Array oder Bucket gespeichert.

2. Löschen: Das Entfernen eines Schlüssel-Wert-Paars aus der Hashmap ist ebenfalls eine O(1)-Operation. Die Hash-Funktion wird verwendet, um den Index zu finden, an dem das Schlüssel-Wert-Paar gespeichert ist, und dann wird es von diesem Index entfernt.

3. Suche: Das Abrufen des Werts, der einem bestimmten Schlüssel zugeordnet ist, ist eine O(1)-Operation. Die Hash-Funktion wird verwendet, um den Index basierend auf dem Schlüssel zu berechnen, und der Wert kann an diesem Index abgerufen werden.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Daten aus dem Cache abrufen (O(1)-Suche)
  } else {
    const data = fetchFromAPI(key); // Daten von der API abrufen
    cache.set(key, data); // Daten im Cache speichern (O(1)-Einfügen)
    return data;
  }
}

Eine Hashmap erstellen

Um eine neue Hashmap zu erstellen, verwenden Sie den Konstruktor new Map(). Dieser erstellt eine leere Hashmap zur Speicherung von Schlüssel-Wert-Paaren.

const myHashmap = new Map();

Zum Beispiel, um eine Hashmap zur Speicherung von Studentendaten zu erstellen:

const studentMap = new Map();

Hinzufügen von Schlüssel-Wert-Paaren

Um ein neues Schlüssel-Wert-Paar zur Hashmap hinzuzufügen, verwenden Sie die Methode set(). Sie nimmt zwei Argumente: den Schlüssel und den Wert.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

Im obigen Beispiel fügen wir zwei Schlüssel-Wert-Paare zu myHashmap hinzu: 'name' verweist auf 'John' und 'age' verweist auf 25.

Fügen wir einige Studentendaten zu unserer studentMap hinzu:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Werte abrufen

Um den Wert für einen bestimmten Schlüssel abzurufen, verwenden Sie die Methode get(). Sie nimmt den Schlüssel als Argument und gibt den Wert zurück.

const name = myHashmap.get('name');
console.log(name); // Ausgabe: 'John'

In diesem Beispiel rufen wir den Wert für den Schlüssel 'name' aus der myHashmap ab, der 'John' ist.

Um die Daten eines bestimmten Studenten aus studentMap abzurufen:

const student = studentMap.get('2');
console.log(student); // Ausgabe: { name: 'Alice', age: 22, major: 'Mathematics' }

Prüfen auf Schlüsselexistenz

Um zu prüfen, ob ein Schlüssel in der Hashmap existiert, verwenden Sie die Methode has(). Sie nimmt den Schlüssel als Argument und gibt einen booleschen Wert zurück.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Ausgabe: true

Hier prüfen wir, ob der Schlüssel 'age' in der myHashmap existiert, indem wir die Methode has() verwenden, die true zurückgibt.

Prüfen, ob ein Student mit der ID '4' in studentMap existiert:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Ausgabe: false

Entfernen von Schlüssel-Wert-Paaren

Um ein Schlüssel-Wert-Paar aus der Hashmap zu entfernen, verwenden Sie die Methode delete(). Sie nimmt den Schlüssel als Argument und entfernt das Schlüssel-Wert-Paar aus der Hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Ausgabe: false

In diesem Beispiel entfernen wir das Schlüssel-Wert-Paar mit dem Schlüssel 'age' aus der myHashmap mit der Methode delete(). Nach dem Entfernen gibt has('age') false zurück.

Einen Studenten aus studentMap entfernen:

studentMap.delete('1');
console.log(studentMap.has('1')); // Ausgabe: false

Die Größe der Hashmap abrufen

Um die Anzahl der Schlüssel-Wert-Paare in der Hashmap zu erhalten, verwenden Sie die Eigenschaft size. Sie gibt die Größe der Hashmap zurück.

console.log(myHashmap.size); // Ausgabe: 1

Hier greifen wir auf die Eigenschaft size der myHashmap zu, die 1 zurückgibt und anzeigt, dass ein Schlüssel-Wert-Paar in der Hashmap vorhanden ist.

Die Anzahl der Studenten in studentMap abrufen:

console.log(studentMap.size); // Ausgabe: 2

Zusammenfassung der Hashmap-Operationen

Dies sind die grundlegenden Operationen, die Sie mit einer Hashmap unter Verwendung des Map-Objekts von JavaScript ausführen können. Das Map-Objekt bietet eine Möglichkeit, mit Schlüssel-Wert-Paaren zu arbeiten, und stellt Methoden zur Manipulation und zum Zugriff auf die Daten in der Hashmap bereit.

Das Map-Objekt bewahrt die Reihenfolge der Schlüssel-Wert-Paare, was bedeutet, dass beim Iterieren über die Hashmap mit Methoden wie forEach() oder der for...of-Schleife die Schlüssel-Wert-Paare in der Reihenfolge ihres Hinzufügens abgerufen werden.

Die forEach()-Methode

Die Methode forEach() ist in das Map-Objekt integriert. Sie ermöglicht es Ihnen, über jedes Schlüssel-Wert-Paar in der Hashmap zu iterieren. Sie verwendet eine Callback-Funktion, die für jedes Paar ausgeführt wird.

Die Callback-Funktion erhält drei Parameter:

1. value: Der Wert des aktuellen Paars.
2. key: Der Schlüssel des aktuellen Paars.
3. map: Die Hashmap, auf der forEach() aufgerufen wurde.

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

Die for...of-Schleife

Sie können auch eine for...of-Schleife verwenden, um über eine Hashmap zu iterieren. Die for...of-Schleife funktioniert mit iterierbaren Objekten wie Arrays, Strings und Maps.

Wenn Sie for...of mit einer Hashmap verwenden, gibt jede Iteration ein Array mit dem [key, value]-Paar zurück. !!!

Visualisierung der Hashmap-Iteration

Hier ist ein Diagramm, das zeigt, wie die Iteration über eine Hashmap funktioniert:

Das Diagramm zeigt die Hashmap und die Iteration über jedes Schlüssel-Wert-Paar. Für jedes Paar verarbeiten wir es basierend auf dem, was wir tun müssen, wie Berechnungen, Vergleiche oder andere Operationen.

Sowohl forEach() als auch for...of ermöglichen es Ihnen, über die Schlüssel-Wert-Paare einer Hashmap in JavaScript zu iterieren. Welche Sie verwenden, hängt von Ihren spezifischen Anforderungen ab. forEach() ist gut, wenn Sie etwas für jedes Paar tun möchten, während for...of nützlich ist, wenn Sie sowohl die Schlüssel als auch die Werte in jeder Iteration benötigen.

Beachten Sie, dass die Reihenfolge der Iteration in einer Hashmap auf der Reihenfolge basiert, in der die Paare hinzugefügt wurden. Das Map-Objekt von JavaScript bewahrt diese Reihenfolge.

Die Iteration über Hashmaps ist üblich bei der Arbeit mit Schlüssel-Wert-Paaren, und JavaScript bietet diese Methoden, um es einfacher und schneller zu machen. Weitere Informationen zu Map-Objekten und Iteration finden Sie in den MDN Web Docs.

Was sind Kollisionen?

In einer Hashmap treten Kollisionen auf, wenn zwei oder mehr Schlüssel auf denselben Index hashen. Das bedeutet, dass mehrere Schlüssel-Wert-Paare an derselben Position im Array oder Bucket gespeichert werden müssen. Wenn sie nicht gut behandelt werden, können Kollisionen zum Überschreiben von Daten oder zu langsamem Abrufen von Werten führen.

Hier ist ein Beispiel für eine Kollision in einer Hashmap:

In diesem Beispiel hashen sowohl die Schlüssel 'John' als auch 'Alice' auf denselben Index (Index 0), was eine Kollision verursacht.

Wenn Kollisionen nicht behoben werden, können diese Probleme auftreten:

1. Überschreiben von Daten: Wenn ein neues Schlüssel-Wert-Paar auf denselben Index wie ein bestehendes Paar hasht, könnte das bestehende Paar überschrieben werden, was zu Datenverlust führt.

2. Langsames Abrufen: Wenn Kollisionen auftreten, wird das Finden von Werten langsamer, da die Hashmap mehr Schritte ausführen muss, um den richtigen Wert unter den kollidierenden Paaren zu finden.

Um diese Probleme zu beheben, verwenden Hashmaps Techniken zur Kollisionsbehandlung.

Möglichkeiten zur Behandlung von Kollisionen

Es gibt zwei Hauptmethoden zur Behandlung von Kollisionen in Hashmaps:

1. Separate Verkettung (Separate Chaining)

• Jeder Index des Arrays oder Buckets der Hashmap speichert eine verkettete Liste von Schlüssel-Wert-Paaren.
• Wenn eine Kollision auftritt, wird das neue Schlüssel-Wert-Paar zur verketteten Liste an diesem Index hinzugefügt.
• Das Finden eines Werts bedeutet, die verkettete Liste am gehashten Index zu durchlaufen, um das gewünschte Schlüssel-Wert-Paar zu finden.

2. Offene Adressierung (Open Addressing)

• Die offene Adressierung verwendet keine verketteten Listen zur Behandlung von Kollisionen. Stattdessen sucht sie den nächsten freien Index im Array, wenn eine Kollision auftritt.
• Es gibt verschiedene Möglichkeiten, den nächsten Index zu finden, wie lineares Probing, quadratisches Probing und Double Hashing.
• Wenn eine Kollision auftritt, verwendet die Hashmap die Probing-Methode, um den nächsten leeren Platz im Array zu finden, um das Schlüssel-Wert-Paar zu speichern.

Best Practices für die Verwendung von Hashmaps

1. Wählen Sie eine gute Hash-Funktion, die Kollisionen reduziert und Schlüssel gleichmäßig verteilt.
2. Berücksichtigen Sie die erwartete Anzahl von Elementen und die gewünschte Performance bei der Wahl der Anfangsgröße der Hashmap.
3. Seien Sie sich bewusst, wie Kollisionen die Geschwindigkeit von Hashmap-Operationen beeinflussen können, insbesondere bei vielen Kollisionen.
4. Verwenden Sie separate Verkettung oder offene Adressierung basierend auf den Anforderungen Ihrer Anwendung, unter Berücksichtigung von Faktoren wie Speicherverbrauch und Abrufgeschwindigkeit.