Eine Hashtabelle als Zähler
Kurz gesagt: Eine Map als Zähler (HashMap in Java) zählt in einem einzigen Durchgang, wie oft jedes Element vorkommt: O(n) statt O(n²) bei der Suche in einer Liste.
Problem
Die meistverkauften Produkte des Tages
Das Shop-Dashboard zeigt die drei meistverkauften Produkte des Tages. Das Log ist eine Liste von Bestellungen, eine pro Zeile. Der Code führt zwei Listen, die Namen und die Zähler, und sucht für jede Bestellung das Produkt vom Anfang der Namen an:
List<String> log = logOf(1000);List<String> names = new ArrayList<>();List<Integer> counts = new ArrayList<>();long comparisons = 0;for (String item : log) { int i = 0; while (i < names.size()) { comparisons++; if (names.get(i).equals(item)) break; i++; } if (i == names.size()) { names.add(item); counts.add(1); } else { counts.set(i, counts.get(i) + 1); }}System.out.println("Bestellungen: " + log.size());System.out.println("Produkte: " + names.size());System.out.println("Vergleiche: " + comparisons);Bestellungen: 1000Produkte: 251Vergleiche: 125255Tausend Bestellungen und 251 verschiedene Produkte: 125.255 Vergleiche. Der Katalog wächst mit dem Shop, und mit ihm die Liste, die jede Bestellung durchläuft. An einem großen Tag mit 100.000 Bestellungen lädt das Dashboard minutenlang.
Woher das Log kommt
Das Log folgt einer Formel, damit die Programme in allen vier Sprachen und der Vergleich unten im Browser genau dasselbe bauen. Der Katalog hat n / 4 + 1 Produkte:
static List<String> logOf(int n) { int catalog = n / 4 + 1; List<String> log = new ArrayList<>(); for (int i = 0; i < n; i++) { log.add("SKU-" + (i * 7919) % catalog); } return log;}Die Idee
Die Map zählt
In der Lektion „HashMap und HashSet“ hast du Bestellungen mit einer Map gezählt. Hier wird daraus eine Technik: eine Hashtabelle als Zähler (eine Häufigkeitsmap). Der Schlüssel ist, was du zählst, der Wert, wie oft du es gesehen hast.
- Ein Durchgang über die Daten. Für jedes Element: seinen Zähler finden (oder 0) und 1 addieren.
- Das Nachschlagen geschieht in einer Hashtabelle: im Durchschnitt O(1), egal wie viele Produkte es gibt. Insgesamt O(n) statt O(n · m).
- Danach beantwortest du die Fragen aus den Zählern, nicht aus den Daten: welches am häufigsten ist, welches einmal vorkommt, ob zwei Dinge dieselben Zähler haben.
Der Speicher ist O(m): ein Paar für jedes verschiedene Produkt.
Sieh es dir an
Der Zähler füllt sich
List<String> log = List.of( "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset");Map<String, Integer> counts = new HashMap<>();for (String item : log) { counts.merge(item, 1, Integer::sum);}List<Map.Entry<String, Integer>> top = new ArrayList<>(counts.entrySet());top.sort((x, y) -> y.getValue() - x.getValue());for (var e : top.subList(0, 3)) { System.out.println(e.getKey() + " " + e.getValue());}Maus 4Headset 3Monitor 2Map<String, Integer> counts = new HashMap<>();for (String item : log) { counts.merge(item, 1, Integer::sum);}List<Map.Entry<String, Integer>> top = new ArrayList<>(counts.entrySet());top.sort((x, y) -> y.getValue() - x.getValue());for (var e : top.subList(0, 3)) { System.out.println(e.getKey() + " " + e.getValue());}Schritt für Schritt, in Worten
- Eine leere Map: Produkt → wie oft es verkauft wurde. Das Log hat 10 Bestellungen.
- Bestellung 1: Maus. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 2: Headset. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 3: Maus, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 4: Monitor. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 5: Tastatur. Es ist noch nicht in der Map, also bekommt es den Zähler 1.
- Bestellung 6: Maus, 2 → 3. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 7: Headset, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 8: Monitor, 1 → 2. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 9: Maus, 3 → 4. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- Bestellung 10: Headset, 2 → 3. Ein Nachschlagen in der Hashtabelle, ohne die anderen Produkte zu durchlaufen.
- 10 Bestellungen, 10 Zähleraktualisierungen. Sortiert werden nur die 4 verschiedenen Produkte nach Zähler, nicht die Bestellungen.
- Die Top drei: Maus 4, Headset 3, Monitor 2.
merge(item, 1, Integer::sum) setzt 1, wenn der Schlüssel nicht da ist, und addiert sonst 1 zum alten Zähler. Die Top drei entstehen durch Sortieren der Paare nach Zähler: Sortiert werden nur die verschiedenen Produkte, nicht die Bestellungen.
Probier es aus
Ergänze
Die Zeile, die zählt:
counts.merge(item, 1, );merge bekommt, wie der alte Zähler mit dem neuen zu verbinden ist: Integer::sum.Sieh es dir an
Die Werkzeuge deiner Sprache
In Java ist der Zähler eine HashMap<String, Integer>. getOrDefault mit put macht dasselbe wie merge, schlägt den Schlüssel aber zweimal nach. merge schlägt ihn einmal nach. Brauchst du die Schlüssel sortiert, zählt Collectors.groupingBy mit einer TreeMap und Collectors.counting() in einem Stream:
List<String> log = List.of( "Maus", "Headset", "Maus", "Monitor", "Tastatur", "Maus", "Headset", "Monitor", "Maus", "Headset");Map<String, Integer> counts = new HashMap<>();for (String item : log) { counts.put(item, counts.getOrDefault(item, 0) + 1);}System.out.println(counts.get("Maus") + " " + counts.getOrDefault("Tablet", 0));Map<String, Long> sorted = log.stream() .collect(Collectors.groupingBy(item -> item, TreeMap::new, Collectors.counting()));System.out.println(sorted);4 0{Headset=3, Maus=4, Monitor=2, Tastatur=1}Sieh es dir an
Miss es: eine Liste von Paaren gegen eine Map
Dieselben tausend Bestellungen mit der Map:
List<String> log = logOf(1000);Map<String, Integer> counts = new HashMap<>();long updates = 0;for (String item : log) { counts.merge(item, 1, Integer::sum); updates++;}System.out.println("Bestellungen: " + log.size());System.out.println("Produkte: " + counts.size());System.out.println("Zähleraktualisierungen: " + updates);Bestellungen: 1000Produkte: 251Zähleraktualisierungen: 10001.000 Aktualisierungen statt 125.255 Vergleiche. Lass beide im Browser laufen. n ist die Zahl der Bestellungen, und der Katalog wächst mit:
- Eine Liste von Paaren aus Produkt und Anzahl
O(n²) - Eine Map als Zähler
O(n)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 |
|---|---|---|---|
| Eine Liste von Paaren aus Produkt und Anzahl | 16 | 125.255 | ≈ 1.252.550.000 |
| Eine Map als Zähler | 10 | 1.000 | 100.000 |
Map<String, Integer> counts = new HashMap<>();for (String item : log) { counts.merge(item, 1, Integer::sum);}List<Map.Entry<String, Integer>> top = new ArrayList<>(counts.entrySet());top.sort((x, y) -> y.getValue() - x.getValue());for (var e : top.subList(0, 3)) { System.out.println(e.getKey() + " " + e.getValue());}Genauer, für Neugierige
Die Top k ohne alles zu sortieren. Das Sortieren von m verschiedenen Produkten ist O(m log m). Gibt es Millionen von Produkten und du brauchst die Top 10, behältst du einen Heap mit höchstens k Paaren: Jedes Paar kommt hinein, und bei k + 1 Paaren geht das kleinste hinaus. Das ist O(m log k).
Ein Schlüssel aus mehreren Teilen. Du zählst Verkäufe nach Stadt und Produkt: Der Schlüssel ist das Paar. In Java ist es ein record CityItem(String city, String item): Ein Record hat equals und hashCode über seine Felder.
Die Idee
Der Warenkorb und das Set
Das Set „Homeoffice“ besteht aus einem Monitor, einer Tastatur, einer Maus und zwei Kabeln. Das Lager prüft, dass der Warenkorb, der verschickt werden soll, genau das Set ist: nichts zu viel, nichts zu wenig. Die Reihenfolge ist egal, die Zähler nicht.
Ein Zähler: +1 für jedes Produkt des Sets, −1 für jedes Produkt im Warenkorb. Der Warenkorb passt, wenn alle Zähler am Ende 0 sind.
static boolean matches(List<String> kit, List<String> basket) { Map<String, Integer> need = new HashMap<>(); for (String item : kit) need.merge(item, 1, Integer::sum); for (String item : basket) need.merge(item, -1, Integer::sum); for (int n : need.values()) { if (n != 0) return false; } return true;}Dieselbe Prüfung findet Anagramme: „listen“ und „silent“ haben dieselben Buchstaben mit denselben Zählern. Der Zähler läuft über Buchstaben statt über Produkte.
Probier es aus
Sag die Prüfung voraus
List<String> kit = List.of( "Monitor", "Tastatur", "Maus", "Kabel", "Kabel");List<String> basket1 = List.of( "Kabel", "Maus", "Monitor", "Kabel", "Tastatur");List<String> basket2 = List.of( "Monitor", "Tastatur", "Maus", "Maus", "Kabel");System.out.println("Warenkorb 1: " + (matches(kit, basket1) ? "vollständiges Set" : "passt nicht"));System.out.println("Warenkorb 2: " + (matches(kit, basket2) ? "vollständiges Set" : "passt nicht"));Der erste Warenkorb hat dieselben fünf Produkte in anderer Reihenfolge: Jeder Zähler wird 0. Der zweite hat zwei Mäuse und ein Kabel: Die Maus bleibt bei −1, das Kabel bei +1, also passt er nicht, obwohl es fünf Produkte sind.
Die Idee
Der erste Kunde mit einer einzigen Bestellung
Das Marketing schickt einen „Komm zurück“-Gutschein an die Kunden, die nur einmal bestellt haben. Es will den zeitlich ersten. Der Zähler liefert die Zähler, aber nicht die Reihenfolge:
static String firstSingle(List<String> customers) { Map<String, Integer> counts = new HashMap<>(); for (String c : customers) counts.merge(c, 1, Integer::sum); for (String c : customers) { if (counts.get(c) == 1) return c; } return null;}List<String> customers = List.of( "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30");System.out.println("erster Kunde mit einer Bestellung: " + firstSingle(customers));erster Kunde mit einer Bestellung: C-21Zwei Durchgänge: Der erste zählt, der zweite läuft durch das Log, in der Reihenfolge der Bestellungen, und hält beim ersten mit Zähler 1 an. O(n), ohne verschachtelte Schleife.
Genauer, für Neugierige
Warum läuft der zweite Durchgang durch das Log und nicht durch die Map? Eine HashMap behält gar keine Reihenfolge: Das Durchlaufen geht Bucket für Bucket. Eine LinkedHashMap behält die Reihenfolge des Einfügens, und dann funktioniert auch das Durchlaufen der Map.
Die Idee
Zwei Produkte für genau 50 €
Der Kunde hat einen Gutschein über genau 50 € und will zwei Produkte, die ihn aufbrauchen. Die Preise im Katalog sind nicht sortiert.
Du gehst die Preise durch und fragst bei jedem: Habe ich den Preis, der diesen auf 50 auffüllt, schon gesehen? Die Map behält die bisher gesehenen Preise und ihre Positionen:
static int[] voucherPair(int[] prices, int voucher) { Map<Integer, Integer> seen = new HashMap<>(); for (int i = 0; i < prices.length; i++) { Integer j = seen.get(voucher - prices[i]); if (j != null) return new int[] { j, i }; seen.put(prices[i], i); } return null;}int[] prices = { 27, 14, 33, 25, 8, 36, 19 };int[] p = voucherPair(prices, 50);System.out.println("Produkte " + p[0] + " und " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");Produkte 1 und 5: 14 € + 36 €Ein Durchgang: O(n) Zeit und O(n) Speicher. Mit zwei Zeigern geht es ohne Map, mit O(1) Speicher, aber die Preise müssen sortiert sein. Sind sie es nicht, kostet das Sortieren O(n log n) und die Position jedes Produkts im Katalog geht verloren. Also: sortierte Daten, zwei Zeiger; unsortierte Daten, eine Map.
Probier es aus
Finde den Fehler
Jemand hat zwei Zeilen vertauscht. Jetzt bietet das Programm für einen Gutschein über 50 € ein Produkt zweimal an:
int[] prices = { 27, 14, 33, 25, 8, 36, 19 };int[] p = voucherPair(prices, 50);System.out.println("Produkte " + p[0] + " und " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");Produkte 3 und 3: 25 € + 25 €Wähle die Zeile mit dem Fehler.
Der Preis kommt in die Map, bevor sein Partner nachgeschlagen wird. Das Produkt für 25 € sucht 50 − 25 = 25 und findet sich selbst. Das Schreiben muss nach dem Nachschlagen kommen: Dann enthält die Map nur die Produkte vor dem aktuellen, und das Programm findet 14 € + 36 €.
Übung
Wer gibt am meisten aus
Löse die Aufgabe in deinem eigenen Editor.
Umsatz pro Kunde. Das Log hat Paare aus Kunde und Betrag: C-4 mit 30 €, C-17 mit 55 €, C-4 mit 20 €, C-9 mit 80 €, C-17 mit 10 € und C-4 mit 45 €. Addiere die Beträge pro Kunde mit einer Map (der Wert ist eine Summe, kein Zähler) und gib die zwei aus, die am meisten ausgegeben haben:
C-4: 95 €C-9: 80 €Weitere Aufgaben
- Anagramme. Schreibe eine Prüfung, ob zwei Wörter Anagramme sind („listen“ und „silent“), indem du die Buchstaben mit einer Map zählst. Wie viele Operationen braucht sie bei Wörtern der Länge n?
- Die erste Wiederholung. Finde die erste Bestellung, deren Kunde schon früher bestellt hat. Brauchst du einen Zähler, oder genügt ein Set?
- Zeiträume mit gleichen Zählern. Aus den Präfixsummen weißt du, wie man Zeiträume mit gegebener Summe zählt. Zähle die Zeiträume aufeinanderfolgender Tage, in denen die Zahl der zurückgeschickten Bestellungen der Zahl der gelieferten entspricht.
Test