A probabilistic data structure using a bit array and k hash functions. Answers "is this key in the set?" with zero false negatives but possible false positives.
Bit = 1
Bit = 0
Hash 1
Hash 2
Hash 3
0
Bits Set
0%
Fill Rate
0%
FP Rate
A Bloom filter uses k hash functions to map keys to bit positions. Insert sets those bits; lookup checks if all are set.
Lookup Result
Inserted Keys
No keys inserted yet
Configuration
Insert Key
Lookup Key
Try looking up a key you haven't inserted to see a false negative guarantee, or a never-inserted key that happens to collide for a false positive.
How Hash Functions Work
Enter a key above to see hash values
Key Properties
False Negatives: Never occur False Positives: Can occur Space: O(m) bits (very compact) Insert: O(k) hash computations Lookup: O(k) hash computations Delete: Not supported