Introdução

Na parte 1 cobrimos Listas e na parte 2 cobrimos Árvores. Agora vamos para uma das estruturas mais usadas em sistemas reais: Hash Tables.

Se você já implementou cache, deduplicação, contadores, indexação, joins, lookup de sessão ou checagem de permissões, provavelmente já dependeu de hash tables.

O objetivo central dessa estrutura é simples: acesso rápido por chave. Em cenários médios, insert, lookup e delete ficam em O(1).

Como nos artigos anteriores, vamos manter a mesma interface base:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

O que é uma Hash Table?

Uma Hash Table armazena dados como pares chave-valor.

Ao invés de percorrer nós (como listas encadeadas) ou comparar em níveis da árvore (como BST/AVL), ela calcula um índice diretamente a partir de uma chave usando uma função de hash.

Fluxo simples:

1. Você fornece uma chave (exemplo: "user:42").
2. A função de hash converte a chave para um hash inteiro.
3. O hash é mapeado para um índice do array (bucket).
4. O dado é inserido/lido naquele bucket.

Visualização de alto nível

flowchart LR
  K["Chave: user:42"] --> H["Função de Hash"]
  H --> M["mod bucketCount"]
  M --> B["Bucket #3"]
  B --> V["(user:42, profile)"]

Por que colisões acontecem

Colisões são inevitáveis porque o espaço de chaves é muito maior que o array de buckets.

Chaves diferentes podem produzir:

• o mesmo hash, ou
• hashes diferentes que caem no mesmo índice após o módulo.

Exemplo:

hash("ab") = 100
hash("ba") = 116

bucketCount = 8

100 % 8 = 4
116 % 8 = 4

As duas vão para bucket[4] -> colisão

Então hash table não é sobre eliminar colisão totalmente. É sobre tratá-las de forma eficiente.

Estratégias para resolução de colisão

As duas abordagens mais comuns são:

1) Separate Chaining

Cada bucket guarda uma coleção (geralmente linked list ou slice) de entries.

bucket[0] -> (a, 10) -> (k, 99)
bucket[1] -> (x, 2)
bucket[2] -> vazio
bucket[3] -> (m, 8) -> (n, 13) -> (p, 21)

Prós:

• simples de implementar
• deleção é direta
• performance degrada de forma gradual

Contras:

• overhead de ponteiros/slices
• localidade de cache pode ser pior dependendo da estrutura

2) Open Addressing

Todos os entries ficam no próprio array. Em colisão, procura outro slot (linear probing, quadratic probing, double hashing).

Prós:

• melhor localidade de cache em muitos cenários
• sem estrutura extra por bucket

Contras:

• deleção é mais complicada (tombstones)
• load factor alto degrada mais rápido

Neste artigo vamos implementar separate chaining, porque é mais simples de ler e raciocinar.

Load factor e resize

Load factor é:

alpha = size / bucketCount

Conforme alpha cresce, colisões aumentam, e o tamanho médio de bucket aumenta.

Estratégia típica:

• definir um limite (por exemplo 0.75)
• quando alpha ultrapassar o limite, criar um array maior (normalmente 2x)
• reinserir todos os entries (rehash)

Esse passo de resize é O(n), mas ele não acontece em toda operação, então a inserção amortizada continua perto de O(1).

Resumo de complexidade

Caso médio (bom hash + load factor controlado):

• Insert: O(1)
• Lookup: O(1)
• Delete: O(1)

Pior caso (todas as chaves colapsam no mesmo bucket):

• Insert: O(n)
• Lookup: O(n)
• Delete: O(n)

Implementação prática em Go (separate chaining)

Abaixo está uma implementação completa com:

• chaves string
• valores genéricos
• resize dinâmico
• update em chaves existentes
• métodos da interface Container

type entry[V any] struct {
  key   string
  value V
}

type HashTable[V any] struct {
  buckets       [][]entry[V]
  size          int
  maxLoadFactor float64
}

func NewHashTable[V any](initialBuckets int) *HashTable[V] {
  if initialBuckets < 8 {
    initialBuckets = 8
  }
  return &HashTable[V]{
    buckets:       make([][]entry[V], initialBuckets),
    maxLoadFactor: 0.75,
  }
}

func (h *HashTable[V]) Empty() bool {
  return h.size == 0
}

func (h *HashTable[V]) Size() int {
  return h.size
}

func (h *HashTable[V]) Clear() {
  h.buckets = make([][]entry[V], len(h.buckets))
  h.size = 0
}

func (h *HashTable[V]) Values() []interface{} {
  values := make([]interface{}, 0, h.size)
  for _, bucket := range h.buckets {
    for _, e := range bucket {
      values = append(values, e.value)
    }
  }
  return values
}

func (h *HashTable[V]) String() string {
  pairs := make([]string, 0, h.size)
  for _, bucket := range h.buckets {
    for _, e := range bucket {
      pairs = append(pairs, fmt.Sprintf("%s=%v", e.key, e.value))
    }
  }
  return fmt.Sprintf("{%s}", strings.Join(pairs, ", "))
}

func (h *HashTable[V]) Put(key string, value V) {
  if float64(h.size+1)/float64(len(h.buckets)) > h.maxLoadFactor {
    h.resize(len(h.buckets) * 2)
  }

  index := h.bucketIndex(key)
  bucket := h.buckets[index]

  // Update de chave existente (size não muda)
  for i := range bucket {
    if bucket[i].key == key {
      bucket[i].value = value
      h.buckets[index] = bucket
      return
    }
  }

  // Insert de nova chave
  h.buckets[index] = append(bucket, entry[V]{key: key, value: value})
  h.size++
}

func (h *HashTable[V]) Get(key string) (V, bool) {
  index := h.bucketIndex(key)
  bucket := h.buckets[index]

  for i := range bucket {
    if bucket[i].key == key {
      return bucket[i].value, true
    }
  }

  var zero V
  return zero, false
}

func (h *HashTable[V]) Remove(key string) bool {
  index := h.bucketIndex(key)
  bucket := h.buckets[index]

  for i := range bucket {
    if bucket[i].key == key {
      // remove trocando com o último (O(1) após lookup)
      last := len(bucket) - 1
      bucket[i] = bucket[last]
      bucket = bucket[:last]
      h.buckets[index] = bucket
      h.size--
      return true
    }
  }

  return false
}

func (h *HashTable[V]) ContainsKey(key string) bool {
  _, ok := h.Get(key)
  return ok
}

func (h *HashTable[V]) Keys() []string {
  keys := make([]string, 0, h.size)
  for _, bucket := range h.buckets {
    for _, e := range bucket {
      keys = append(keys, e.key)
    }
  }
  return keys
}

func (h *HashTable[V]) LoadFactor() float64 {
  if len(h.buckets) == 0 {
    return 0
  }
  return float64(h.size) / float64(len(h.buckets))
}

func (h *HashTable[V]) bucketIndex(key string) int {
  hash := fnv.New64a()
  _, _ = hash.Write([]byte(key))
  return int(hash.Sum64() % uint64(len(h.buckets)))
}

func (h *HashTable[V]) resize(newBucketCount int) {
  oldBuckets := h.buckets
  h.buckets = make([][]entry[V], newBucketCount)
  h.size = 0

  for _, bucket := range oldBuckets {
    for _, e := range bucket {
      h.Put(e.key, e.value)
    }
  }
}

Imports usados por essa implementação:

import (
  "fmt"
  "hash/fnv"
  "strings"
)

Visualização de resize

flowchart TD
  A["size=6, buckets=8, alpha=0.75"] --> B["inserir mais uma chave"]
  B --> C["alpha passa do limite"]
  C --> D["criar novos buckets (16)"]
  D --> E["rehash de todos os entries"]
  E --> F["retomar operações normais"]

Detalhes importantes de implementação

Update de chave existente

Put("k", old) e depois Put("k", new) deve atualizar valor, não duplicar entrada com a mesma chave.

Qualidade da função de hash importa

Funções fracas podem gerar índices muito agrupados e derrubar performance.

Em produção:

• prefira funções estáveis e bem conhecidas
• evite hashes simplistas customizados sem necessidade real

Ordem de iteração não é garantida

Assim como no map nativo do Go, a iteração de hash table deve ser tratada como não ordenada.

Se ordenação estável for obrigatória, mantenha uma estrutura ordenada auxiliar (exemplo: slice de chaves ou árvore).

Comportamento de memória

Hash tables trocam memória por velocidade:

• array de buckets
• metadados por entrada
• alocações temporárias durante resize

Na maior parte dos casos isso compensa, porque o objetivo principal é velocidade de lookup.

Casos de uso reais

• Caches: chave para resultado computado
• Counting/frequency maps: chave para quantidade
• Indexes: identificador externo para objeto interno
• Sets: chave com struct{} vazio ou valor bool
• Joins/grouping: hashear um lado, consultar com o outro

Hash Tables vs Trees

• Use Hash Table quando sua operação principal for lookup exato por chave.
• Use Balanced Tree quando precisar de ordem, consultas por intervalo, predecessor/successor ou travessia determinística.

As duas são fundamentais e frequentemente usadas juntas em sistemas reais.

Conclusão

Hash tables são uma das estruturas mais práticas da engenharia de software porque oferecem operações médias rápidas com um modelo simples: hashear chave, escolher bucket, resolver colisão.

Neste artigo nós entramos fundo em colisões, load factor, resize e uma implementação completa em Go usando separate chaining, mantendo a mesma interface Container usada nos posts anteriores.

No próximo artigo podemos seguir para Heaps/Priority Queues, que são um ótimo próximo passo depois de estruturas focadas em lookup por hash.