std.HashMap — Tabela Hash de Alto Desempenho
O std.HashMap é a implementação principal de tabela hash na biblioteca padrão do Zig. Ele utiliza open addressing com Robin Hood hashing para oferecer excelente desempenho em operações de busca, inserção e remoção. Diferente do ArrayHashMap, não garante nenhuma ordem de iteração, mas oferece desempenho superior em operações de lookup.
Visão Geral
const std = @import("std");
const HashMap = std.HashMap;
Tipo e Assinatura
pub fn HashMap(
comptime K: type,
comptime V: type,
comptime Context: type,
comptime max_load_percentage: u64,
) type
Para uso simplificado, utilize std.AutoHashMap que configura o contexto e o fator de carga automaticamente:
pub fn AutoHashMap(comptime K: type, comptime V: type) type
O AutoHashMap usa a função de hash padrão do Zig, que é uma implementação otimizada de Wyhash.
Funções Principais
Criação e Destruição
// Cria um mapa vazio
pub fn init(allocator: Allocator) AutoHashMap(K, V)
// Libera toda a memória
pub fn deinit(self: *Self) void
Inserção e Acesso
// Insere ou atualiza
pub fn put(self: *Self, key: K, value: V) Allocator.Error!void
// Busca valor pela chave
pub fn get(self: Self, key: K) ?V
// Busca ponteiro para o valor
pub fn getPtr(self: *Self, key: K) ?*V
// Insere se não existe, retorna entrada existente ou nova
pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult
// Verifica existência
pub fn contains(self: Self, key: K) bool
// Número de elementos
pub fn count(self: Self) usize
Remoção
// Remove a chave e retorna o valor, ou null
pub fn fetchRemove(self: *Self, key: K) ?KV
// Remove a chave (retorna bool)
pub fn remove(self: *Self, key: K) bool
Iteração
// Retorna um iterador sobre entradas
pub fn iterator(self: Self) Iterator
// Retorna iterador sobre chaves
pub fn keyIterator(self: Self) KeyIterator
// Retorna iterador sobre valores
pub fn valueIterator(self: Self) ValueIterator
Exemplo 1: Cache de Resultados com HashMap
const std = @import("std");
fn fibonacci(n: u64, cache: *std.AutoHashMap(u64, u64)) !u64 {
if (n <= 1) return n;
if (cache.get(n)) |resultado| {
return resultado;
}
const resultado = try fibonacci(n - 1, cache) + try fibonacci(n - 2, cache);
try cache.put(n, resultado);
return resultado;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var cache = std.AutoHashMap(u64, u64).init(allocator);
defer cache.deinit();
const stdout = std.io.getStdOut().writer();
const valores = [_]u64{ 10, 20, 30, 40, 50 };
for (valores) |n| {
const resultado = try fibonacci(n, &cache);
try stdout.print("fibonacci({d}) = {d}\n", .{ n, resultado });
}
try stdout.print("Entradas no cache: {d}\n", .{cache.count()});
}
Exemplo 2: Índice Invertido de Documentos
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Mapa de caractere para contagem
var frequencia = std.AutoHashMap(u8, u32).init(allocator);
defer frequencia.deinit();
const texto = "abracadabra";
for (texto) |c| {
const entry = try frequencia.getOrPut(c);
if (entry.found_existing) {
entry.value_ptr.* += 1;
} else {
entry.value_ptr.* = 1;
}
}
const stdout = std.io.getStdOut().writer();
try stdout.print("Frequência de caracteres em '{s}':\n", .{texto});
var it = frequencia.iterator();
while (it.next()) |entry| {
try stdout.print(" '{c}': {d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
}
}
Exemplo 3: Agrupamento com getOrPut
const std = @import("std");
const Pessoa = struct {
nome: []const u8,
cidade: []const u8,
idade: u32,
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const pessoas = [_]Pessoa{
.{ .nome = "Ana", .cidade = "SP", .idade = 25 },
.{ .nome = "Bruno", .cidade = "RJ", .idade = 30 },
.{ .nome = "Carla", .cidade = "SP", .idade = 28 },
.{ .nome = "Diego", .cidade = "RJ", .idade = 35 },
.{ .nome = "Eva", .cidade = "MG", .idade = 22 },
};
// Agrupa contagem por cidade
var por_cidade = std.AutoHashMap([]const u8, u32).init(allocator);
defer por_cidade.deinit();
for (pessoas) |p| {
const entry = try por_cidade.getOrPut(p.cidade);
if (entry.found_existing) {
entry.value_ptr.* += 1;
} else {
entry.value_ptr.* = 1;
}
}
const stdout = std.io.getStdOut().writer();
try stdout.writeAll("Pessoas por cidade:\n");
var it = por_cidade.iterator();
while (it.next()) |entry| {
try stdout.print(" {s}: {d}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
}
}
Padrões Comuns
Hash Customizado
Para tipos personalizados como chaves, implemente um contexto com hash e eql:
const Ponto = struct { x: i32, y: i32 };
const PontoContext = struct {
pub fn hash(self: @This(), p: Ponto) u64 {
_ = self;
var h = std.hash.Wyhash.init(0);
h.update(std.mem.asBytes(&p.x));
h.update(std.mem.asBytes(&p.y));
return h.final();
}
pub fn eql(self: @This(), a: Ponto, b: Ponto) bool {
_ = self;
return a.x == b.x and a.y == b.y;
}
};
var mapa = std.HashMap(Ponto, []const u8, PontoContext, 80).init(allocator);
Módulos Relacionados
- std.ArrayHashMap — HashMap com ordem de inserção
- std.StringHashMap — HashMap para chaves string
- std.mem.Allocator — Interface de alocação
- std.hash — Funções de hash