Quante funzioni hash ha bisogno del mio filtro bloom?

Question

Wikipedia dice:

Un filtro Bloom vuoto è una matrice di bit di m bit, pronto a 0. Non ci deve essere k diverse funzioni di hash definite, ciascuna delle quali mappe o hash qualche elemento insieme ad una delle la matrice m si posiziona con una distribuzione casuale uniforme.

Ho letto l'articolo, ma quello che non capisco è come k è determinato. È una funzione delle dimensioni del tavolo?

Inoltre, nelle tabelle hash che ho scritto ho utilizzato un algoritmo semplice ma efficace per aumentare automaticamente le dimensioni dell'hash. Fondamentalmente, se mai più del 50% dei bucket nella tabella fosse riempito, raddopperei le dimensioni del tavolo. Ho il sospetto che potresti ancora voler fare questo con un filtro di fioritura per ridurre i falsi positivi. Corretta?

Answer 1

Se si legge più avanti nello Wikipedia article about Bloom filters, si trova una sezione Probabilità di falsi positivi. Questa sezione spiega in che modo il numero di funzioni hash influenza le probabilità di falsi positivi e fornisce la formula per determinare dal valore atteso desiderato. di falsi positivi.

---

citazione dall'articolo Wikipedia:

Ovviamente, la probabilità di falsi positivi diminuisce m (il numero di bit della matrice) aumenta, e aumenta con n (il numero degli elementi inseriti ) aumenta. Per un dato m ed n, il valore di k (il numero di hash funzioni) che riduce al minimo la probabilità è

Answer 2

E di averlo disposto in un piccolo tavolo pulito:

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

Answer 3

Dato:

• n: quanti elementi ci si aspetta di avere nel filtro (ad es. 216,553)
• p: il tuo tasso di falsi positivi accettabile {0..1} (ad es.0.01 → 1%)

vogliamo calcolare:

• m
  : il numero di bit necessari nel filtro fioritura
• k: il numero di funzioni hash dovremmo applicare

Le formule:

m = -n*ln(p)/(ln(2)^2)il numero di bit
k = m/n * ln(2)il numero di funzioni hash

Nel nostro caso:

• m = -216553*ln(0.01)/(ln(2)^2) = 997263/0.48045 = 2,075,686 bit (253 kB)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 funzioni di hash (7 funzioni di hash)

Nota: Qualsiasi codice rilasciato nel pubblico dominio. Nessuna attribuzione richiesta.