Bloom Filters & Probabilistic Data Structures

// Python 3.10+ Bloom Filter
import hashlib

class BloomFilter:
    def __init__(self, size_in_bits: int, hash_count: int):
        self.size = size_in_bits
        self.k = hash_count
        self.bit_array = bytearray((size_in_bits + 7) // 8)

    def _hashes(self, item: str):
        # Kirsch-Mitzenmacher optimization: generate k hashes from 2 hash values
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.k):
            yield (h1 + i * h2) % self.size

    def add(self, item: str):
        for bit in self._hashes(item):
            self.bit_array[bit // 8] |= (1 << (bit % 8))

    def contains(self, item: str) -> bool:
        for bit in self._hashes(item):
            if not (self.bit_array[bit // 8] & (1 << (bit % 8))):
                return False  # Definitely not present (0% false negative)
        return True  # Probably present

// C++20 Bloom Filter with std::vector<bool>
#include <vector>
#include <string>

class BloomFilter {
    std::vector<bool> bits;
    int k;
public:
    BloomFilter(size_t size, int hashes) : bits(size, false), k(hashes) {}

    void add(const std::string& item) {
        size_t h = std::hash<std::string>{}(item);
        for (int i = 0; i < k; ++i) {
            bits[(h + i * 0x9e3779b9) % bits.size()] = true;
        }
    }

    bool contains(const std::string& item) const {
        size_t h = std::hash<std::string>{}(item);
        for (int i = 0; i < k; ++i) {
            if (!bits[(h + i * 0x9e3779b9) % bits.size()]) return false;
        }
        return true;
    }
};

// Java BitSet Bloom Filter
import java.util.BitSet;

public class BloomFilter {
    private final BitSet bitSet;
    private final int size;
    private final int k;

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.k = hashCount;
        this.bitSet = new BitSet(size);
    }

    public void add(String item) {
        int h = item.hashCode();
        for (int i = 0; i < k; i++) {
            int idx = Math.abs((h + i * 31) % size);
            bitSet.set(idx);
        }
    }

    public boolean contains(String item) {
        int h = item.hashCode();
        for (int i = 0; i < k; i++) {
            int idx = Math.abs((h + i * 31) % size);
            if (!bitSet.get(idx)) return false;
        }
        return true;
    }
}

// Go Bit Array Bloom Filter
package main

import "hash/fnv"

type BloomFilter struct {
    bits []byte
    size uint32
    k    uint32
}

func (b *BloomFilter) Add(item string) {
    h := fnv.New32a()
    h.Write([]byte(item))
    val := h.Sum32()
    for i := uint32(0); i < b.k; i++ {
        idx := (val + i*0x5bd1e995) % b.size
        b.bits[idx/8] |= (1 << (idx % 8))
    }
}

// TypeScript Uint8Array Bloom Filter
export class BloomFilter {
    private bits: Uint8Array;
    constructor(private size: number, private k: number) {
        this.bits = new Uint8Array(Math.ceil(size / 8));
    }

    add(item: string): void {
        const h = this.hash(item);
        for (let i = 0; i < this.k; i++) {
            const idx = Math.abs((h + i * 31) % this.size);
            this.bits[Math.floor(idx / 8)] |= (1 << (idx % 8));
        }
    }

    contains(item: string): boolean {
        const h = this.hash(item);
        for (let i = 0; i < this.k; i++) {
            const idx = Math.abs((h + i * 31) % this.size);
            if (!(this.bits[Math.floor(idx / 8)] & (1 << (idx % 8)))) return false;
        }
        return true;
    }
}