Thema: data-structures
-
Abhängigkeitsreihenfolge per Graphtraversierung: BFS, DFS und topologische Sortierung
Abhängigkeiten als gerichteten Graphen modellieren, mit Breiten- oder Tiefensuche alles finden, was von einer Änderung betroffen ist, und mit Kahns Algorithmus oder DFS-Nachordnung eine Build- oder Migrationsreihenfolge erzeugen, die Zyklen meldet statt sie zu verbergen; graphlib und tsort setzen die Sortierung um.
-
Hashtabellen in der Praxis: Kollisionen, Füllgrad und geseedetes Hashing
Eine Hashtabelle ist im Mittel nur schnell, solange sich Schlüssel gleichmässig über die Buckets verteilen; Kollisionen, der Füllgrad, der ein Rehashing auslöst, und ein pro Prozess geseedeter Hash gegen Hash-Flooding bestimmen ihr tatsächliches Verhalten. Hashwerte nie persistieren und sich nie auf die Iterationsreihenfolge verlassen.
-
Leaderboard-Walkthrough: Score-Events, ein abgeleitetes Sorted Set und rekonstruierbare Ranglisten
Ein Design-Walkthrough für Ranglisten (Leaderboards): serverautoritative Score-Events mit Idempotenzschlüssel als Wahrheitsquelle, je ein Sorted Set pro Board-Periode als abgeleiteter Index für Top-N- und Einzelrang-Abfragen, in den Score codierte Regeln für Gleichstände, nach Ereigniszeitpunkt geroutete Periodengrenzen, und Rebuilds als Routineaufgabe.
-
Tries für Präfix-Lookups: Autovervollständigung und Longest-Prefix-Matching
Ein Trie speichert Strings mit einem Knoten pro gemeinsamem Präfix, sodass die Kosten eines Lookups nur von der Schlüssellänge abhängen, unabhängig davon, wie viele Schlüssel existieren; alle Schlüssel mit einem Präfix bilden einen Teilbaum, und das längste gespeicherte Präfix einer Anfrage lässt sich in einem einzigen Durchlauf finden; für Autovervollständigung und Routing einsetzen, und zuerst mit einem sortierten Array vergleichen.
-
At what share of negative lookups does a Bloom filter in front of a store pay off?
Open question: Bloom filters are recommended for skipping lookups of absent keys, but the break-even depends on the miss share, the false-positive rate, memory, rebuild cost and the price of the lookup saved; which measured thresholds have teams found for databases, caches and object stores?
-
Bloom filters: probabilistic set membership with no false negatives
A Bloom filter answers 'definitely not in the set' or 'probably in the set' with a small bit array and k hash functions; false positives are tunable, false negatives impossible, deletion unsupported. Use it to skip lookups for absent keys, and always verify a positive against the source of truth.
Maschinenlesbar: JSON