Zum Inhalt
wannacode

Map und Set

Kurz gesagt: Eine Map (Dictionary) speichert Paare aus Schlüssel und Wert mit eindeutigen Schlüsseln und findet einen Wert schnell über seinen Schlüssel, und ein Set speichert eindeutige Werte.

Problem

Wer ist dieser Benutzer?

Die Benutzer der Website stehen in einem Array. Bei jeder Anmeldung suchst du die E-Mail zum Benutzernamen:

function findEmail(users, username) {
  for (const u of users) {
    if (u.username === username) {
      return u.email;
    }
  }
  return null;
}

Bei drei Benutzern geht das sofort. Bei 2 000 000 vergleicht jede Anmeldung bis zu 2 000 000 Namen, und es gibt Tausende Anmeldungen pro Minute. Ein Telefonbuch liest du auch nicht ab der ersten Seite. Du schlägst direkt beim Buchstaben auf.

Die Idee

Map: Schlüssel → Wert

Du willst fragen „Welche E-Mail hat weber?“ und sofort die Antwort bekommen. Die Collection dafür heißt Map (auch Wörterbuch oder Dictionary). Sie speichert Paare: einen Schlüssel und einen Wert. In JavaScript heißt sie Map:

const emails = new Map();
emails.set("mueller", "mueller@example.com");
emails.set("mschmidt", "mschmidt@example.com");
emails.set("weber", "weber@example.com");


console.log(emails.get("weber"));
console.log(emails.get("niemand"));
console.log(`Benutzer: ${emails.size}`);
Ausgabe
weber@example.com
undefined
Benutzer: 3
  • new Map() ist eine leere Map. set(key, value) legt ein Paar hinein, und get(key) gibt den Wert zurück.
  • Ein Schlüssel, den es nicht gibt, ergibt undefined.
  • size ist die Anzahl der Paare. Du schreibst es ohne Klammern: Es ist eine Eigenschaft, keine Methode.

In JavaScript sieht auch ein einfaches Objekt {} wie eine Map aus: stock[key] = value. Viel Code benutzt es so, aber es gibt Fallen:

const stock = {};
stock[1] = "Laptop";
stock["1"] = "Maus";
console.log(stock);
console.log("toString" in stock);


const map = new Map();
map.set(1, "Laptop");
map.set("1", "Maus");
console.log(map);
console.log(map.has("toString"));
Ausgabe
{ '1': 'Maus' }
true
Map(2) { 1 => 'Laptop', '1' => 'Maus' }
false
  • Die Schlüssel eines Objekts werden immer zu Text: 1 und "1" sind ein Schlüssel, und „Maus“ hat „Laptop“ ersetzt.
  • Im Objekt gibt es auch Schlüssel, die du nie hineingelegt hast: toString kommt vom gemeinsamen Prototyp aller Objekte.
  • Eine Map behält den Typ des Schlüssels, und darin ist nur, was du hineingelegt hast. Für Paare aus Schlüssel und Wert nimm also Map.

get durchläuft nicht alle Paare. Es findet den Platz des Schlüssels fast sofort, egal wie viele es sind. Wie das geht, zeigt die nächste Lektion.

Die Idee

Das Lager: ändern und prüfen

Der Bestand im Lager: Artikel → Anzahl.

const stock = new Map();
stock.set("Laptop", 4);
stock.set("Maus", 25);
stock.set("Laptop", 3);


console.log(stock.get("Laptop"));
console.log(stock.has("Monitor"));
console.log(stock.get("Monitor") ?? 0);
stock.delete("Maus");
console.log(stock.size);
Ausgabe
3
false
0
1
  • Schlüssel sind eindeutig. Das zweite set("Laptop", 3) fügt keine neue Zeile hinzu. Es ersetzt 4 durch 3.
  • has fragt, ob der Schlüssel in der Map ist.
  • get(key) ?? 0 gibt den Wert, oder 0, wenn es den Schlüssel nicht gibt. a ?? b ist a, außer wenn a undefined oder null ist: Dann ist es b. Das schützt dich vor undefined.
  • delete(key) entfernt das Paar.
Genauer, für Neugierige
  • Werte dürfen sich wiederholen: Laptop und Maus können beide 3 sein. Schlüssel nicht.
  • Eine Methode „Ist dieser Wert darin?“ hat Map nicht. Du musst values() durchlaufen, denn eine Map ist nur nach Schlüssel schnell.

