Trasformare in modo intelligente una tabella hash in una struttura dati probabilistica per scambiare la precisione con grandi guadagni di memoria
Htavolo in frassino è una delle strutture dati più conosciute e utilizzate. Con una saggia scelta della funzione hash, una tabella hash può produrre prestazioni ottimali per query di inserimento, ricerca ed eliminazione in tempo costante.
Lo svantaggio principale della tabella hash sono le potenziali collisioni. Per evitarli, uno dei metodi standard prevede l'aumento della dimensione della tabella hash. Sebbene questo approccio funzioni bene nella maggior parte dei casi, a volte siamo ancora limitati nell'utilizzo di un ampio spazio di memoria.
È necessario ricordare che una tabella hash fornisce sempre una risposta corretta a qualsiasi query. Potrebbe subire collisioni ed essere lento a volte, ma è così Sempre garantisce risposte corrette al 100%.. Si scopre che in alcuni sistemi non è sempre necessario ricevere informazioni corrette per le query. Tale diminuzione della precisione può essere utilizzata per concentrarsi sul miglioramento di altri aspetti del sistema.
In questo articolo scopriremo una struttura dati innovativa chiamata a Filtro Bloom. In parole semplici, si tratta di una versione modificata di una tabella hash standard che baratta una piccola diminuzione della precisione con guadagni di spazio di memoria.
Il filtro Bloom è organizzato sotto forma di un array booleano di dimensione m. Inizialmente tutti i suoi elementi sono contrassegnati come 0 (falso). Oltre a ciò, è necessario scegliere funzioni hash k che prendano gli oggetti come input e li mappano nell'intervallo (0, m – 1). Ogni valore di output corrisponderà successivamente a un elemento dell'array in quell'indice.
Per ottenere risultati migliori, si consiglia che le funzioni hash restituiscano valori la cui distribuzione sia quasi uniforme.
Inserimento
Ogni volta che è necessario aggiungere un nuovo oggetto, viene passato attraverso k funzioni hash predefinite. Per ogni valore hash di output, l'elemento corrispondente a quell'indice diventa 1 (vero).
Se un elemento dell'array il cui indice è stato emesso da una funzione hash è già stato impostato su 1, rimane semplicemente come 1.
Fondamentalmente, la presenza di 1 in qualsiasi elemento dell'array agisce come una prova parziale che un elemento che ha il rispettivo indice dell'array esiste effettivamente nel filtro Bloom.
Ricerca
Per verificare se un oggetto esiste, vengono calcolati i suoi valori hash k. Gli scenari possibili possono essere due:
Se questo è almeno una valore hash per il quale il rispettivo elemento dell'array è uguale a 0, ciò significa che il l'oggetto non esiste.
Durante l'inserimento, un oggetto viene associato a diversi elementi dell'array contrassegnati come 1. Se un oggetto esistesse realmente nel filtro, tutte le funzioni hash produrrebbero in modo deterministico la stessa sequenza di indici che puntano a 1. Tuttavia, puntando a un array l'elemento con 0 significa chiaramente che l'oggetto corrente non è presente nella struttura dati.
Se per tutti i valori hashi rispettivi elementi dell'array sono uguali a 1, ciò significa che il oggetto probabilmente esiste (non al 100%).
Questa affermazione è esattamente ciò che rende il filtro Bloom una struttura dati probabilistica. Se un oggetto è stato aggiunto prima, durante una ricerca il filtro Bloom garantisce che i valori hash saranno gli stessi per esso, quindi l'oggetto verrà trovato.
Tuttavia, il filtro Bloom può produrre una risposta falsa positiva quando un oggetto in realtà non esiste ma il filtro Bloom sostiene il contrario. Ciò accade quando tutte le funzioni hash per l'oggetto restituiscono valori hash pari a 1 corrispondenti ad altri oggetti già inseriti nel filtro.
Le risposte false positive tendono a verificarsi quando il numero di oggetti inseriti diventa relativamente alto rispetto alla dimensione dell'array del filtro Bloom.
Stima degli errori falsi positivi
È possibile stimare la probabilità di ottenere un errore falso positivo, data la struttura del filtro Bloom.
La prova completa di questa formula può essere trovata su Wikipedia. Sulla base di questa espressione, possiamo fare un paio di osservazioni interessanti:
- La probabilità FP diminuisce con l'aumento del numero di funzioni hash hash k, l'aumento della dimensione dell'array m e la diminuzione del numero di oggetti inseriti n.
- Prima di inserire oggetti nel filtro Bloom, possiamo trovare il numero ottimale di funzioni hash richieste k che minimizzerà la probabilità FP se conosciamo la dimensione dell'array m e possiamo stimare il numero di oggetti n che verranno inseriti in futuro.
Un'altra opzione per ridurre la probabilità FP è una combinazione (congiunzione AND) di diversi filtri Bloom indipendenti. Un elemento viene infine considerato presente nella struttura dati solo se è presente in tutti i filtri Bloom.
Vincoli
- Contrariamente alle tabelle hash, l'implementazione standard di un filtro Bloom non supporta la cancellazione.
- Il numero scelto di funzioni hash k e la dimensione dell'array m all'inizio non può essere modificato in seguito. Se ce n'è la necessità, l'unico modo per farlo è costruire un altro filtro Bloom con nuove impostazioni inserendo tutti gli oggetti precedentemente memorizzati.
Secondo il pagina di Wikipedia, l'enciclopedia liberail filtro Bloom è molto utilizzato nei grandi impianti:
- Database come Apache HBase, Apache Cassandra E PostgreSQL utilizzare il filtro Bloom per controllare righe o colonne inesistenti. Questo approccio è notevolmente più veloce rispetto all'utilizzo delle ricerche su disco.
- medio utilizza il filtro Bloom per filtrare le pagine che sono già state consigliate a un utente.
- Google Chrome ha utilizzato il filtro Bloom in passato per identificare URL dannosi. Un URL veniva considerato sicuro se il filtro Bloom restituiva una risposta negativa. In caso contrario, è stato eseguito il controllo completo.
In questo articolo abbiamo trattato un approccio alternativo alla costruzione di tabelle hash. Quando una piccola diminuzione della precisione può essere compromessa per un utilizzo più efficiente della memoria, il filtro Bloom risulta essere una soluzione solida in molti sistemi distribuiti.
Variare il numero di funzioni hash con la dimensione del filtro Bloom ci consente di trovare l'equilibrio più adatto tra precisione e requisiti di prestazione.
Tutte le immagini, se non diversamente specificato, sono dell'autore.
Fonte: towardsdatascience.com
