che cosa sta memorizzando i dati nello spazio costante?

Questa affermazione è abbastanza vera, ma non proprio. Un filtro Bloom è una struttura dati utile per la memorizzazione di più hash. Generalmente, lo implementeresti come una matrice di bit o di int che ogni cella dell'array esegue il mapping ad una posizione di bit nella rappresentazione binaria di un intero, di solito un hash. Per vedere se l'hash che stai cercando è memorizzato nel filtro, devi controllare se tutti i suoi bit sono impostati. C'è sempre la possibilità che otterrai un falso positivo, ovviamente, quindi l'uso a cui hai messo il filtro Bloom deve essere tollerante a tale possibilità.

Il filtro Bloom ha sempre le stesse dimensioni, indipendentemente dal numero di hash che hai impostato, ma aumenta anche la probabilità di falsi positivi, quindi la sua utilità diminuisce.

Un filtro Bloom non è un secchio magico nel quale puoi lanciare tutti i dati che vuoi e non diventa mai più grande. Questo si chiama Bag of Holding e devi andare in un posto chiamato Greyhawk per trovarne uno.

EDIT: Quindi, un filtro Bloom è una matrice di bit. Quando è nuovo, sarà pieno di zeri. Per aggiungere un hash ad esso, calcoli il valore binario di quell'hash e poi OR con il filtro Bloom

0000000000000000 BF start
0010011010010010 Hash that I want to add

0010011010010010 BF state
1001010001010011 Hash that I want to add

1011011011010011 BF state

Ora, per verificare se un determinato hash è stato aggiunto al filtro Bloom, lo trasformo un numero binario e verificare che ogni bit impostato sia impostato anche nel BF:

1011011011010011 BF state
0100100100100010 Hash that I am testing
                 Negative! Hash has not been added to the BF

Tuttavia, i falsi positivi sono possibili:

1011011011010011 BF state
1011011011010011 Hash that I am testing
                 False Positive! Hash checks out, but I never added that value.

Questo esempio sembra banale perché il filtro ha solo 16 bit, e questa è una versione molto semplificata di un filtro Bloom, ma il principio è comprensibile, spero.

Questo risponde alla tua domanda @Timothy?

Non sono sicuro dei filtri bloom, o anche della validità di questa affermazione, ma so che in generale, "spazio costante" significa che la quantità di dati N richiede la stessa quantità di spazio , qualunque cosa sia N .

Quindi, quando la tua fonte dice "un filtro di fioritura ci consente di memorizzare i dati in uno spazio costante", significa che non importa quanti dati hai, ci vorrà sempre la stessa quantità di memoria per memorizzarli.

Un esempio potrebbe essere l'hash MD5. Un digest MD5 conterrà sempre 128 bit, non importa se si assegna un algoritmo di hashing a un singolo carattere oa tutta la Wikipedia.

Questo è simile (e correlato) alla complessità dell'algoritmo: la ricerca di un valore in una hashmap è sempre O(1) - tempo costante, ovvero non importa quanto grande sia l'hashmap, richiederà sempre lo stesso tempo per trovare l'hash.