Bitget App
Trade smarter
Acquista CryptoMercatiTradingFuturesCopy TradingBotEarn

Filtro Bloom

Avanzato
share

Un "Filtro Bloom" è una struttura dati probabilistica progettata per verificare in modo efficiente se un elemento fa parte di un insieme. È stato inventato da Burton Howard Bloom nel 1970 ed è diventato uno strumento fondamentale dell'informatica grazie alla sua capacità di gestire grandi insiemi di dati con un consumo minimo di memoria. A differenza delle strutture dati tradizionali, come le tabelle hash o gli alberi binari di ricerca, un filtro bloom può fornire una risposta definitiva quando un elemento non è presente nell'insieme, ma solo una risposta probabilistica quando un elemento è presente. Ciò significa che mentre i falsi positivi sono possibili, i falsi negativi non lo sono.

Il concetto di base di un filtro bloom ruota attorno a un array (matrice) di bit, tutti inizialmente impostati a 0, e a una serie di funzioni hash. Quando un elemento viene aggiunto al filtro bloom, viene passato attraverso ciascuna delle funzioni hash per generare più posizioni nell'array di bit. I bit in queste posizioni vengono quindi impostati a 1. Per verificare se un elemento è presente nell'insieme, si esegue nuovamente l'hashing utilizzando le stesse funzioni e si controllano i bit corrispondenti. Se tutti i bit in queste posizioni sono 1, l'elemento è considerato possibile nell'insieme; se uno qualsiasi dei bit è 0, l'elemento non è sicuramente nell'insieme.

Uno dei vantaggi significativi dei filtri bloom è la loro efficienza in termini di spazio. Richiedono una quantità di memoria significativamente inferiore rispetto ad altre strutture di dati per la stessa attività, soprattutto all'aumentare del numero di elementi. Ad esempio, per ottenere una probabilità di falso positivo dell'1%, indipendentemente dal numero di elementi dell'insieme, sono necessari meno di 10 bit per elemento. Questo rende i filtri bloom particolarmente utili nelle applicazioni in cui l'uso della memoria è una preoccupazione primaria, come i router di rete, i sistemi di database e i sistemi distribuiti.

Tuttavia, i filtri bloom presentano alcune limitazioni. L'impossibilità di rimuovere gli elementi dall'insieme è uno svantaggio principale, poiché cancellare i bit impostati da più elementi introdurrebbe falsi negativi. Per risolvere questo problema sono state sviluppate varianti come i filtri bloom a conteggio, che consentono di rimuovere gli elementi mantenendo un conteggio del numero di volte in cui ogni bit è stato impostato. Inoltre, il tasso di falsi positivi aumenta con l'aggiunta di più elementi, il che significa che la dimensione dell'array di bit e il numero di funzioni hash devono essere scelti con attenzione in base al numero di elementi previsto e al tasso di falsi positivi accettabile.

Nelle applicazioni pratiche, i filtri bloom hanno trovato ampio utilizzo in vari ambiti. Ad esempio, nel caso di Bitcoin, vengono utilizzati per migliorare la privacy nei client SPV (verifica semplificata di pagamento), consentendo agli utenti di interrogare le transazioni senza rivelare i propri indirizzi. Le reti di distribuzione dei contenuti come Akamai utilizzano i filtri bloom per gestire in modo efficiente l'archiviazione della cache, riducendo il carico di lavoro sui server evitando recuperi di dati non necessari. Nonostante la loro natura probabilistica e le loro limitazioni, i filtri bloom rimangono uno strumento molto utile per la progettazione di sistemi efficienti e scalabili.

Scarica l’app
Scarica l’app