Skip to content

Latest commit

 

History

History
48 lines (32 loc) · 1.81 KB

readme.md

File metadata and controls

48 lines (32 loc) · 1.81 KB

Bloom Filter

A Bloom Filter is a probabilistic data structure that is used to test whether an element is a member of a set. It is highly space-efficient but allows for a small probability of false positives.

How It Works

  1. Initialization: A Bloom Filter is initialized with an array of bits set to 0.
  2. Hash Functions: Multiple independent hash functions are used to hash each element.
  3. Insertion: To add an element, it is hashed using all hash functions, and the corresponding bits in the array are set to 1.
  4. Query: To check if an element is in the set, it is hashed using all hash functions. If all corresponding bits are 1, the element is probably in the set; if any bit is 0, the element is definitely not in the set.

Advantages

  • Space Efficient: Requires less memory compared to other data structures.
  • Speed: Fast insertion and query operations.

Disadvantages

  • False Positives: May return false positives, meaning it might indicate that an element is in the set when it is not.
  • No Deletion: Standard Bloom Filters do not support deletion of elements.

Use Cases

  • Databases: To quickly check if an element is present in a large dataset.
  • Networking: To prevent cache poisoning in distributed systems.
  • Security: To detect malicious URLs or spam.

Example

from bloom_filter import BloomFilter

# Initialize Bloom Filter with expected number of elements and false positive rate
bloom = BloomFilter(max_elements=1000, error_rate=0.1)

# Add elements
bloom.add("apple")
bloom.add("banana")

# Query elements
print("apple" in bloom)  # Output: True
print("cherry" in bloom) # Output: False

References