Linear Probing:
  Capacidade: 8
  hash("gato")=2, hash("rato")=2, hash("pato")=2

  Inserir "gato":  posição 2 livre → insere
  +---+---+-------+---+---+---+---+---+
  |   |   | gato  |   |   |   |   |   |
  +---+---+-------+---+---+---+---+---+

  Inserir "rato":  posição 2 ocupada → probe → posição 3 livre → insere
  +---+---+-------+-------+---+---+---+---+
  |   |   | gato  | rato  |   |   |   |   |
  +---+---+-------+-------+---+---+---+---+

  Inserir "pato":  posição 2,3 ocupadas → probe → posição 4 livre → insere
  +---+---+-------+-------+-------+---+---+---+
  |   |   | gato  | rato  | pato  |   |   |   |
  +---+---+-------+-------+-------+---+---+---+

  Buscar "rato": hash=2 → "gato"≠"rato" → probe 3 → "rato" ✓
  Remover "gato": marca como TOMBSTONE (não pode apagar, senão busca de "rato" falha)

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

pub fn HashMap(comptime K: type, comptime V: type) type {
    return struct {
        const Self = @This();

        const Estado = enum { vazio, ocupado, removido };

        const Slot = struct {
            chave: K,
            valor: V,
            estado: Estado,
        };

        slots: []Slot,
        tamanho: usize,
        capacidade: usize,
        allocator: Allocator,

        pub fn init(allocator: Allocator) !Self {
            const cap: usize = 16;
            const slots = try allocator.alloc(Slot, cap);
            for (slots) |*s| s.estado = .vazio;
            return .{
                .slots = slots,
                .tamanho = 0,
                .capacidade = cap,
                .allocator = allocator,
            };
        }

        pub fn deinit(self: *Self) void {
            self.allocator.free(self.slots);
        }

        fn hash(chave: K, cap: usize) usize {
            if (K == []const u8) {
                var h: u64 = 14695981039346656037;
                for (chave) |c| {
                    h ^= c;
                    h *%= 1099511628211;
                }
                return @intCast(h % cap);
            } else {
                const val: u64 = @bitCast(@as(i64, chave));
                return @intCast((val *% 2654435761) % cap);
            }
        }

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

        /// Insere ou atualiza — O(1) amortizado.
        pub fn put(self: *Self, chave: K, valor: V) !void {
            if ((self.tamanho + 1) * 2 >= self.capacidade) {
                try self.redimensionar();
            }

            var idx = hash(chave, self.capacidade);
            var primeiro_removido: ?usize = null;

            while (true) {
                switch (self.slots[idx].estado) {
                    .vazio => {
                        const pos = primeiro_removido orelse idx;
                        self.slots[pos] = .{ .chave = chave, .valor = valor, .estado = .ocupado };
                        self.tamanho += 1;
                        return;
                    },
                    .removido => {
                        if (primeiro_removido == null) primeiro_removido = idx;
                    },
                    .ocupado => {
                        if (chavesIguais(self.slots[idx].chave, chave)) {
                            self.slots[idx].valor = valor;
                            return;
                        }
                    },
                }
                idx = (idx + 1) % self.capacidade;
            }
        }

        /// Busca — O(1) amortizado.
        pub fn get(self: *const Self, chave: K) ?V {
            var idx = hash(chave, self.capacidade);
            var tentativas: usize = 0;
            while (tentativas < self.capacidade) : (tentativas += 1) {
                switch (self.slots[idx].estado) {
                    .vazio => return null,
                    .ocupado => {
                        if (chavesIguais(self.slots[idx].chave, chave))
                            return self.slots[idx].valor;
                    },
                    .removido => {},
                }
                idx = (idx + 1) % self.capacidade;
            }
            return null;
        }

        /// Remove — O(1) amortizado.
        pub fn delete(self: *Self, chave: K) ?V {
            var idx = hash(chave, self.capacidade);
            var tentativas: usize = 0;
            while (tentativas < self.capacidade) : (tentativas += 1) {
                switch (self.slots[idx].estado) {
                    .vazio => return null,
                    .ocupado => {
                        if (chavesIguais(self.slots[idx].chave, chave)) {
                            const valor = self.slots[idx].valor;
                            self.slots[idx].estado = .removido;
                            self.tamanho -= 1;
                            return valor;
                        }
                    },
                    .removido => {},
                }
                idx = (idx + 1) % self.capacidade;
            }
            return null;
        }

        fn redimensionar(self: *Self) !void {
            const nova_cap = self.capacidade * 2;
            const novos_slots = try self.allocator.alloc(Slot, nova_cap);
            for (novos_slots) |*s| s.estado = .vazio;

            const antigos = self.slots;
            const cap_antiga = self.capacidade;
            self.slots = novos_slots;
            self.capacidade = nova_cap;
            self.tamanho = 0;

            for (antigos[0..cap_antiga]) |slot| {
                if (slot.estado == .ocupado) {
                    try self.put(slot.chave, slot.valor);
                }
            }
            self.allocator.free(antigos);
        }
    };
}

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

    var mapa = try HashMap([]const u8, i32).init(allocator);
    defer mapa.deinit();

    try mapa.put("x", 10);
    try mapa.put("y", 20);
    try mapa.put("z", 30);
    try mapa.put("w", 40);

    try stdout.print("x={?d}, y={?d}, z={?d}\n", .{ mapa.get("x"), mapa.get("y"), mapa.get("z") });

    _ = mapa.delete("y");
    try stdout.print("Após remover y: {?d}\n", .{mapa.get("y")});
    try stdout.print("z ainda existe: {?d}\n", .{mapa.get("z")});
    try stdout.print("Tamanho: {d}\n", .{mapa.tamanho});
}