Probier es aus

Wie viele stehen auf der Karte?

Was gibt das Programm aus?

const menu = new Map();
menu.set("Kaffee", 2);
menu.set("Tee", 2);
menu.set("Kaffee", 3);
console.log(menu.size, menu.get("Kaffee"));
Antwort

Die Idee

Durchlaufen und Reihenfolge

Die Lieferkosten nach Stadt. for...of über eine Map liefert Paare [key, value], und const [city, price] teilt jedes in zwei Namen auf:

const delivery = new Map();
delivery.set("Berlin", 4.5);
delivery.set("Hamburg", 5.2);
delivery.set("Bremen", 6.0);
delivery.set("Dresden", 6.0);
delivery.set("Leipzig", 5.8);


for (const [city, price] of delivery) {
  console.log(`${city}: ${price.toFixed(2)} €`);
}
Ausgabe
Berlin: 4.50 €
Hamburg: 5.20 €
Bremen: 6.00 €
Dresden: 6.00 €
Leipzig: 5.80 €

Die Städte kommen in der Reihenfolge heraus, in der sie hinzugefügt wurden. Map behält die Reihenfolge des Hinzufügens, und das ist versprochen. toFixed(2) gibt den Preis mit zwei Stellen aus: Sonst kommt 6.0 als 6 heraus.

Wenn du alphabetische Reihenfolge brauchst, nimm die Schlüssel in ein Array und sortiere es. Die Map ändert sich nicht:

const delivery = new Map();
delivery.set("Berlin", 4.5);
delivery.set("Hamburg", 5.2);
delivery.set("Bremen", 6.0);
delivery.set("Dresden", 6.0);
delivery.set("Leipzig", 5.8);


for (const city of Array.from(delivery.keys()).sort()) {
  console.log(`${city}: ${delivery.get(city).toFixed(2)} €`);
}
Ausgabe
Berlin: 4.50 €
Bremen: 6.00 €
Dresden: 6.00 €
Hamburg: 5.20 €
Leipzig: 5.80 €
Genauer, für Neugierige
  • Wenn du nur die Schlüssel brauchst, durchlaufe keys(). Wenn du nur die Werte brauchst, durchlaufe values():
console.log(Array.from(delivery.keys()).join(" "));


let sum = 0;
for (const price of delivery.values()) {
  sum += price;
}
console.log(`Durchschnitt: ${(sum / delivery.size).toFixed(2)} €`);
Ausgabe
Berlin Hamburg Bremen Dresden Leipzig
Durchschnitt: 5.50 €
  • Array.from(...) macht aus den Schlüsseln ein Array, damit du join und sort hast.
  • Ein einfaches Objekt behält auch die Reihenfolge des Hinzufügens, aber nicht immer: Schlüssel, die wie ganze Zahlen aussehen, kommen zuerst, sortiert wie Zahlen.
const rooms = {};
rooms["Saal"] = "frei";
rooms["12"] = "belegt";
rooms["3"] = "frei";
console.log(Object.keys(rooms));
Ausgabe
[ '3', '12', 'Saal' ]

Die Idee

Zählen

Wie oft wurde jeder Artikel bestellt? Der Schlüssel ist der Artikel, der Wert ist die Anzahl. Bei jeder Bestellung nimmst du die alte Anzahl (oder 0) und addierst 1:

const orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);
Ausgabe
Map(3) { 'Kaffee' => 3, 'Tee' => 2, 'Cola' => 1 }

Das ist die häufigste Verwendung einer Map: Wörter zählen, Stimmen, Fehler nach Art, Verkäufe nach Stadt. Die Artikel kommen in der Reihenfolge heraus, in der sie zum ersten Mal vorkamen. Die Klammern um counts.get(item) ?? 0 sind nötig: Ohne sie wird + 1 vor ?? berechnet, und die Anzahl eines schon gesehenen Artikels wächst nicht.

const orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
const counts = new Map();
for (const item of orders.split(" ")) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}
console.log(counts);
Schritt für Schritt, in Worten
  1. 6 Bestellungen und eine leere Map.
  2. „Kaffee“ ist noch nicht da: get gibt undefined, ?? macht daraus 0, und set fügt den Schlüssel mit 1 hinzu.
  3. „Tee“ ist noch nicht da: get gibt undefined, ?? macht daraus 0, und set fügt den Schlüssel mit 1 hinzu. Eine Map behält die Reihenfolge des Hinzufügens: Der neue Schlüssel kommt ans Ende.
  4. „Kaffee“ ist schon da: get gibt 1, und set ersetzt den Wert durch 2.
  5. „Cola“ ist noch nicht da: get gibt undefined, ?? macht daraus 0, und set fügt den Schlüssel mit 1 hinzu. Eine Map behält die Reihenfolge des Hinzufügens: Der neue Schlüssel kommt ans Ende.
  6. „Kaffee“ ist schon da: get gibt 2, und set ersetzt den Wert durch 3.
  7. „Tee“ ist schon da: get gibt 1, und set ersetzt den Wert durch 2.
  8. Jeder Artikel ist nur einmal ein Schlüssel, und der Wert sagt, wie oft er bestellt wurde.
Genauer, für Neugierige
  • split(" ") aus der Lektion über Strings teilt die Zeile in Wörter.
  • Einen fertigen Zähler hat JavaScript nicht. Die Schreibweise mit get, ?? 0 und set ist der übliche Weg.

Probier es aus

Finde den Fehler

Das Programm soll die Bestellungen zählen. Es bricht nicht ab und zeigt keinen Fehler, aber statt der Anzahlen gibt es das aus:
Ausgabe
Map(2) { 'Kaffee' => NaN, 'Tee' => NaN }

In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Set: jedes nur einmal

Wie viele verschiedene Leute haben sich heute auf der Website angemeldet? Wer sich fünfmal anmeldet, soll nur einmal zählen. Eine Collection, die jeden Wert nur einmal speichert, heißt Set (Menge):

const visits = ["anna@example.com", "jonas@example.com", "anna@example.com", "maria@example.com", "jonas@example.com"];
const visitors = new Set();
for (const email of visits) {
  visitors.add(email);
}
console.log(`Besuche: ${visits.length}`);
console.log(`Verschiedene Besucher: ${visitors.size}`);
console.log(visitors.has("maria@example.com"));
Ausgabe
Besuche: 5
Verschiedene Besucher: 3
true
  • add auf einen Wert, der schon darin ist, macht nichts. In beiden Fällen gibt es das Set selbst zurück, darum sagt es nicht, ob es etwas hinzugefügt hat:
const seen = new Set();
console.log(seen.add("F-101") === seen);
Ausgabe
true
  • has ist so schnell wie has bei einer Map. size ist die Anzahl der Werte.
  • Es gibt keine Indizes. Ein Set beantwortet nur die Frage „Ist es hier drin?“.
Genauer, für Neugierige
  • Ein Set behält die Reihenfolge des Hinzufügens, wie eine Map. Du kannst es auch auf einmal aus einem Array machen, und Array.from macht wieder ein Array daraus, zum Beispiel für sort():
const tags = new Set(["java", "sql", "git", "java"]);
console.log(tags);
console.log(Array.from(tags).sort());


const backend = new Set(["java", "sql", "docker"]);
console.log(tags.intersection(backend));
console.log(tags.union(backend));
Ausgabe
Set(3) { 'java', 'sql', 'git' }
[ 'git', 'java', 'sql' ]
Set(2) { 'java', 'sql' }
Set(4) { 'java', 'sql', 'git', 'docker' }
  • intersection behält nur die Elemente, die zwei Sets gemeinsam haben, und union vereinigt sie. Du brauchst sie in der Übung. Sie sind neu: Node hat sie seit Version 22, die Browser seit 2024.

Probier es aus

Eine doppelte Rechnung

Die Buchhalterin will die Rechnungsnummern sehen, die zweimal eingegeben wurden. Welche Methode fragt, ob die Nummer schon im Set ist?
const invoices = ["F-101", "F-102", "F-101", "F-103"];
const seen = new Set();
for (const number of invoices) {
  if (seen.(number)) {
    console.log(`Doppelte Rechnung: ${number}`);
  }
  seen.add(number);
}

Übung

Maps im Einsatz

Löse die Aufgaben in deinem Editor.

