Bloom Filter com 16 bits e 3 funções hash:

Inserindo "maçã":
  h1("maçã") % 16 = 2   → bit[2]  = 1
  h2("maçã") % 16 = 7   → bit[7]  = 1
  h3("maçã") % 16 = 11  → bit[11] = 1

Inserindo "banana":
  h1("banana") % 16 = 1  → bit[1]  = 1
  h2("banana") % 16 = 7  → bit[7]  = 1  (já era 1)
  h3("banana") % 16 = 14 → bit[14] = 1

Array de bits:  0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0
                  ^b^m          ^ambos    ^m    ^b

Consulta "uva":
  h1("uva") % 16 = 2   → bit[2]  = 1 ✓
  h2("uva") % 16 = 5   → bit[5]  = 0 ✗  → NÃO pertence (certeza!)

Consulta "kiwi":
  h1("kiwi") % 16 = 1  → bit[1]  = 1 ✓
  h2("kiwi") % 16 = 7  → bit[7]  = 1 ✓
  h3("kiwi") % 16 = 11 → bit[11] = 1 ✓
  → POSSIVELMENTE pertence (pode ser falso positivo!)

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Bloom Filter com k funções hash baseadas em double hashing.
pub fn BloomFilter(comptime tamanho_bits: usize) type {
    const num_palavras = (tamanho_bits + 63) / 64;

    return struct {
        const Self = @This();

        bits: [num_palavras]u64,
        num_hashes: u8,
        contagem_insercoes: usize,

        pub fn init(num_hashes: u8) Self {
            return .{
                .bits = [_]u64{0} ** num_palavras,
                .num_hashes = num_hashes,
                .contagem_insercoes = 0,
            };
        }

        fn hashPrimario(dados: []const u8) u64 {
            // FNV-1a hash
            var h: u64 = 14695981039346656037;
            for (dados) |byte| {
                h ^= byte;
                h *%= 1099511628211;
            }
            return h;
        }

        fn hashSecundario(dados: []const u8) u64 {
            // djb2 hash
            var h: u64 = 5381;
            for (dados) |byte| {
                h = ((h << 5) +% h) +% byte;
            }
            return h;
        }

        fn obterBit(self: *const Self, pos: usize) bool {
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            return (self.bits[palavra] >> bit) & 1 == 1;
        }

        fn definirBit(self: *Self, pos: usize) void {
            const palavra = pos / 64;
            const bit: u6 = @intCast(pos % 64);
            self.bits[palavra] |= @as(u64, 1) << bit;
        }

        /// Insere um elemento no filtro.
        pub fn inserir(self: *Self, dados: []const u8) void {
            const h1 = hashPrimario(dados);
            const h2 = hashSecundario(dados);

            for (0..self.num_hashes) |i| {
                const pos = (h1 +% @as(u64, @intCast(i)) *% h2) % tamanho_bits;
                self.definirBit(@intCast(pos));
            }
            self.contagem_insercoes += 1;
        }

        /// Verifica se um elemento POSSIVELMENTE pertence ao conjunto.
        /// Retorna false → certeza que NÃO pertence.
        /// Retorna true  → POSSIVELMENTE pertence (pode ser falso positivo).
        pub fn possivelmenteContem(self: *const Self, dados: []const u8) bool {
            const h1 = hashPrimario(dados);
            const h2 = hashSecundario(dados);

            for (0..self.num_hashes) |i| {
                const pos = (h1 +% @as(u64, @intCast(i)) *% h2) % tamanho_bits;
                if (!self.obterBit(@intCast(pos))) return false;
            }
            return true;
        }

        /// Estimativa da taxa de falsos positivos atual.
        pub fn taxaFalsosPositivos(self: *const Self) f64 {
            const n: f64 = @floatFromInt(self.contagem_insercoes);
            const m: f64 = @floatFromInt(tamanho_bits);
            const k: f64 = @floatFromInt(self.num_hashes);
            // p ≈ (1 - e^(-kn/m))^k
            const expoente = -k * n / m;
            return std.math.pow(f64, 1.0 - @exp(expoente), k);
        }

        /// Conta bits ativos.
        pub fn bitsAtivos(self: *const Self) usize {
            var total: usize = 0;
            for (self.bits) |palavra| {
                total += @popCount(palavra);
            }
            return total;
        }

        /// Reseta o filtro.
        pub fn limpar(self: *Self) void {
            @memset(&self.bits, 0);
            self.contagem_insercoes = 0;
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Bloom Filter com 1024 bits e 5 funções hash
    var filtro = BloomFilter(1024).init(5);

    // Insere URLs visitadas
    const urls_visitadas = [_][]const u8{
        "https://ziglang.org",
        "https://ziglang.com.br",
        "https://github.com/ziglang/zig",
        "https://ziglearn.org",
        "https://zig.news",
    };

    try stdout.writeAll("=== Inserindo URLs ===\n");
    for (urls_visitadas) |url| {
        filtro.inserir(url);
        try stdout.print("  Inserido: {s}\n", .{url});
    }

    // Consultas
    try stdout.writeAll("\n=== Consultas ===\n");
    const urls_teste = [_][]const u8{
        "https://ziglang.org",         // Deve retornar true
        "https://rust-lang.org",       // Deve retornar false
        "https://ziglang.com.br",      // Deve retornar true
        "https://golang.org",          // Deve retornar false
        "https://example.com",         // Provavelmente false
    };

    for (urls_teste) |url| {
        const resultado = filtro.possivelmenteContem(url);
        const status: []const u8 = if (resultado) "possivelmente sim" else "definitivamente não";
        try stdout.print("  {s:<40} → {s}\n", .{ url, status });
    }

    // Estatísticas
    try stdout.print("\n=== Estatísticas ===\n", .{});
    try stdout.print("  Inserções: {d}\n", .{filtro.contagem_insercoes});
    try stdout.print("  Bits ativos: {d}/1024\n", .{filtro.bitsAtivos()});
    try stdout.print("  Taxa estimada de falsos positivos: {d:.6}\n", .{filtro.taxaFalsosPositivos()});
}