Bloomfiltre Ved Eksempel

Et Bloomfilter er en hukommelseseffektiv probabilistisk datastruktur til hurtigt at tjekke medlemskab.

Bloomfiltre kan med sikkerhed afgøre fravær af et element, men kun indikere mulig tilstedeværelse.

Datastrukturen bruger en bitvektor, hvor bit sættes til 1 med flere hashfunktioner ved indsættelse.

Ved medlemskabstest hashes elementet med de samme funktioner og tjekker, om alle relevante bits er sat.

Flere hashfunktioner reducerer falske positiver men øger beregningstid og fylder hurtigere filteret.

Optimal værdi for antal hashfunktioner beregnes som k=(m/n)ln(2) for at minimere fejlrate.

Både indsættelse og forespørgsel har køretid O(k).

Hurtige, uafhængige og jævnt fordelte hashfunktioner som murmur, xxHash og fnv forbedrer ydeevnen.