Ile funkcji mieszania wymaga mój filtr kwitnienia?

Question

Wikipedia mówi:

Pusta filtr Bloom jest tablicą nieco bitów m, ustawiony na 0. Nie może być również k różne funkcje hash zdefiniowane, z których każdy mapy lub skróty pewien zbiór elementów do jednego z pozycje m tablicy z jednolitym rozkładem losowym.

Przeczytałem artykuł, ale nie rozumiem, w jaki sposób k jest określony. Czy jest to funkcja rozmiaru stołu?

Ponadto w tablicach hashowych napisałem, że użyłem prostego, ale efektywnego algorytmu automatycznego zwiększania rozmiaru hasza. Zasadniczo, jeśli zostało wypełnione więcej niż 50% kubełków w tabeli, podwoiłbym rozmiar stołu. Podejrzewam, że nadal możesz chcieć to zrobić z filtrem bloom, aby zmniejszyć liczbę fałszywych alarmów. Poprawny?

Answer 1

Jeśli przeczytacie w dalszej części Wikipedia article about Bloom filters, a następnie znaleźć sekcja Prawdopodobieństwo fałszywych alarmów. W tej sekcji wyjaśniono, w jaki sposób liczba funkcji skrótu wpływa na prawdopodobieństwo fałszywych trafień i podaje formułę do określenia wartości k z żądanego oczekiwanego prob. fałszywych alarmów.

---

żądanie z Wikipedia:

Oczywiście, prawdopodobieństwo fałszywych alarmów zmniejsza się o (numer bitów w tablicy) zwiększa się, a zwiększa się n (liczba wstawionych elementów ) wzrasta. Dla danego mi n, wartość k (liczba hash funkcji), która minimalizuje prawdopodobieństwo jest

Answer 2

I mieć to określone w zadbanej stoliku:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

Answer 3

Dane:

• n: Ile elementów oczekujesz w filtrze (np. 216,553)
• p: akceptowalna liczba fałszywych trafień {0..1} (np.0.01 → 1%)

chcemy obliczyć:

• m: liczba bitów potrzebnych w filtrze rozkwicie
• k: liczba funkcji skrótu powinniśmy zastosować

Formuły:

m = -n*ln(p)/(ln(2)^2)liczba bitów
k = m/n * ln(2)liczba funkcji mieszających

W naszym przypadku

• m = -216553*ln(0.01)/(ln(2)^2) = 997263/0.48045 = 2,075,686 bitów (253 kB)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 funkcje skrótu (hash) 7 funkcji

Note: każdy kod wydany w domenie publicznej. Atrybucja nie jest wymagana.