Ultimo aggiornamento: 2026-07-13

Dimensionamento del filtro di Bloom

Un filtro di Bloom è un modo compatto di rispondere a una sola domanda: «ho probabilmente già visto questo elemento?». Non memorizza chiavi, ma solo un array di bit, e scambia una piccola probabilità regolabile di falso positivo con un grande risparmio di memoria. Due numeri ne decidono la forma — quanti elementi prevedi di memorizzare e con quale frequenza tolleri una corrispondenza falsa — e da essi derivano direttamente la dimensione ottimale dell’array di bit e il numero di funzioni hash.

La formula

Per $n$ elementi previsti e un tasso di falsi positivi obiettivo $p$, l’array di bit che minimizza la memoria ha lunghezza

Il numero ottimale di funzioni hash è allora

arrotondato all’intero più vicino. Qui $m$ è il numero di bit, $k$ è il numero di funzioni hash indipendenti applicate a ogni elemento e $\ln 2 \approx 0{,}693$. Poiché $p$ è una probabilità minore di 1, il suo logaritmo naturale è negativo, quindi entrambe le formule producono valori positivi.

Esempio svolto. Un filtro per un milione di elementi ($n = 1{,}000{,}000$) con obiettivo dell’1% ($p = 0{,}01$):

Un milione di elementi all’1% costano dunque circa 1,14 MiB di memoria e sette funzioni hash — all’incirca 9,6 bit per elemento, una cifra che vale per qualsiasi numero di elementi a quella precisione.

Bit per elemento e la scala di precisione

Poiché la formula della dimensione è lineare in $n$, il costo di memoria per elemento, $m / n = -\ln p / (\ln 2)^2$, dipende solo dal tasso obiettivo. Ciò lo rende una misura pulita per confrontare i budget di precisione.

Ogni riduzione di dieci volte del tasso di falsi positivi aggiunge circa 4,8 bit per elemento e all’incirca tre funzioni hash. La memoria cresce solo linearmente mentre il tasso di errore cala geometricamente, ed è questo a rendere attraenti i filtri di Bloom.

Perché il numero di hash conta

A dimensione dell’array fissa, troppe poche funzioni hash lasciano i bit radi e facili da colpire per caso, mentre troppe riempiono l’array così densamente che quasi ogni bit è impostato. Il punto ottimale imposta metà dei bit e si colloca a $k = (m/n)\ln 2$. Poiché $k$ deve essere intero, il calcolatore lo arrotonda, e il tasso di falsi positivi reale viene ricalcolato da quel valore arrotondato:

Nell’esempio sopra il $k = 7$ arrotondato dà circa 1,004%, un filo sopra l’obiettivo dell’1% perché il $k$ ideale era 6,64 e non un intero.

Cosa può e non può fare un filtro di Bloom

Un filtro di Bloom non produce mai un falso negativo: se dice che un elemento è assente, lo è davvero. L’unico errore è un falso positivo, il cui tasso è ciò che questo calcolatore dimensiona. I filtri standard supportano inserimento e ricerca, ma non la rimozione, perché i bit sono condivisi tra gli elementi: cancellare i bit di uno potrebbe corrompere gli altri. Quando serve la rimozione, un filtro di Bloom con contatori sostituisce ogni bit con un piccolo contatore, al costo di diverse volte la memoria, e un filtro cuckoo offre la rimozione con una dimensione comparabile.

Un’avvertenza: un filtro è dimensionato per un $n$ fisso. Inserisci molti più elementi del previsto e l’array si satura, spingendo il tasso di falsi positivi oltre l’obiettivo. Se la crescita è probabile, dimensiona fin dall’inizio per la quantità maggiore o usa un progetto scalabile che concatena più filtri.

L’arrotondamento nella pratica

Il numero di bit $m$ della formula è raramente un numero tondo. Le implementazioni reali allocano parole macchina o pagine di memoria intere, perciò arrotondano $m$ per eccesso, il che spinge il tasso di falsi positivi ottenuto un po’ sotto l’obiettivo — un piccolo bonus. La dimensione mostrata qui è il minimo teorico prima di quell’arrotondamento.

Calcoli correlati

I filtri di Bloom si basano sull’hashing, quindi la probabilità che due elementi condividano un hash è governata dalla stessa matematica del compleanno — vedi il Calcolatore di probabilità di collisione hash. Per identificatori di lunghezza fissa, il Calcolatore della probabilità di collisione degli UUID applica lo stesso ragionamento agli UUID, e lo Calcolatore di entropia di Shannon misura l’informazione che un insieme di dati porta con sé.