1. Eine Benutzertabelle. Eine Klasse UserTable mit den Methoden add(username, email), get(username) und size(). Innen ist sie eine Map. Füge mueller, mschmidt und weber mit E-Mails der Form mueller@example.com hinzu und suche mschmidt und niemand. In der nächsten Lektion baust du auch deine eigene Hashtabelle, ohne Map.

Ausgabe
mschmidt: mschmidt@example.com
niemand: unbekannter Benutzer
Benutzer: 3

2. Worthäufigkeit. Lies eine Zeile Text ein, schreib sie klein und zähle jedes Wort. Gib die Wörter in alphabetischer Reihenfolge aus.

Eingabe
Kaffee mit Milch und Kaffee ohne Zucker und Kaffee
Ausgabe
kaffee: 3
milch: 1
mit: 1
ohne: 1
und: 2
zucker: 1

3. Dokumente nach Stichwort. Eine Klasse DocumentIndex mit den Methoden addDocument(id, ...keywords) und search(keyword), die ein Array mit den Nummern der Dokumente mit diesem Wort zurückgibt. Innen ist sie eine Map aus Arrays: für jedes Wort ein Array von Dokumenten. Füge Dokument 1 mit „OOP“ und „Java“ hinzu, Dokument 2 mit „SQL“ und „Datenbanken“ und Dokument 3 mit „Java“ und „Collections“. Suche nach „Java“, „SQL“ und „Python“ und gib die Nummern in [] aus, durch Kommas getrennt.

Ausgabe
Java: [1, 3]
SQL: [2]
Python: []

4. Ein Kontaktnetz. Eine Klasse Contact mit Name und E-Mail und eine Klasse ContactNetwork mit den Methoden addContact(name, email), addConnection(a, b) (die Verbindung gilt in beide Richtungen), friendsOf(name), common(a, b) (gemeinsame Freunde) und emailOf(name). Speichere die Kontakte in einer Map Name → Contact und die Verbindungen in einer Map Name → Set von Namen. friendsOf und common geben ein sortiertes Array zurück. Verbinde Jonas mit Maria und Jonas mit Peter.

Ausgabe
Jonas: [Maria, Peter]
Maria: [Jonas]
Gemeinsame Freunde von Maria und Peter: [Jonas]
E-Mail von Peter: peter@example.com

Weitere Aufgaben

  • Eine eindeutige ID. Eine Funktion generateUserId(email) gibt jeder neuen E-Mail eine Nummer, U001, U002 und so weiter, und für eine schon gesehene E-Mail gibt sie dieselbe Nummer zurück. Groß- und Kleinbuchstaben in der E-Mail gelten als gleich. Eine Variante mit einer Hashfunktion gibt es in der nächsten Lektion.
  • Ein Buchkatalog. Der Schlüssel ist die ISBN, zum Beispiel 978-3-16-148410-0, und der Wert ist der Titel. Füge Bücher hinzu, suche eines und gib alle aus, sortiert nach ISBN.
  • Ein Reiseplaner. Speichere für jedes Reiseziel ein Array von Aktivitäten: „Paris“ → „der Eiffelturm“, „der Louvre“. Gib den Plan in der Reihenfolge aus, in der die Reiseziele hinzugefügt wurden. Brauchst du mehr als eine einfache Map?
  • Ein Online-Wörterbuch. Wort → Erklärung. Lies Wörter ein, bis „ende“ kommt. Für ein unbekanntes Wort gib „Dieses Wort gibt es nicht.“ aus.
  • Noten nach Fach. Lies Zeilen wie „Mathe 6“, „Physik 5“, „Mathe 4“ ein und gib die Durchschnittsnote für jedes Fach aus, sortiert nach Namen.

Test

Teste dich

1. Wann ist eine Map besser als ein Array?
2. In der Map menu gibt es schon den Schlüssel "Kaffee" mit dem Wert 2. Was macht menu.set("Kaffee", 3)?
3. Was gibt get für einen Schlüssel zurück, den es nicht gibt?
4. Du gibst eine Map aus. In welcher Reihenfolge kommen die Schlüssel heraus?
5. In einem einfachen Objekt stock schreibst du stock[1] = "Laptop" und danach stock["1"] = "Maus". Wie viele Schlüssel hat stock?
6. Was gibt add auf einem Set zurück, wenn der Wert schon darin ist?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·