Build a Bloom Filter using Murmur3 and FNV-1a hash functions. Implement a counting Bloom…
- 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.
- 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
BloomFilteruses a boolean bit array, and theCountingBloomFilteruses 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
sizeparameter (m) andnum_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.
- The
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.