Datenstrukturdienstag: Eine meiner lieblings-Strukturen, der Bloom-Filter.
Eine wichtige Eigenschaft eines Bloom-Filters ist die False-Positive-Rate. Das ist die Wahrscheinlichkeit für False-Positives. Zu dieser Wahrscheinlichkeit gab es 30 Jahre später noch eine neue Formel, da die ursprüngliche wohl fehlerhaft war. Hier ist ein Writeup dazu[hinweis]. Hier ist noch ein Paper dazu.
Was man in der Praxis für Probleme mit einem Bloom-Filter haben kann, hat Cloudflare mal aufgeschrieben.