Hash Map

Conceito

Um hash map transforma uma chave num índice de array aplicando uma função de hash. É a estrutura que troca memória por tempo de forma mais agressiva que qualquer outra — e por isso é a mais usada.

Por que a busca é O(1): o índice é calculado a partir da chave, não procurado. Se o hash distribui bem e o número de elementos por bucket é mantido constante, achar uma chave custa: calcular o hash, ir ao bucket, comparar poucos elementos.

Em que condição vira O(n): quando todas as chaves caem no mesmo bucket. Isso acontece por hash ruim, ou porque um atacante escolheu as chaves — é o ataque de hash flooding, que transforma um endpoint O(1) em O(n) e derruba o serviço.

O que uma função de hash precisa garantir:

1. determinismo — a mesma chave sempre dá o mesmo hash (é por isso que a chave não pode mudar depois de inserida; ver 4. Mutabilidade)
2. distribuição uniforme — chaves parecidas devem cair em buckets distantes
3. rapidez — ela roda em toda operação

Não precisa ser criptográfica, exceto quando as chaves vêm de fora.

Fator de carga = elementos / buckets. Passando de um limite (tipicamente 0,7 a 1), a estrutura faz rehash: aloca uma tabela maior e reinsere tudo. Uma operação O(n), amortizada em O(1) porque é rara e o crescimento é geométrico.

Ordem de iteração não é confiável porque a ordem física depende do hash e do histórico de rehashes. Depender dela é um bug que só aparece quando o conjunto de dados muda.

Em Go

map[K]V é builtin, e a chave precisa ser comparável — o compilador recusa slice, map e func como chave (4. Mutabilidade).

A ordem de iteração não é apenas "não garantida": ela é deliberadamente randomizada. Go sorteia o ponto de partida a cada range. Isso é uma decisão de projeto para quebrar cedo o código que dependia de ordem, em vez de deixá-lo funcionar por acidente até quebrar em produção. Se você quer ordem, ordene as chaves explicitamente.

Proteção contra hash flooding: a semente do hash é aleatória por processo. Duas execuções do mesmo programa distribuem as mesmas chaves de forma diferente.

Implementação: desde o Go 1.24 o map usa Swiss Tables (grupos de slots com metadados de controle); antes eram buckets de 8 com array de tophash. Você não configura nada disso — o único ajuste possível é a dica de tamanho: make(map[K]V, 10_000), que evita rehashes.

Duas restrições que surpreendem:

• &m[k] não compila. Você não pode tomar o endereço de um elemento de map, porque o rehash move os elementos e o ponteiro ficaria inválido. Consequência prática: para um map[K]Struct você não pode fazer m[k].campo = v — precisa ler, alterar e reescrever, ou usar map[K]*Struct.
• Não é seguro para concorrência. Escrita concorrente dá fatal error: concurrent map writes — detecção deliberada do runtime, e é fatal, não panic: recover não pega. Para acesso concorrente: mutex, ou sync.Map (que só vence em cargas de leitura dominante com chaves estáveis).

O idioma central é o comma-ok: v, ok := m[k] — porque ler chave ausente devolve o valor zero, e 0 ou "" é ambíguo com "existe e vale zero".

Respostas às perguntas-guia

1. Por que a busca é O(1) — e em que condição ela vira O(n)?

Conceito: o índice é calculado, não procurado. Vira O(n) quando tudo colide — hash ruim ou chaves escolhidas por um adversário.

Em Go: a semente aleatória por processo torna o ataque inviável de fora, porque o atacante não consegue prever em que bucket cada chave cai.

2. O que uma função de hash boa precisa garantir?

Conceito: determinismo, distribuição uniforme, rapidez.

Em Go: você não escolhe a função — ela é interna e específica por tipo de chave. O que você controla é o tipo da chave: uma struct com muitos campos custa mais a cada operação do que um inteiro.

3. O que é fator de carga e o que acontece no rehash?

Conceito: elementos por bucket. No rehash, uma tabela maior é alocada e tudo é reinserido — O(n) pontual, O(1) amortizado.

Em Go: o rehash é incremental — o map migra os dados aos poucos, ao longo das operações seguintes, para não criar uma pausa longa. E é por causa do rehash que &m[k] é proibido.

4. Por que a ordem de iteração não é confiável?

Conceito: a ordem física é consequência do hash e do histórico de crescimento.

Em Go: ela é ativamente aleatorizada a cada range, de propósito. Para saída determinística: slices.Sorted(maps.Keys(m)) (Go 1.23+) e itere sobre as chaves ordenadas.

Trade-offs

Do conceito:

• O(1) esperado em troca de memória (buckets vazios) e de perder toda ordenação. Se você precisa de "próximo maior", "faixa", ou iteração ordenada, a estrutura errada é o hash map — use árvore (2. Árvore de Busca Binária).
• Amortização esconde picos: o rehash é uma latência ocasional grande. Em sistema de tempo real isso é inaceitável.
• Hash rápido vs resistente a ataque: você escolhe conforme a chave vir de dentro ou de fora.

Em Go:

• Map builtin é rápido e não configurável — o oposto do HashMap de Java. Menos botões, menos como errar.
• Ordem randomizada por padrão custa conveniência e compra corretude a longo prazo.
• &m[k] proibido força map[K]*T quando você precisa mutar campos — e aí você paga uma alocação por valor.
• sync.Map não é "map com lock": ele é otimizado para um padrão específico. Na dúvida, sync.RWMutex + map normal.

Exemplo prático

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Ponto struct{ X, Y int }

func main() {
	m := map[string]int{"a": 1, "b": 2, "c": 3}

	// comma-ok: distingue "ausente" de "existe e vale zero"
	if v, ok := m["z"]; !ok {
		fmt.Println("z ausente, valor zero foi", v) // 0
	}
	m["zero"] = 0
	_, ok := m["zero"]
	fmt.Println("zero existe?", ok) // true

	// ordem de iteracao e RANDOMIZADA de proposito
	fmt.Print("ordens diferentes: ")
	for i := 0; i < 3; i++ {
		var ks []string
		for k := range m {
			ks = append(ks, k)
		}
		fmt.Print(ks, " ")
	}
	fmt.Println()

	// saida deterministica: ordene as chaves
	fmt.Println("ordenado:", slices.Sorted(maps.Keys(m)))

	// struct como chave: compila porque é comparável
	visitas := map[Ponto]int{}
	visitas[Ponto{1, 2}]++
	visitas[Ponto{1, 2}]++
	fmt.Println("Ponto{1,2}:", visitas[Ponto{1, 2}]) // 2

	// dica de tamanho evita rehashes
	grande := make(map[int]int, 100_000)
	for i := 0; i < 100_000; i++ {
		grande[i] = i
	}
	fmt.Println("len:", len(grande))

	// m[k].campo = v NAO compila para map de struct:
	// tipos := map[string]Ponto{"a": {1, 2}}
	// tipos["a"].X = 9 // erro: cannot assign to struct field
}

Relacionado

• 7. Tratamento de Colisão — o que acontece quando duas chaves caem no mesmo lugar
• 4. Mutabilidade — semana 1, por que a chave precisa ter hash estável
• 6. Hash Map para Contagem — semana 4, o padrão que resolve metade dos exercícios
• 2. Árvore de Busca Binária — semana 3, quando você precisa de ordem

---

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação