Skip to main content

Hash Map | GetHashCode(), Equals() | Algoritmo e Estrutura de dados

  • Hash Map | GetHashCode(), Equals() | Algoritmo e Estrutura de dados

Definição​

  • É um dicitionary. [("augusto", "azul"), ("bernardo", "vermelho")]
  • Na maioria das vezes a complexidade temporal é O(n)
  • Hash Function -> pega a chave e faz alguma operação com ela para transformar em um número. Quando você solicita pela chave ela pega e converte para saber onde está
info

No C#, o dictionary é o equivalente ao hash map.

Explicação no C#

Quando você usa tipos personalizados como chave em um Dictionary<TKey, TValue> (ou qualquer estrutura baseada em hash), o .NET precisa de duas coisas para saber onde guardar os valores e como comparar chaves:

  1. GetHashCode() — para calcular em qual “balde” do dicionário o item será colocado.
  2. Equals() — para verificar se duas chaves são “iguais” quando estão no mesmo balde.

Se essas duas operações não forem corretamente implementadas, o dicionário pode não encontrar um item mesmo que ele esteja lá — o que é um problema grave.

📌 Exemplo: usando um tipo personalizado como chave​

class Pessoa
{
    public string Nome { get; set; }

    // Errado: Não sobrescrevemos GetHashCode e Equals
}
var dicionario = new Dictionary<Pessoa, string>();
dicionario[new Pessoa { Nome = "Maria" }] = "Desenvolvedora";

// Tenta acessar com outra instância com mesmo nome
var chave = new Pessoa { Nome = "Maria" };

bool existe = dicionario.ContainsKey(chave); // ❌ Retorna falso!

Mesmo que o Nome seja o mesmo, o dicionário trata os dois objetos como diferentes, porque ele usa a implementação padrão de GetHashCode() e Equals() — que compara por referência, não por valor.

✅ Solução: sobrescrever Equals e GetHashCode​

class Pessoa
{
    public string Nome { get; set; }

    public override bool Equals(object obj)
    {
        if (obj is Pessoa outra)
            return this.Nome == outra.Nome;

        return false;
    }

    public override int GetHashCode()
    {
        return Nome?.GetHashCode() ?? 0;
    }
}

Agora sim:

var dicionario = new Dictionary<Pessoa, string>();
dicionario[new Pessoa { Nome = "Maria" }] = "Desenvolvedora";

var chave = new Pessoa { Nome = "Maria" };
bool existe = dicionario.ContainsKey(chave); // ✅ Agora funciona!

🧠 Dica arquitetural:​

Se for usar um tipo como chave sem controlar sua lógica de igualdade e hash, pode ser melhor:

  • Torná-lo record (C# 9+), que já implementa Equals e GetHashCode baseado no conteúdo.
public record Pessoa(string Nome);

Esse record já funciona perfeitamente como chave em Dictionary.

Load Factor (Fator de Carga)​

O load factor mede o nível de ocupação da tabela hash.

📌 Definição formal:​

Load Factor = (número de elementos) ÷ (número de baldes disponíveis)

Exemplo simples:​

  • Suponha que a tabela hash tenha 100 posições (baldes).
  • E você inseriu 60 elementos.
  • Load Factor = 60 / 100 = 0.6 (ou 60%)

🧠 Por que importa?​

Um load factor baixo:

  • Menos colisões.
  • Mais memória usada.
  • Acesso mais rápido.

Um load factor alto:

  • Mais colisões.
  • Mais tempo de acesso (porque mais comparações são feitas por balde).
  • Melhor uso da memória, mas com perda de performance.

✅ No Dictionary<TKey, TValue> do .NET:​

  • O Dictionary tem um tamanho interno (capacidade) que aumenta automaticamente quando o load factor passa de um certo limite (geralmente próximo de 0.75).
  • Quando isso acontece, ele rehash — ou seja, recalcula o hash de todas as chaves e redistribui nos novos baldes.

Hash Collisions (Colisões de Hash)​

Uma colisão ocorre quando duas chaves diferentes geram o mesmo hash code e são colocadas no mesmo balde.

Exemplo:​

var dicionario = new Dictionary<int, string>();
dicionario[1] = "um";
dicionario[101] = "cento e um"; // Suponha que 1 e 101 caiam no mesmo balde

🧠 O que o .NET faz?​

  • Usa encadeamento aberto (em versões antigas) ou endereçamento aberto com sondagem (versões mais recentes do .NET).
  • Ou seja, dentro de cada balde, ele mantém uma estrutura para comparar as chaves, usando Equals.

🚨 Impacto das colisões:​

  • Se houver muitas colisões, o dicionário se comporta mais como uma lista encadeada — perde o tempo constante O(1) e pode ir para O(n) no pior caso.
  • É por isso que é essencial ter uma boa função de hash e manter o load factor em um nível saudável.