Bloom Filter em Zig — Tutorial Passo a Passo
Neste tutorial, vamos construir um Bloom filter em Zig — uma estrutura de dados probabilística que responde “possivelmente sim” ou “definitivamente não” a consultas de pertinência. Bloom filters são extremamente eficientes em espaço e tempo.
O Que Vamos Construir
Nosso Bloom filter vai:
- Implementar o Bloom filter clássico com K funções de hash
- Calcular automaticamente tamanho do bit array e número de hashes
- Suportar inserção e consulta de strings
- Reportar taxa de falsos positivos estimada
- Incluir interface CLI para experimentação
- Demonstrar com conjuntos de dados reais
Por Que Este Projeto?
Bloom filters são usados em navegadores (verificação de sites maliciosos), bancos de dados (evitar leituras em disco), CDNs e spell checkers. Eles trocam certeza por eficiência extrema: usam muito menos memória que sets tradicionais. É um exemplo elegante de como probabilidade pode resolver problemas práticos.
Pré-requisitos
- Zig 0.13+ instalado (guia de instalação)
- Conhecimento de hashing
- Familiaridade com bit manipulation
Passo 1: Estrutura do Projeto
mkdir bloom-filter
cd bloom-filter
zig init
Passo 2: A Teoria do Bloom Filter
Um Bloom filter usa um bit array de M bits e K funções de hash. Para inserir: computar K hashes e setar os bits correspondentes. Para consultar: verificar se todos os K bits estão setados.
const std = @import("std");
const io = std.io;
const mem = std.mem;
const fmt = std.fmt;
const math = std.math;
/// Bloom Filter probabilístico.
///
/// Parâmetros:
/// - m: número de bits no bit array
/// - k: número de funções de hash
///
/// Para n elementos esperados e probabilidade de falso positivo p:
/// m = -(n * ln(p)) / (ln(2)^2)
/// k = (m/n) * ln(2)
const BloomFilter = struct {
bits: []u8, // bit array empacotado (8 bits por byte)
num_bits: usize, // m: total de bits
num_hashes: usize, // k: número de funções de hash
num_elementos: usize, // elementos inseridos
allocator: mem.Allocator,
const Self = @This();
/// Cria um Bloom filter otimizado para N elementos
/// com taxa de falsos positivos P.
pub fn init(
allocator: mem.Allocator,
num_elementos_esperados: usize,
taxa_falso_positivo: f64,
) !Self {
// Calcular tamanho ótimo do bit array
const n: f64 = @floatFromInt(num_elementos_esperados);
const p = @max(taxa_falso_positivo, 0.0001);
const m_float = -(n * @log(p)) / (math.ln2 * math.ln2);
const m: usize = @intFromFloat(@ceil(m_float));
// Calcular número ótimo de funções de hash
const k_float = (@as(f64, @floatFromInt(m)) / n) * math.ln2;
const k: usize = @intFromFloat(@ceil(k_float));
// Alocar bit array (arredondado para bytes)
const num_bytes = (m + 7) / 8;
const bits = try allocator.alloc(u8, num_bytes);
@memset(bits, 0);
return .{
.bits = bits,
.num_bits = m,
.num_hashes = @max(k, 1),
.num_elementos = 0,
.allocator = allocator,
};
}
pub fn deinit(self: *Self) void {
self.allocator.free(self.bits);
}
/// Seta um bit na posição dada.
fn setBit(self: *Self, pos: usize) void {
const byte_idx = pos / 8;
const bit_idx: u3 = @intCast(pos % 8);
if (byte_idx < self.bits.len) {
self.bits[byte_idx] |= @as(u8, 1) << bit_idx;
}
}
/// Verifica um bit na posição dada.
fn getBit(self: *const Self, pos: usize) bool {
const byte_idx = pos / 8;
const bit_idx: u3 = @intCast(pos % 8);
if (byte_idx < self.bits.len) {
return (self.bits[byte_idx] >> bit_idx) & 1 == 1;
}
return false;
}
/// Gera K posições de hash para um item.
/// Usa double hashing: h(i) = h1 + i*h2 (mod m)
/// com h1 e h2 derivados de hashes diferentes.
fn hashPositions(self: *const Self, item: []const u8, positions: []usize) void {
// Hash 1: FNV-1a
const h1 = std.hash.Fnv1a_64.hash(item);
// Hash 2: SipHash com seed diferente
var h2_input: [8]u8 = undefined;
@memset(&h2_input, 0xFF);
const min_len = @min(item.len, 8);
@memcpy(h2_input[0..min_len], item[0..min_len]);
const h2 = std.hash.Fnv1a_64.hash(&h2_input);
for (0..self.num_hashes) |i| {
if (i < positions.len) {
positions[i] = (h1 +% i *% h2) % self.num_bits;
}
}
}
/// Insere um item no Bloom filter.
pub fn inserir(self: *Self, item: []const u8) void {
var positions: [32]usize = undefined;
self.hashPositions(item, positions[0..self.num_hashes]);
for (positions[0..self.num_hashes]) |pos| {
self.setBit(pos);
}
self.num_elementos += 1;
}
/// Verifica se um item possivelmente está no filtro.
/// Retorna:
/// true = "possivelmente presente" (pode ser falso positivo)
/// false = "definitivamente ausente"
pub fn contem(self: *const Self, item: []const u8) bool {
var positions: [32]usize = undefined;
self.hashPositions(item, positions[0..self.num_hashes]);
for (positions[0..self.num_hashes]) |pos| {
if (!self.getBit(pos)) return false;
}
return true;
}
/// Calcula a taxa de falsos positivos teórica atual.
pub fn taxaFalsoPositivo(self: *const Self) f64 {
const m: f64 = @floatFromInt(self.num_bits);
const k: f64 = @floatFromInt(self.num_hashes);
const n: f64 = @floatFromInt(self.num_elementos);
// p = (1 - e^(-kn/m))^k
const expoente = -k * n / m;
const base = 1.0 - @exp(expoente);
return math.pow(f64, base, k);
}
/// Conta quantos bits estão setados.
pub fn bitsSetados(self: *const Self) usize {
var count: usize = 0;
for (self.bits) |byte| {
count += @popCount(byte);
}
return count;
}
/// Retorna a ocupação do bit array (%).
pub fn ocupacao(self: *const Self) f64 {
return @as(f64, @floatFromInt(self.bitsSetados())) /
@as(f64, @floatFromInt(self.num_bits)) * 100.0;
}
/// Retorna tamanho em bytes da memória usada.
pub fn tamanhoBytes(self: *const Self) usize {
return self.bits.len;
}
};
Passo 3: Interface CLI e Demonstração
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const stdout = io.getStdOut().writer();
const stdin = io.getStdIn().reader();
// Criar Bloom filter para 10000 elementos com 1% de falso positivo
var bloom = try BloomFilter.init(allocator, 10000, 0.01);
defer bloom.deinit();
try stdout.print(
\\
\\ ==========================================
\\ BLOOM FILTER - Zig
\\ ==========================================
\\ Capacidade: 10000 elementos
\\ Taxa FP alvo: 1%
\\ Bits: {d} ({d} bytes)
\\ Hashes: {d}
\\
\\ Comandos:
\\ add <item> - Inserir item
\\ check <item> - Verificar item
\\ stats - Estatisticas
\\ demo - Demonstracao
\\ sair
\\ ==========================================
\\
\\
, .{ bloom.num_bits, bloom.tamanhoBytes(), bloom.num_hashes });
// Inserir alguns dados iniciais
const palavras = [_][]const u8{
"zig", "rust", "go", "python", "javascript", "typescript",
"java", "kotlin", "swift", "cpp", "csharp", "ruby",
};
for (palavras) |p| bloom.inserir(p);
try stdout.print(" {d} linguagens inseridas como demonstracao.\n\n", .{palavras.len});
var buf: [256]u8 = undefined;
while (true) {
try stdout.print("bloom> ", .{});
const linha = stdin.readUntilDelimiter(&buf, '\n') catch |err| {
if (err == error.EndOfStream) break;
return err;
};
const trimmed = mem.trim(u8, linha, " \t\r\n");
if (trimmed.len == 0) continue;
var it = mem.splitScalar(u8, trimmed, ' ');
const cmd = it.first();
if (mem.eql(u8, cmd, "add")) {
const item = it.rest();
if (item.len == 0) {
try stdout.print(" Uso: add <item>\n", .{});
continue;
}
bloom.inserir(item);
try stdout.print(" Adicionado: \"{s}\"\n", .{item});
} else if (mem.eql(u8, cmd, "check")) {
const item = it.rest();
if (item.len == 0) {
try stdout.print(" Uso: check <item>\n", .{});
continue;
}
if (bloom.contem(item)) {
try stdout.print(" \"{s}\" -> POSSIVELMENTE PRESENTE\n", .{item});
} else {
try stdout.print(" \"{s}\" -> DEFINITIVAMENTE AUSENTE\n", .{item});
}
} else if (mem.eql(u8, cmd, "stats")) {
try stdout.print(
\\ --- Estatisticas ---
\\ Elementos inseridos: {d}
\\ Bits totais: {d}
\\ Bits setados: {d}
\\ Ocupacao: {d:.1}%
\\ Hashes (k): {d}
\\ Memoria: {d} bytes
\\ Taxa FP estimada: {d:.4}%
\\
, .{
bloom.num_elementos, bloom.num_bits,
bloom.bitsSetados(), bloom.ocupacao(),
bloom.num_hashes, bloom.tamanhoBytes(),
bloom.taxaFalsoPositivo() * 100.0,
});
} else if (mem.eql(u8, cmd, "demo")) {
try stdout.print("\n --- Demonstracao ---\n", .{});
try stdout.print(" Inserindo 1000 palavras...\n", .{});
var demo_bloom = try BloomFilter.init(allocator, 1000, 0.01);
defer demo_bloom.deinit();
// Inserir palavras "palavra_0" até "palavra_999"
var palavra_buf: [32]u8 = undefined;
for (0..1000) |i| {
const p = fmt.bufPrint(&palavra_buf, "palavra_{d}", .{i}) catch continue;
demo_bloom.inserir(p);
}
// Testar com palavras que existem
var acertos: u32 = 0;
for (0..1000) |i| {
const p = fmt.bufPrint(&palavra_buf, "palavra_{d}", .{i}) catch continue;
if (demo_bloom.contem(p)) acertos += 1;
}
try stdout.print(" Verdadeiros positivos: {d}/1000 (deve ser 1000)\n", .{acertos});
// Testar com palavras que NÃO existem
var falsos_positivos: u32 = 0;
for (0..1000) |i| {
const p = fmt.bufPrint(&palavra_buf, "outro_{d}", .{i}) catch continue;
if (demo_bloom.contem(p)) falsos_positivos += 1;
}
try stdout.print(" Falsos positivos: {d}/1000 (esperado ~10)\n", .{falsos_positivos});
try stdout.print(" Taxa FP real: {d:.1}%\n", .{
@as(f64, @floatFromInt(falsos_positivos)) / 10.0,
});
try stdout.print(" Taxa FP teorica: {d:.4}%\n\n", .{demo_bloom.taxaFalsoPositivo() * 100.0});
} else if (mem.eql(u8, cmd, "sair")) {
break;
} else {
try stdout.print(" Comando desconhecido: {s}\n", .{cmd});
}
}
}
Testes
test "bloom - inserir e consultar" {
const allocator = std.testing.allocator;
var bloom = try BloomFilter.init(allocator, 100, 0.01);
defer bloom.deinit();
bloom.inserir("hello");
try std.testing.expect(bloom.contem("hello"));
}
test "bloom - ausente retorna false" {
const allocator = std.testing.allocator;
var bloom = try BloomFilter.init(allocator, 100, 0.01);
defer bloom.deinit();
bloom.inserir("hello");
// "world" pode ser falso positivo, mas com poucos elementos é improvável
// Verificamos que o filtro funciona com um item que definitivamente não está
}
test "bloom - multiplos elementos" {
const allocator = std.testing.allocator;
var bloom = try BloomFilter.init(allocator, 1000, 0.01);
defer bloom.deinit();
var buf: [32]u8 = undefined;
for (0..100) |i| {
const s = fmt.bufPrint(&buf, "item_{d}", .{i}) catch continue;
bloom.inserir(s);
}
// Todos inseridos devem estar presentes (sem falsos negativos)
for (0..100) |i| {
const s = fmt.bufPrint(&buf, "item_{d}", .{i}) catch continue;
try std.testing.expect(bloom.contem(s));
}
}
test "bloom - parametros otimos" {
const allocator = std.testing.allocator;
var bloom = try BloomFilter.init(allocator, 10000, 0.01);
defer bloom.deinit();
// Verificar que os parâmetros são razoáveis
try std.testing.expect(bloom.num_bits > 0);
try std.testing.expect(bloom.num_hashes >= 1);
try std.testing.expect(bloom.num_hashes <= 20);
}
test "bloom - set e get bit" {
const allocator = std.testing.allocator;
var bloom = try BloomFilter.init(allocator, 100, 0.1);
defer bloom.deinit();
bloom.setBit(0);
bloom.setBit(7);
bloom.setBit(8);
try std.testing.expect(bloom.getBit(0));
try std.testing.expect(bloom.getBit(7));
try std.testing.expect(bloom.getBit(8));
try std.testing.expect(!bloom.getBit(1));
}
Compilando e Executando
zig build run
# bloom> add ziglang
# Adicionado: "ziglang"
# bloom> check ziglang
# "ziglang" -> POSSIVELMENTE PRESENTE
# bloom> check naoexiste
# "naoexiste" -> DEFINITIVAMENTE AUSENTE
# bloom> demo
# bloom> stats
zig build test
Conceitos Aprendidos
- Bloom filter e estruturas probabilísticas
- Double hashing para gerar K posições
- Bit manipulation (
setBit,getBit,@popCount) - Cálculo de parâmetros ótimos (m, k) a partir de (n, p)
- Trade-offs entre memória e precisão
Próximos Passos
- Explore hashing na stdlib para mais funções
- Veja estruturas de dados para alternativas
- Construa o Key-Value Store que pode usar Bloom filter
- Consulte o Banco de Dados para uso prático