Hashing & Sets
Die O(1)-Suche hinter den meisten schnellen Lösungen.
Hashing macht aus einer großen Klasse von O(n^2)-Problemen O(n): Zählen, Gruppieren, Deduplizieren und der Komplement-Trick. Verstehe, wie eine Hash-Map intern arbeitet, und nutze sie, um etwas Echtes zu bauen - einen LRU-Cache.
Lektionen in dieser Stufe
- 01
Wie Hashing funktioniert
FortgeschrittenHash-Funktionen, Buckets, Kollisionen und warum HashMap-Operationen im Schnitt O(1), im schlimmsten Fall aber O(n) sind.
15 Min. - 02
Zählen & Häufigkeit
FortgeschrittenHäufigkeitskarten lösen erstaunlich viele Probleme - erstes eindeutiges Element, Mehrheitselement, Top-k - in einem einzigen Durchlauf.
13 Min. - 03
Gruppieren & Deduplizieren
FortgeschrittenMap<K, List<V>>, um nach einem berechneten Schlüssel zu gruppieren, und Sets, um in O(1) zu deduplizieren oder 'schon gesehen' zu erkennen.
13 Min. - 04
Der Komplement-Trick
FortgeschrittenDas häufigste Hashing-Muster: merke dir, was du gesehen hast, sodass der Partner jedes Elements nur eine O(1)-Suche entfernt ist.
12 Min. - 05
Einen LRU-Cache entwerfen
ExperteEine klassische Design-Frage: kombiniere eine Hash-Map mit einer doppelt verketteten Liste für O(1)-get und -put mit LRU-Verdrängung.
16 Min.