Bloom filter и Cuckoo filter

<?php

declare(strict_types=1);

/**
 * Bloom filter with two FNV-1a seeds used to derive k hashes
 * via double hashing: h_i(x) = h1(x) + i*h2(x).
 */
final class BloomFilter
{
    /** @var \GMP Bit array as arbitrary-precision integer (for simplicity). */
    private \GMP $bits;

    public function __construct(
        public readonly int $m,      // number of bits
        public readonly int $k,      // number of hashes
    ) {
        $this->bits = gmp_init(0);
    }

    /**
     * Construct optimal filter for expected n items and target false positive p.
     */
    public static function forCapacity(int $n, float $p): self
    {
        $m = (int) ceil(-($n * log($p)) / (log(2) ** 2));
        $k = max(1, (int) round(($m / $n) * log(2)));
        return new self($m, $k);
    }

    public function add(string $item): void
    {
        foreach ($this->hashes($item) as $bit) {
            $this->bits = gmp_setbit($this->bits, $bit, true) ?? $this->bits;
            gmp_setbit($this->bits, $bit, true);
        }
    }

    public function contains(string $item): bool
    {
        foreach ($this->hashes($item) as $bit) {
            if (gmp_testbit($this->bits, $bit) === false) {
                return false;
            }
        }
        return true;
    }

    /** @return \Generator<int, int> */
    private function hashes(string $item): \Generator
    {
        // Double hashing: two independent hashes are enough for k
        $h1 = hexdec(substr(hash('fnv1a64', $item), 0, 15));
        $h2 = hexdec(substr(hash('fnv1a64', 'seed:' . $item), 0, 15));

        for ($i = 0; $i < $this->k; $i++) {
            yield ($h1 + $i * $h2) % $this->m;
        }
    }
}

// Example
// $bf = BloomFilter::forCapacity(n: 1_000_000, p: 0.01);
// $bf->add('[email protected]');
// $bf->contains('[email protected]'); // true
// $bf->contains('[email protected]');   // almost certainly false

package bloom

import (
	"hash/fnv"
	"math"
)

// Filter is a classic Bloom filter using double hashing.
type Filter struct {
	bits []uint64 // packed bitset
	m    uint64   // number of bits
	k    uint64   // number of hashes
}

// New constructs a filter sized for n items and target false-positive rate p.
func New(n uint64, p float64) *Filter {
	m := uint64(math.Ceil(-(float64(n) * math.Log(p)) / (math.Ln2 * math.Ln2)))
	k := uint64(math.Max(1, math.Round((float64(m)/float64(n))*math.Ln2)))

	return &Filter{
		bits: make([]uint64, (m+63)/64),
		m:    m,
		k:    k,
	}
}

func (f *Filter) hashes(data []byte) (uint64, uint64) {
	h := fnv.New64a()
	_, _ = h.Write(data)
	h1 := h.Sum64()
	_, _ = h.Write([]byte{0x1f})
	h2 := h.Sum64()
	return h1, h2
}

// Add inserts an item.
func (f *Filter) Add(item []byte) {
	h1, h2 := f.hashes(item)
	for i := uint64(0); i < f.k; i++ {
		idx := (h1 + i*h2) % f.m
		f.bits[idx/64] |= 1 << (idx % 64)
	}
}

// Contains reports possible membership. False positives possible, false negatives impossible.
func (f *Filter) Contains(item []byte) bool {
	h1, h2 := f.hashes(item)
	for i := uint64(0); i < f.k; i++ {
		idx := (h1 + i*h2) % f.m
		if f.bits[idx/64]&(1<<(idx%64)) == 0 {
			return false
		}
	}
	return true
}

using System;
using System.Collections;
using System.Security.Cryptography;
using System.Text;

// Classic Bloom filter using double hashing: h_i(x) = h1(x) + i*h2(x).
public sealed class BloomFilter
{
    private readonly BitArray _bits;
    private readonly int _m; // number of bits
    private readonly int _k; // number of hashes

    private BloomFilter(int m, int k)
    {
        _m = m;
        _k = k;
        _bits = new BitArray(m);
    }

    // Build a filter sized for n items and target false-positive rate p.
    public static BloomFilter ForCapacity(int n, double p)
    {
        var m = (int)Math.Ceiling(-(n * Math.Log(p)) / (Math.Log(2) * Math.Log(2)));
        var k = Math.Max(1, (int)Math.Round(m / (double)n * Math.Log(2)));
        return new BloomFilter(m, k);
    }

    public void Add(string item)
    {
        var (h1, h2) = Hashes(item);
        for (var i = 0UL; i < (ulong)_k; i++)
        {
            _bits[(int)((h1 + i * h2) % (ulong)_m)] = true;
        }
    }

    // Contains reports possible membership.
    // False positives are possible, false negatives are not.
    public bool Contains(string item)
    {
        var (h1, h2) = Hashes(item);
        for (var i = 0UL; i < (ulong)_k; i++)
        {
            if (!_bits[(int)((h1 + i * h2) % (ulong)_m)])
            {
                return false;
            }
        }
        return true;
    }

    // One 128-bit digest split into two independent 64-bit hashes.
    private static (ulong H1, ulong H2) Hashes(string item)
    {
        var digest = MD5.HashData(Encoding.UTF8.GetBytes(item));
        var h1 = BitConverter.ToUInt64(digest, 0);
        var h2 = BitConverter.ToUInt64(digest, 8) | 1UL; // odd h2 improves bit spread
        return (h1, h2);
    }
}

// Example:
// var bf = BloomFilter.ForCapacity(n: 1_000_000, p: 0.01);
// bf.Add("[email protected]");
// bf.Contains("[email protected]"); // true
// bf.Contains("[email protected]");   // almost certainly false

from __future__ import annotations

import hashlib
import math

class BloomFilter:
    """Classic Bloom filter using double hashing: h_i(x) = h1(x) + i*h2(x)."""

    __slots__ = ("m", "k", "_bits")

    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        # bytearray as a packed bitset: 8 bits per byte
        self._bits = bytearray((m + 7) // 8)

    @classmethod
    def for_capacity(cls, n: int, p: float) -> "BloomFilter":
        """Size the filter for n items and target false-positive rate p."""
        m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))
        k = max(1, round(m / n * math.log(2)))
        return cls(m, k)

    def add(self, item: bytes) -> None:
        for idx in self._indexes(item):
            self._bits[idx >> 3] |= 1 << (idx & 7)

    def __contains__(self, item: bytes) -> bool:
        """False positives are possible, false negatives are not."""
        return all(
            self._bits[idx >> 3] & (1 << (idx & 7))
            for idx in self._indexes(item)
        )

    def _indexes(self, item: bytes):
        # One 128-bit digest split into two independent 64-bit hashes
        digest = hashlib.blake2b(item, digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1  # odd h2 improves bit spread

        for i in range(self.k):
            yield (h1 + i * h2) % self.m

# Example:
# bf = BloomFilter.for_capacity(n=1_000_000, p=0.01)
# bf.add(b"[email protected]")
# b"[email protected]" in bf  # True
# b"[email protected]" in bf    # almost certainly False