Hash Table com encadeamento (16 buckets):

Bucket  Conteúdo
  0     → null
  1     → null
  2     → ["banana":5] → null
  3     → null
  4     → ["uva":3] → ["pera":8] → null   (colisão!)
  5     → null
  ...
 10     → ["maçã":2] → null
  ...

hash("maçã") % 16 = 10
hash("banana") % 16 = 2
hash("uva") % 16 = 4
hash("pera") % 16 = 4   ← colisão com "uva", encadeia

Fator de carga = n/m = itens/buckets
Redimensiona quando fator > 0.75

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

/// Hash Table com encadeamento separado.
pub fn HashTable(comptime K: type, comptime V: type) type {
    return struct {
        const Self = @This();

        const Entrada = struct {
            chave: K,
            valor: V,
            proximo: ?*Entrada,
        };

        buckets: []?*Entrada,
        tamanho: usize,
        capacidade: usize,
        allocator: Allocator,

        pub fn init(allocator: Allocator) !Self {
            const cap: usize = 16;
            const buckets = try allocator.alloc(?*Entrada, cap);
            @memset(buckets, null);
            return .{
                .buckets = buckets,
                .tamanho = 0,
                .capacidade = cap,
                .allocator = allocator,
            };
        }

        pub fn deinit(self: *Self) void {
            for (self.buckets) |bucket| {
                var atual = bucket;
                while (atual) |entrada| {
                    const prox = entrada.proximo;
                    self.allocator.destroy(entrada);
                    atual = prox;
                }
            }
            self.allocator.free(self.buckets);
        }

        fn hash(self: *const Self, chave: K) usize {
            if (K == []const u8) {
                var h: u64 = 5381;
                for (chave) |c| {
                    h = ((h << 5) +% h) +% c;
                }
                return @intCast(h % self.capacidade);
            } else {
                return @intCast(@as(u64, @bitCast(@as(i64, chave))) % self.capacidade);
            }
        }

        /// Insere ou atualiza um par chave-valor — O(1) amortizado.
        pub fn inserir(self: *Self, chave: K, valor: V) !void {
            if (self.tamanho * 4 >= self.capacidade * 3) {
                try self.redimensionar();
            }

            const idx = self.hash(chave);

            // Verifica se a chave já existe
            var atual = self.buckets[idx];
            while (atual) |entrada| {
                if (chavesIguais(entrada.chave, chave)) {
                    entrada.valor = valor;
                    return;
                }
                atual = entrada.proximo;
            }

            // Nova entrada
            const nova = try self.allocator.create(Entrada);
            nova.* = .{ .chave = chave, .valor = valor, .proximo = self.buckets[idx] };
            self.buckets[idx] = nova;
            self.tamanho += 1;
        }

        /// Busca por chave — O(1) amortizado.
        pub fn buscar(self: *const Self, chave: K) ?V {
            const idx = self.hash(chave);
            var atual = self.buckets[idx];
            while (atual) |entrada| {
                if (chavesIguais(entrada.chave, chave)) return entrada.valor;
                atual = entrada.proximo;
            }
            return null;
        }

        /// Remove por chave — O(1) amortizado.
        pub fn remover(self: *Self, chave: K) ?V {
            const idx = self.hash(chave);
            var anterior: ?*?*Entrada = null;
            var ponteiro: *?*Entrada = &self.buckets[idx];

            _ = anterior;
            while (ponteiro.*) |entrada| {
                if (chavesIguais(entrada.chave, chave)) {
                    const valor = entrada.valor;
                    ponteiro.* = entrada.proximo;
                    self.allocator.destroy(entrada);
                    self.tamanho -= 1;
                    return valor;
                }
                ponteiro = &entrada.proximo;
            }
            return null;
        }

        pub fn contem(self: *const Self, chave: K) bool {
            return self.buscar(chave) != null;
        }

        fn chavesIguais(a: K, b: K) bool {
            if (K == []const u8) return std.mem.eql(u8, a, b);
            return a == b;
        }

        fn redimensionar(self: *Self) !void {
            const nova_cap = self.capacidade * 2;
            const novos_buckets = try self.allocator.alloc(?*Entrada, nova_cap);
            @memset(novos_buckets, null);

            const cap_antiga = self.capacidade;
            const buckets_antigos = self.buckets;

            self.buckets = novos_buckets;
            self.capacidade = nova_cap;

            for (buckets_antigos[0..cap_antiga]) |bucket| {
                var atual = bucket;
                while (atual) |entrada| {
                    const prox = entrada.proximo;
                    const novo_idx = self.hash(entrada.chave);
                    entrada.proximo = self.buckets[novo_idx];
                    self.buckets[novo_idx] = entrada;
                    atual = prox;
                }
            }

            self.allocator.free(buckets_antigos);
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Hash table string → inteiro
    var tabela = try HashTable([]const u8, i32).init(allocator);
    defer tabela.deinit();

    try tabela.inserir("maçã", 5);
    try tabela.inserir("banana", 3);
    try tabela.inserir("uva", 8);
    try tabela.inserir("pera", 2);

    try stdout.print("maçã: {?d}\n", .{tabela.buscar("maçã")});
    try stdout.print("uva: {?d}\n", .{tabela.buscar("uva")});
    try stdout.print("manga: {?d}\n", .{tabela.buscar("manga")});

    // Atualizar
    try tabela.inserir("maçã", 10);
    try stdout.print("maçã (atualizada): {?d}\n", .{tabela.buscar("maçã")});

    // Remover
    const removido = tabela.remover("banana");
    try stdout.print("Removido banana: {?d}\n", .{removido});
    try stdout.print("Tamanho: {d}\n", .{tabela.tamanho});
}