Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Build a Bloom Filter using Murmur3 and FNV-1a hash functions. Implement a counting Bloom…

  1. User

    Build a Bloom Filter using Murmur3 and FNV-1a hash functions. Implement a counting Bloom filter variant using 4-bit counters instead of single bits to allow element deletion with a small probability of false negatives.

  2. Assistant

    Implementing counting Bloom filter with Murmur3 and FNV-1a

    A Python Bloom filter uses Murmur3 and FNV-1a 32-bit hashes combined with double hashing to generate multiple positions. The counting Bloom filter variant replaces bits with 4-bit saturating counters (0–15) to allow deletions, though removing may cause false negatives if counters overlap. The implementation includes add, check (via contains), and remove methods with safe counter updates. Both hash functions are implemented for clarity and self-containment. A standard Bloom filter uses (k) hash functions to set bits in a bit array of length (m). Querying membership checks that all (k) corresponding bits are set. The tradeoff is that the filter can return false positives but never false negatives. A counting Bloom filter replaces each bit with a small counter; it lets you decrement counts when you remove an element. If different elements collide on the same counters, a removal can drive a counter back to zero and introduce a small probability of false negatives for other elements.

    Below is a self‑contained Python implementation that uses two base hash functions — MurmurHash3 and FNV‑1a — and derives (k) hash values via double hashing ((h_i = h_1 + i \cdot h_2 \pmod m)). The basic BloomFilter uses a boolean bit array, and the CountingBloomFilter uses 4‑bit counters stored in an integer array and saturates at 15.

    import struct
    import sys
    
    def murmur3_32(data: bytes, seed: int = 0) -> int:
        """
        Pure-Python MurmurHash3 x86 32-bit implementation.
        """
        data = bytearray(data)
        length = len(data)
        nblocks = length // 4
    
        h1 = seed & 0xffffffff
        c1 = 0xcc9e2d51
        c2 = 0x1b873593
    
        # body
        for block_start in range(0, nblocks * 4, 4):
            k1 = struct.unpack_from("<I", data, block_start)[0]
            k1 = (k1 * c1) & 0xffffffff
            k1 = ((k1 << 15) | (k1 >> 17)) & 0xffffffff  # ROTL15
            k1 = (k1 * c2) & 0xffffffff
    
            h1 ^= k1
            h1 = ((h1 << 13) | (h1 >> 19)) & 0xffffffff  # ROTL13
            h1 = (h1 * 5 + 0xe6546b64) & 0xffffffff
    
        # tail
        tail_index = nblocks * 4
        k1 = 0
        tail_size = length & 3
        if tail_size == 3:
            k1 ^= data[tail_index + 2] << 16
        if tail_size >= 2:
            k1 ^= data[tail_index + 1] << 8
        if tail_size >= 1:
            k1 ^= data[tail_index]
            k1 = (k1 * c1) & 0xffffffff
            k1 = ((k1 << 15) | (k1 >> 17)) & 0xffffffff
            k1 = (k1 * c2) & 0xffffffff
            h1 ^= k1
    
        # finalization
        h1 ^= length
        h1 &= 0xffffffff
        h1 ^= h1 >> 16
        h1 = (h1 * 0x85ebca6b) & 0xffffffff
        h1 ^= h1 >> 13
        h1 = (h1 * 0xc2b2ae35) & 0xffffffff
        h1 ^= h1 >> 16
    
        return h1
    
    def fnv1a_32(data: bytes) -> int:
        """
        FNV-1a 32-bit hash.
        """
        fnv_prime = 0x01000193
        hash_ = 0x811c9dc5  # offset basis
        for byte in data:
            hash_ ^= byte
            hash_ = (hash_ * fnv_prime) & 0xffffffff
        return hash_
    
    class BloomFilter:
        def __init__(self, size: int, num_hashes: int):
            self.size = size
            self.num_hashes = num_hashes
            self.bits = bytearray(size)  # each entry is 0 or 1
    
        def _hashes(self, item: bytes):
            h1 = murmur3_32(item)
            h2 = fnv1a_32(item)
            for i in range(self.num_hashes):
                yield (h1 + i * h2) % self.size
    
        def add(self, item):
            b = self._to_bytes(item)
            for idx in self._hashes(b):
                self.bits[idx] = 1
    
        def __contains__(self, item) -> bool:
            b = self._to_bytes(item)
            return all(self.bits[idx] for idx in self._hashes(b))
    
        @staticmethod
        def _to_bytes(item) -> bytes:
            if isinstance(item, str):
                return item.encode('utf-8')
            elif isinstance(item, bytes):
                return item
            else:
                return str(item).encode('utf-8')
    
    class CountingBloomFilter:
        def __init__(self, size: int, num_hashes: int):
            self.size = size
            self.num_hashes = num_hashes
            # store counts as ints; enforce 4-bit saturation (0..15)
            self.counts = [0] * size
    
        def _hashes(self, item: bytes):
            h1 = murmur3_32(item)
            h2 = fnv1a_32(item)
            for i in range(self.num_hashes):
                yield (h1 + i * h2) % self.size
    
        def add(self, item):
            b = self._to_bytes(item)
            for idx in self._hashes(b):
                if self.counts[idx] < 15:  # saturate at 4-bit max
                    self.counts[idx] += 1
    
        def remove(self, item):
            """
            Decrement counters for item. If counters are shared, this can
            introduce false negatives for other elements.
            """
            b = self._to_bytes(item)
            for idx in self._hashes(b):
                if self.counts[idx] > 0:
                    self.counts[idx] -= 1
    
        def __contains__(self, item) -> bool:
            b = self._to_bytes(item)
            return all(self.counts[idx] > 0 for idx in self._hashes(b))
    
        @staticmethod
        def _to_bytes(item) -> bytes:
            if isinstance(item, str):
                return item.encode('utf-8')
            elif isinstance(item, bytes):
                return item
            else:
                return str(item).encode('utf-8')
    
    # Example usage:
    if __name__ == "__main__":
        bf = BloomFilter(size=1000, num_hashes=4)
        cbf = CountingBloomFilter(size=1000, num_hashes=4)
    
        for word in ["apple", "banana", "cherry"]:
            bf.add(word)
            cbf.add(word)
    
        print("banana" in bf)  # True
        print("durian" in bf)  # False (likely)
    
        print("banana" in cbf)  # True
        cbf.remove("banana")
        print("banana" in cbf)  # False (we just removed)
    

    Notes:

    • The size parameter (m) and num_hashes (k) control the false positive rate; you should choose them based on your expected number of insertions and acceptable false positive probability.
    • The counting filter uses 4‑bit counters (0–15). When a counter is shared by multiple elements, removing one element decrements the shared counter and can produce a false negative for another element whose hashes overlap at that position. Using more bits per counter reduces the chance of underflow when multiple elements map to the same counter.

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