Bloom Filter is a probabilistic data structure that is used to determine the membership of an element in a set of elements. It is probabilistic because it can produce false-positive matches (The data structure can return the result saying an element is possibly present in the set which may not be 100% accurate), but it cannot produce false-negatives (If the data structure returns the result saying an element is not present, it is 100% accurate).
The primary data structure used in Bloom Filter is a Bit Vector. The initial state of the Bit Vector will be all empty (0s). Each Bloom Filter is associated with k hash functions whose job is to accept input and the input is passed through each of the k hash function and generated bit indices are set to 1 in the Bit Vector.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert | O(k) | O(m) |
| Search | O(k) | O(m) |
Note: Bloom filters do not support deletion directly, as clearing bits may affect other elements' membership tests. Variations like counting Bloom filters can support deletion.
© 2024 Adarsh Sidnal - KLE Technological University, Hubballi-31