I filtri Bloom sembrano davvero grandi se si considera che è possibile determinare se un Int si trova in un set con una certezza del 99% in un tempo costante. Ma lo stesso vale per gli hash, con la sola differenza che, in un hash, la maggior parte delle volte si accede alla memoria solo una volta. Con i filtri di fioritura, devi accedervi ~ 7 volte per ogni richiesta in luoghi completamente distanti , quindi avrai diversi errori di cache per richiesta.
Mi manca qualcosa?
Manca il modo in cui le due strutture dati gestiscono le collisioni di hash. I filtri di fioritura non memorizzano i valori effettivi, quindi lo spazio richiesto è la dimensione costante dell'array designato. Invece, se usi un hash tradizionale, prova a memorizzare tutti i valori che gli vengono assegnati, quindi aumenta con il tempo.
Considera una funzione di hash semplificata (solo per un esempio!) f(x) = x % 2 . Ora inserisci i seguenti numeri interi: 2, 3, 4, 5, 6, 7 .
Hash standard: i valori dati verranno sottoposti a hash e finiremo con un sacco di collisioni a causa di f(2) = f(4) = f(6) = 0 e f(3) = f(5) = f(7) = 1 . Tuttavia, l'hash memorizza tutti questi valori e sarà in grado di dirti che 8 non è memorizzato in esso. Come lo fa? Tiene traccia delle collisioni e memorizza tutti i valori con lo stesso valore di hash, quindi quando lo interroghi, confronta ulteriormente la tua query. Quindi interrogiamo la mappa per 8 : f(8) = 0 , quindi esamineremo un bucket in cui abbiamo già inserito 2, 4, 6 e dobbiamo effettuare 3 confronti per dirvi che 8 non faceva parte del ingresso.
Filtro Bloom: normalmente, ogni valore di input viene sottoposto a hash rispetto a k diverse funzioni hash. Di nuovo, per semplicità, supponiamo di utilizzare solo la funzione hash singola f . Abbiamo bisogno di un array di 2 valori e quando incontriamo l'input 2 significa che a causa di f(2) = 0 impostiamo il valore dell'array alla posizione 0 sul valore 1 . Lo stesso accade per 4 e 6 . Allo stesso modo, gli input 3, 5, 7 ciascuno impostano la posizione dell'array 1 sul valore 1 . Ora interrogiamo se 8 era parte dell'input: f(8) = 0 e l'array alla posizione 0 è 1 , quindi il filtro di fioritura dichiarerà falsamente che 8 era effettivamente parte dell'input.
Per essere un po 'più realistici, consideriamo che aggiungiamo una seconda funzione di hash g(x) = x % 10 . Con questo, il valore di input 2 porta a due valori hash f(2) = 0 e g(2) = 2 e le due posizioni dell'array corrispondenti saranno impostate su 1 . Ovviamente, la matrice ora dovrebbe essere almeno della dimensione 10 . Ma quando chiediamo 8 verificheremo la matrice alla posizione 8 a causa di g(8) = 8 , e quella posizione sarà ancora 0 . Ecco perché ulteriori funzioni hash diminuiscono i falsi positivi che otterrai.
Confronto: il filtro bloom usa% hash dik che significa fino a k posizioni dell'array casuale a cui si accede. Ma quella cifra è esatta. L'hash invece ti garantisce solo un tempo di accesso costante ammortizzato, ma può de-generare a seconda della natura della tua funzione hash e dei dati di input. Quindi è in genere più veloce, ad eccezione dei casi de-generati.
Tuttavia, una volta che si verifica una collisione hash, l'hash standard dovrà controllare l'uguaglianza dei valori memorizzati rispetto al valore della query. Questo controllo di uguaglianza può essere arbitrariamente costoso e non si verificherà mai con un filtro di fioritura.
In termini di spazio, il filtro di fioritura è costante, poiché non è mai necessario utilizzare più memoria rispetto alla matrice designata. D'altra parte, l'hash cresce in modo dinamico e potrebbe diventare molto più grande a causa del fatto di dover tenere traccia dei valori collisionati.
Sconti: Ora che sai cosa è economico e cosa no e in quali circostanze, dovresti essere in grado di vedere il trade-off. I filtri Bloom sono ottimi se vuoi rilevare molto rapidamente che un valore è stato visto in precedenza, ma puoi vivere con falsi positivi. D'altra parte, puoi scegliere la mappa di hash se vuoi garantire la correttezza al prezzo di non essere in grado di giudicare esattamente il tuo runtime, ma puoi accettare casi degenerati occasionalmente che possono essere molto più lenti della media.
Allo stesso modo, se ti trovi in un ambiente con memoria limitata potresti preferire filtri di fioritura per la garanzia di utilizzo della memoria.
I casi d'uso per i filtri di fioritura e gli hash sono distinti e per lo più disgiunti, quindi il confronto diretto non ha senso. Inoltre dipenderà dai dettagli tecnici delle implementazioni in quanto vi sono molti modi per gestire le collisioni hash con diversi compromessi.
Il filtro di fioritura può rispondere se l'elemento si trova in un insieme di insiemi enormi , con probabilità ragionevole, ma non esattamente, utilizzando una quantità di memoria modesta. Enormi, come, trilioni di elementi. Ma non sono mai esatti. È possibile ridurre la quantità di falsi positivi solo utilizzando più memoria o più funzioni hash.
D'altra parte le tabelle hash sono esatte, ma hanno bisogno di memorizzare il set. Quindi trilioni di elementi richiederebbe terrabyte di memoria (e sono solo trilioni americani). Possono inoltre memorizzare dati aggiuntivi per ciascun elemento, che non possono essere filtrati dai filtri.
Quindi i filtri di fioritura vengono utilizzati quando si ha un metodo lento di acquisizione dei dati per un membro (che implica query su server, letture dal disco e simili) di un set di grandi dimensioni (che non si adatta alla memoria o non è pratico trasferirlo al client o simili) e si desidera evitare di eseguire l'operazione lenta per oggetti che non si trovano nel set.
Leggi altre domande sui tag data-structures