Anzeige
Anzeige
Anzeige
Anzeige
Anzeige
Anzeige
Lesedauer 3 Min.

Ein Beispiel zu Bloom-Filtern

Ein Bloom-Filter ist eine Datenstruktur, die entwickelt wurde, um schnell und speichereffizient zu prüfen, ob ein Element in einem Set vorhanden ist.
Der Preis für seine Effizienz ist, dass ein Bloom-Filter eine probabilistische Datenstruktur ist: Er sagt uns, dass das Element entweder definitiv nicht im Set ist oder sich im Set befinden kann. Basisdatenstruktur eines Bloom-Filters ist ein Bitvektor. Stellen Sie sich für ein Beispiel ein leeres Array mit 15 Elementen vor (Index: 0 bis 14) – siehe Bild. Jede leere Zelle in diesem Array hat einen Index und repräsentiert ein Bit. Um ein Element zum Bloom-Filter hinzuzufügen, hashen wir es einfach ein paar Mal und setzen die Bits im Bitvektor auf den Index dieser Hashes auf 1. Es ist einfacher zu sehen, was das bedeutet, als es zu erklären. Im abgebildeten Beispiel 1 wurde der String "dotnetpro" eingegeben. Im Bitvektor wurden durch die einfachen Hash-Funktionen Fnv und Murmur die Indizes 11 und 14 mit einer 1 belegt. In Beispiel 2 wurden drei weitere Strings hinzugefügt.Um die Mitgliedschaft zu testen, werden die abzufragenden Zeichenketten mit den gleichen Hash-Funktionen bearbeitet und geprüft, ob diese Werte im Bitvektor gesetzt sind. Sind sie nicht gesetzt, wissen Sie, dass das Element nicht in der Menge ist (Abfrage 2). Sind sie gesetzt (Abfragen 1 und 3), dann wissen Sie nur, dass das Element enthalten sein könnte (maybe!), denn ein anderes Element oder eine Kombination von anderen Elementen könnte die gleichen Bits gesetzt haben (Abfrage 3).Die in einem Bloom-Filter verwendeten Hash-Funktionen sollten unabhängig und gleichmäßig verteilt sein. Sie sollten auch so schnell wie möglich sein (kryptographische Hashes wie sha1sind daher keine gute Wahl). Beispiele für schnelle, einfache Hashes, die unabhängig genug sind, sind murmur, die fnv-Serie von Hashes und HashMix.Mehr über Bloom-Filter erfahren Sie im Bloom-Filter-Tutorial von Entwickler Bernardo Sulzbach (auch auf GitHub), in diesem Beitrag von C. Titus Brown sowie auf Wikipedia.

Neueste Beiträge

Managed DevOps Pools - Azure DevOps Pipelines Security
Agent Pools als Managed Service mit einfacher Integration in private Netzwerke und Authentisierung mittels Managed Identity tragen deutlich zur Sicherheit der Agent-Infrastruktur bei.
7 Minuten
7. Aug 2025
Müssen Ziele SMART sein?
Wenn es um Ziele im Projektmanagement oder in der Führung einer Organisation geht, stoßen wir schnell und fast ausnahmslos auf das Akronym SMART. Was steckt dahinter, und kann es nicht auch sinnvolle Ziele geben, die nicht SMART sind?
8 Minuten
Browser-Apps mit Avalonia entwickeln - Avalonia
Klassische UI-Frameworks finden ihren Weg in den Browser
7 Minuten
11. Aug 2025
Miscellaneous

Das könnte Dich auch interessieren

Sicher ist sicher - Azure DevOps Pipelines Security
Als integraler Bestandteil der Entwicklungsumgebung ist Azure DevOps Pipelines oft Ziel von Angriffen. Da ist es gut zu wissen, wo die Schwachstellen des Systems liegen.
14 Minuten
16. Jun 2025
CodeProject.AI Server in neuer Version - Lokaler AI-Server
CodeProject.AI Server (jetzt in Version 2.1.10) ist ein lokal installierter, selbstgehosteter, schneller, kostenloser und Open Source Artificial Intelligence Server für jede Plattform und jede Sprache.
2 Minuten
Für Einsteiger: Backend-Webentwicklung mit .NET - Microsoft
Auf YouTube bietet Microsoft eine Videoserie für Einsteiger in die Backend-Webentwicklung mit .NET.
2 Minuten
13. Feb 2024
Anzeige
Anzeige
Anzeige
Anzeige
Anzeige