Brakuje sposobu, w jaki dwie struktury danych radzą sobie z kolizjami mieszania. Filtry Bloom nie przechowują rzeczywistych wartości, więc wymagana przestrzeń to stały rozmiar wyznaczonej tablicy. Zamiast tego, jeśli używasz tradycyjnego skrótu, próbuje on zapisać wszystkie podane wartości, więc rośnie z czasem.
Rozważ uproszczoną funkcję skrótu (tylko dla przykładu!) f(x) = x % 2. Teraz możesz wejść następujące liczby całkowite: 2, 3, 4, 5, 6, 7.
Standardowy skrót: podane wartości zostaną zaszyfrowane, a my skończymy z wieloma kolizjami z powodu f(2) = f(4) = f(6) = 0i f(3) = f(5) = f(7) = 1. Niemniej jednak skrót przechowuje wszystkie te wartości i będzie mógł powiedzieć, że 8nie jest w nim przechowywany. Jak to robi? Śledzi kolizje i przechowuje wszystkie wartości o tej samej wartości skrótu, a następnie, gdy je wywołujesz, dodatkowo porównuje zapytanie. Zapytajmy więc mapę o 8:, f(8) = 0więc przejdzie do wiadra, w którym już wstawiliśmy, 2, 4, 6i musi dokonać 3 porównań, aby powiedzieć, że 8nie było częścią danych wejściowych.
Filtr Bloom: Zwykle każda wartość wejściowa jest mieszana z króżnymi funkcjami skrótu. Ponownie, dla uproszczenia, załóżmy, że używamy tylko pojedynczej funkcji skrótu f. Potrzebujemy wtedy tablicy 2 wartości, a kiedy napotkamy dane wejściowe 2, oznacza to, że z powodu f(2) = 0ustawienia wartości tablicy w pozycji 0na wartość 1. To samo dzieje się w przypadku 4i 6. Podobnie 3, 5, 7każdy z wejść ustawia pozycję tablicy 1na wartość 1. Teraz pytamy, czy 8był częścią danych wejściowych: f(8) = 0a tablica w pozycji 0jest 1, więc filtr Bloom będzie fałszywie twierdził, że 8rzeczywiście był częścią danych wejściowych.
Aby uzyskać nieco bardziej realistyczny charakter, zastanówmy się nad dodaniem drugiej funkcji skrótu g(x) = x % 10. Dzięki temu wartość wejściowa 2prowadzi do dwóch wartości skrótu, f(2) = 0a g(2) = 2dwie odpowiadające pozycje tablicy zostaną ustawione na 1. Oczywiście tablica powinna mieć teraz przynajmniej rozmiar 10. Ale kiedy zapytamy o 8, sprawdzimy tablicę w pozycji z 8powodu g(8) = 8, i ta pozycja nadal będzie 0. Dlatego dodatkowe funkcje skrótu zmniejszają liczbę fałszywych alarmów.
Porównanie: Filtr Bloom używa kfunkcji skrótu, co oznacza, kże można uzyskać dostęp do losowych pozycji tablicy. Ale ta liczba jest dokładna. Zamiast tego hash gwarantuje ci tylko stały, zamortyzowany czas dostępu, ale może de-generować w zależności od charakteru twojej funkcji hash i danych wejściowych. Zwykle jest to szybsze, z wyjątkiem przypadków generowanych od nowa.
Jednak po kolizji skrótu standardowy skrót będzie musiał sprawdzić równość przechowywanych wartości z wartością zapytania. Ta kontrola równości może być dowolnie droga i nigdy nie nastąpi z filtrem Bloom.
Pod względem przestrzeni filtr Bloom jest stały, ponieważ nigdy nie ma potrzeby używania większej ilości pamięci niż wyznaczona tablica. Z drugiej strony, skrót rośnie dynamicznie i może być znacznie większy ze względu na konieczność śledzenia wartości kolizyjnych.
Kompromis: Teraz, gdy wiesz, co jest tanie, a co nie i w jakich okolicznościach, powinieneś być w stanie zobaczyć kompromis. Filtry Bloom są świetne, jeśli chcesz bardzo szybko wykryć, że wartość została wcześniej zauważona, ale może żyć z fałszywymi pozytywami. Z drugiej strony możesz wybrać mapę haszowania, jeśli chcesz zagwarantować poprawność za cenę niemożności dokładnego oszacowania czasu działania, ale możesz zaakceptować przypadki zdegenerowane zdegenerowane, które mogą być znacznie wolniejsze niż średnia.
Podobnie, jeśli masz ograniczone środowisko pamięci, możesz preferować filtry Bloom ze względu na gwarancję wykorzystania pamięci.