Skip to content
TheChatArchiveThe Chat Archive
GeminiGemini 3 Pro Preview· googleHugging Face Frontier Reasoning Traces

Build a bloom filter and demonstrate its use in detecting duplicates.

  1. User

    Build a bloom filter and demonstrate its use in detecting duplicates.

  2. Gemini Assistant

    Analyzing the Bloom Filter

    I'm currently focused on the core concept of a Bloom Filter. It seems like a probabilistic data structure. I'm moving beyond just the definition, and now I'm thinking about the practical application for duplicate detection, as that is the user's ultimate goal. I need to understand its strengths and weaknesses in this context.

    Implementing Duplicate Detection

    I've decided to prioritize a Python-based implementation for demonstration. I'm choosing hashlib for hash functions to avoid external dependencies, aligning with the "runnable out-of-the-box" requirement. I'm now exploring the implementation of the bit array and the hashing mechanism. My focus is on achieving a balance between clarity and practical usability for duplicate detection.

    Evaluating Hash Functions

    The project requires understanding the impact of hash functions on performance. I'm currently analyzing the time complexity of different hash functions with varying input sizes. Considering the user's objective, I'm leaning toward recommending non-cryptographic hashes for speed, while acknowledging the security implications. I'm exploring the practical trade-offs.

    Defining the Core Class

    I'm now focused on the practical implementation. I'm building out the BloomFilter class in Python, defining the __init__, add, and check methods. I'm focusing on incorporating the double hashing method to generate multiple hash indices. I will include the mathematical calculations for determining the optimal array size (mm) and the number of hash functions (kk).

    Refining Hash and Logic

    I'm now focusing on optimizing the hash function implementation. The double hashing is implemented using md5 and I'm generating multiple hash indices from a single digest, balancing speed and the requirement for "runnable out of the box." Next, I will refactor the internal logic. This will include adding the double hashing method to generate multiple hash indices, incorporating the math for mm and kk.

    Finalizing Implementation Details

    I'm now focused on the practical coding of the BloomFilter class in Python. I'm building it from scratch, using a boolean list for the bit array. I have finished the initialization, and now the focus is on the add and check methods with the double hashing logic inside _get_hash_indices. My next step is to incorporate the math for size and hash count, then test the finished class with a duplicate detection use case.

    Here is a complete guide to building a Bloom Filter from scratch in Python.

    What is a Bloom Filter?

    A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.

    • Space Efficient: It uses a bit array rather than storing the actual items.
    • Probabilistic:
      • False Negatives: Impossible. If the filter says "No", the item is definitely not there.
      • False Positives: Possible. If the filter says "Yes", the item is likely there, but there is a small chance it is not.

    The Implementation (Python)

    We will build a class that handles the mathematics of sizing the bit array and the hashing logic. We will use the Double Hashing technique to simulate multiple hash functions using reasonable standard libraries.

    import math
    import hashlib
    
    class BloomFilter:
        def __init__(self, expected_items, false_positive_rate):
            """
            expected_items (n): Estimated number of items to add.
            false_positive_rate (p): Desired error rate (e.g., 0.01 for 1%).
            """
            self.false_positive_rate = false_positive_rate
            
            # 1. Calculate Size of Bit Array (m)
            # Formula: m = -(n * ln(p)) / (ln(2)^2)
            self.size = - (expected_items * math.log(false_positive_rate)) / (math.log(2) ** 2)
            self.size = int(self.size)
            
            # 2. Calculate Number of Hash Functions (k)
            # Formula: k = (m/n) * ln(2)
            self.hash_count = (self.size / expected_items) * math.log(2)
            self.hash_count = int(self.hash_count)
            
            # 3. Initialize Bit Array
            # In a real low-level imp, this would be a continuous block of bits.
            # Here, a list of booleans serves as a readable abstraction.
            self.bit_array = [False] * self.size
            
            print(f"Initialized: Size={self.size} bits, Hash Functions={self.hash_count}")
    
        def _get_hash_indices(self, item):
            """
            Generates 'k' indices for a given item using Double Hashing.
            h(i) = (h1 + i * h2) % m
            """
            item_str = str(item).encode('utf-8')
            
            # Generate two large hash values using MD5 (standard and deterministic)
            # We split the 128-bit MD5 digest into two 64-bit integers
            digest = hashlib.md5(item_str).hexdigest()
            h1 = int(digest[0:16], 16)
            h2 = int(digest[16:32], 16)
            
            indices = []
            for i in range(self.hash_count):
                # Double hashing formula to generate k unique indices
                index = (h1 + i * h2) % self.size
                indices.append(index)
                
            return indices
    
        def add(self, item):
            """Add an item to the Bloom Filter"""
            for index in self._get_hash_indices(item):
                self.bit_array[index] = True
    
        def check(self, item):
            """
            Check for existence.
            Returns True if item MIGHT be present.
            Returns False if item is DEFINITELY NOT present.
            """
            for index in self._get_hash_indices(item):
                if not self.bit_array[index]:
                    return False
            return True
    

    Demonstration: Detecting Duplicates

    Bloom filters are frequently used in web crawlers (to check if a URL has already been visited) or transaction processors. Below is a simulation of a stream of data containing duplicates.

    # 1. Setup: We expect 20 items, allow 5% error rate
    bloom = BloomFilter(expected_items=20, false_positive_rate=0.05)
    
    # A stream of emails (some are duplicates)
    email_stream = [
        "alice@example.com",
        "bob@example.com",
        "charlie@example.com", # New
        "alice@example.com",   # Duplicate
        "dave@example.com",
        "bob@example.com",     # Duplicate
        "eve@example.com"
    ]
    
    print("\n--- Processing Stream ---")
    
    processed_emails = []
    
    for email in email_stream:
        # CHECK if exists
        if bloom.check(email):
            print(f"[DUPLICATE DETECTED] Skipped: {email}")
        else:
            # If not, ADD to filter and process
            bloom.add(email)
            processed_emails.append(email)
            print(f"[NEW] Processed: {email}")
    
    print("\n--- Final Result ---")
    print(f"Processed {len(processed_emails)} unique emails: {processed_emails}")
    

    Why use this over a Python set?

    You might ask: Why not just use seen_emails = set()?

    1. Memory Usage:
      • A Python set stores the entire string of every email. If you have 1 billion URLs, that requires hundreds of Gigabytes of RAM.
      • A Bloom Filter stores bits. For 1 billion items with a 1% error rate, a Bloom Filter only requires about 1.1 GB of RAM, regardless of how long the URL strings are.
    2. Performance:
      • Checking a bit array is extremely fast and efficient in terms of CPU cache usage compared to chasing pointers in a hash map/set.

    Limitations to keep in mind

    Since the filter can return False Positives, you have two strategies for duplicate detection:

    1. Acceptable Loss: In a recommendation engine (e.g., "Don't show this ad twice"), it is okay if you accidentally hide an ad the user has not seen (False positive), as long as you never show one they have seen (True Negative).
    2. Two-Tier Check: Use the Bloom Filter as a "Gatekeeper." If the Bloom Filter says "Maybe", then (and only then) do you perform the expensive disk lookup or database query to confirm if it is actually a duplicate.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.