Et Bloom filter er en pladsbesparende probabilistisk datastruktur, der besvarer sætmedlemskapsspørgsmål med en drejning: det kan have falske positive, men aldrig falske negative. "Definitivt ikke til stede" er sikker; "muligvis til stede" kræver en ægte kontrol.
Et bitarray på bits og hashfunktioner. For at et element skal du indstille de bits, det hashes til. For at , tjek de bits — hvis nogen er 0, er elementet helt sikkert fravær.
mkkkbits: [0 0 0 0 0 0 0 0]
add "cat": hash->bits 1,4,6 -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
class BloomFilter:
def __init__(self, m, hashes):
self.bits = [0]*m
self.m, self.hashes = m, hashes # list of hash fns
def add(self, x):
for h in self.hashes:
self.bits[h(x) % self.m] = 1
def __contains__(self, x): # False = certain; True = maybe
return all(self.bits[h(x) % self.m] for h in self.hashes)
| Handling | Tid | Plads |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
Ingen falske negative; falsk-positiv-rate falder som m (og tunet k) vokser.
Bloom filters springer billigt dyrt arbejde over: databaser (f.eks. Cassandra, HBase) bruger dem til at undgå disklæsninger for nøgler, der definitivt ikke er på disken.
De legemliggør en klassisk systemafvejning — accepter en lille, afgrænset fejlrate i bytte for en enorm reduktion i hukommelse og I/O.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér