Elementen Toegevoegd aan Bloom-filters - dummies

In het algemeen maak je Bloom-filters voor algoritmen van een vaste grootte (recent ontwikkelde versies kun je het formaat wijzigen van filter) U bedient ze door nieuwe elementen toe te voegen aan het filter en ze op te zoeken als ze al aanwezig zijn. Het is niet mogelijk om een ​​element uit het filter te verwijderen nadat het is toegevoegd (het filter heeft een onuitwisbaar geheugen).

Bij het toevoegen van een element naar een bitvector heeft de bitvector enkele bits ingesteld op 1, zoals weergegeven.In dit geval voegt het Bloom-filter X toe aan de bitvector.

Een enkel element toevoegen naar een bitvector.

U kunt zoveel elementen toevoegen als nodig is voor de bitvector. In de volgende afbeelding ziet u bijvoorbeeld wat er gebeurt wanneer u een ander element, Y, aan de bitvector toevoegt. voor zowel X als Y. Bijgevolg representeert bit 7 een botsing tussen X en Y. Deze botsingen zijn de bron van de potentiële valse positieven; vanwege hen zou het algoritme kunnen zeggen dat een element al aan de bitvector is toegevoegd, terwijl dat niet het geval is. Het gebruik van een grotere bitvector maakt botsingen minder waarschijnlijk en verbetert de prestaties van het Bloom-filter, maar dit gaat ten koste van zowel ruimte als tijd.

Het toevoegen van een tweede element kan botsingen veroorzaken.