ori pei - puzzle online

Filtr Blooma – tablica bitowa stworzona przez Burtona H. Blooma w 1970 roku. Pierwotnie Filtr Blooma był wykorzystywany do implementacji baz danych, obecnie jest bardzo popularny w sieciach komputerowych. Filtr ten jest strukturą prostą i wydajną pamięciowo, która ma na celu reprezentować zadany zbiór elementów. Zastosowanie znajduje w szybkim określaniu przynależności podanych argumentów do tego zbioru elementów. Filtr Blooma ma jedną wadę. Jego wydajność ( oszczędność pamięci) jest możliwa dzięki wprowadzeniu marginesu błędnych pozytywnych odpowiedzi. Efektem tego zabiegu są straty, spowodowane błędnymi informacjami, które często są większe od zaoszczędzonej pamięci.

Implementacja

Filtr Blooma jest tablicą o m-bitach.

Filtr Blooma wykorzystuje k losowych i niezależnych funkcji haszujących, które przyjmują wartość z przedziału [0,m).

Jakość funkcji haszujących oraz parametry m i k określają jakość działania filtru Blooma.