Hash Set com 8 buckets:

Bucket  Conteúdo
  0     → null
  1     → ["banana"] → null
  2     → null
  3     → ["maçã"] → ["uva"] → null   (colisão)
  4     → null
  5     → ["pera"] → null
  6     → null
  7     → null

Operações:
  inserir("manga")  → hash("manga") % 8 = 2 → bucket[2]
  contem("maçã")    → hash("maçã") % 8 = 3  → encontrado!
  contem("kiwi")    → hash("kiwi") % 8 = 6  → não encontrado

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

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

/// Hash Set genérico com encadeamento separado.
pub fn HashSet(comptime T: type) type {
    return struct {
        const Self = @This();

        const No = struct {
            valor: T,
            proximo: ?*No,
        };

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

        pub fn init(allocator: Allocator) !Self {
            const cap: usize = 16;
            const buckets = try allocator.alloc(?*No, 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) |no| {
                    const prox = no.proximo;
                    self.allocator.destroy(no);
                    atual = prox;
                }
            }
            self.allocator.free(self.buckets);
        }

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

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

        /// Insere um valor no conjunto. Retorna true se foi inserido (novo).
        pub fn inserir(self: *Self, valor: T) !bool {
            if (self.tamanho * 4 >= self.capacidade * 3) {
                try self.redimensionar();
            }

            const idx = self.hash(valor);

            // Verifica se já existe
            var atual = self.buckets[idx];
            while (atual) |no| {
                if (iguais(no.valor, valor)) return false;
                atual = no.proximo;
            }

            // Insere novo nó
            const novo = try self.allocator.create(No);
            novo.* = .{ .valor = valor, .proximo = self.buckets[idx] };
            self.buckets[idx] = novo;
            self.tamanho += 1;
            return true;
        }

        /// Verifica se o valor pertence ao conjunto — O(1) amortizado.
        pub fn contem(self: *const Self, valor: T) bool {
            const idx = self.hash(valor);
            var atual = self.buckets[idx];
            while (atual) |no| {
                if (iguais(no.valor, valor)) return true;
                atual = no.proximo;
            }
            return false;
        }

        /// Remove um valor do conjunto — O(1) amortizado.
        pub fn remover(self: *Self, valor: T) bool {
            const idx = self.hash(valor);
            var ponteiro: *?*No = &self.buckets[idx];

            while (ponteiro.*) |no| {
                if (iguais(no.valor, valor)) {
                    ponteiro.* = no.proximo;
                    self.allocator.destroy(no);
                    self.tamanho -= 1;
                    return true;
                }
                ponteiro = &no.proximo;
            }
            return false;
        }

        /// União com outro conjunto.
        pub fn uniao(self: *Self, outro: *const Self) !void {
            for (outro.buckets) |bucket| {
                var atual = bucket;
                while (atual) |no| {
                    _ = try self.inserir(no.valor);
                    atual = no.proximo;
                }
            }
        }

        /// Retorna os valores como slice (caller libera).
        pub fn paraSlice(self: *const Self, allocator: Allocator) ![]T {
            var resultado = try allocator.alloc(T, self.tamanho);
            var i: usize = 0;
            for (self.buckets) |bucket| {
                var atual = bucket;
                while (atual) |no| {
                    resultado[i] = no.valor;
                    i += 1;
                    atual = no.proximo;
                }
            }
            return resultado;
        }

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

            const antigos = self.buckets;
            const cap_antiga = self.capacidade;
            self.buckets = novos;
            self.capacidade = nova_cap;

            for (antigos[0..cap_antiga]) |bucket| {
                var atual = bucket;
                while (atual) |no| {
                    const prox = no.proximo;
                    const novo_idx = self.hash(no.valor);
                    no.proximo = self.buckets[novo_idx];
                    self.buckets[novo_idx] = no;
                    atual = prox;
                }
            }
            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 frutas = try HashSet([]const u8).init(allocator);
    defer frutas.deinit();

    // Inserções (duplicatas ignoradas)
    _ = try frutas.inserir("maçã");
    _ = try frutas.inserir("banana");
    _ = try frutas.inserir("uva");
    _ = try frutas.inserir("maçã"); // Duplicata — retorna false
    _ = try frutas.inserir("pera");

    try stdout.print("Tamanho: {d}\n", .{frutas.tamanho});
    try stdout.print("Contém 'maçã': {}\n", .{frutas.contem("maçã")});
    try stdout.print("Contém 'manga': {}\n", .{frutas.contem("manga")});

    // Remoção
    const removido = frutas.remover("banana");
    try stdout.print("Removeu 'banana': {}\n", .{removido});
    try stdout.print("Tamanho após remoção: {d}\n", .{frutas.tamanho});

    // Eliminação de duplicatas de um array
    try stdout.writeAll("\n=== Eliminando Duplicatas ===\n");
    const dados = [_]i32{ 5, 3, 8, 3, 1, 5, 9, 1, 8, 7 };
    var numeros = try HashSet(i32).init(allocator);
    defer numeros.deinit();

    for (dados) |n| {
        _ = try numeros.inserir(n);
    }
    try stdout.print("Original: {d} elementos\n", .{dados.len});
    try stdout.print("Únicos:   {d} elementos\n", .{numeros.tamanho});
}