Filtr Blooma na przykładach

Filtr Blooma to probabilistyczna struktura danych pozwalająca szybko i pamięciooszczędnie sprawdzać przynależność elementu do zbioru.

Wewnętrznie wykorzystuje wektor bitowy oraz k niezależnych i szybko działających funkcji hashujących, które ustawiają bity na pozycjach określonych przez wartości hashy.

Przy dodawaniu elementu hashuje się go k razy i ustawia odpowiadające bity na 1, a przy sprawdzaniu przynależności weryfikuje się, czy te same bity są ustawione.

Brak któregokolwiek bitu gwarantuje, że element nie należy do zbioru, natomiast obecność wszystkich bitów oznacza jedynie możliwość przynależności ze względu na fałszywe trafienia.

Współczynnik fałszywych trafień wynosi w przybliżeniu (1–e^(–k·n/m))^k i zależy od liczby bitów m, liczby hashów k i liczby elementów n.

Optymalną liczbę funkcji hashujących wyznacza wzór k = (m/n)·ln(2), co umożliwia minimalizację wskaźnika fałszywych trafień.

Operacje dodawania i sprawdzania przynależności wykonują się w czasie O(k).

W praktyce zaleca się używanie szybkich, niekryptograficznych hashy, np. Murmur, xxHash lub FNV.