Tratamento de Colisão

Conceito

Colisão não é falha da função de hash — é matematicamente inevitável. O espaço de chaves possíveis é maior que o de buckets (princípio da casa dos pombos), então existem necessariamente chaves diferentes que caem no mesmo lugar. Um hash map é definido tanto pela função de hash quanto pela política de colisão.

Encadeamento separado. Cada bucket guarda uma coleção (tipicamente uma 3. Lista Ligada) com todos os elementos que caíram nele.

• simples de implementar e de raciocinar
• tolera fator de carga > 1 (mais elementos que buckets, com degradação suave)
• remoção é trivial
• custa um ponteiro por elemento e péssima localidade — cada passo na cadeia é um possível cache miss

Endereçamento aberto. Não há cadeia: se o bucket está ocupado, você sonda o próximo segundo uma regra — linear (+1), quadrática (+i²), ou double hashing (passo derivado de um segundo hash).

• excelente localidade: tudo no mesmo array contíguo
• não aloca por elemento
• exige fator de carga < 1, com degradação abrupta perto do limite
• linear probing sofre de clustering: elementos agrupados fazem grupos crescerem, e grupos maiores aumentam a chance de crescerem mais

O ataque de colisão. Se o hash é determinístico e público, o atacante gera milhares de chaves que colidem, e cada inserção passa a percorrer uma cadeia enorme: O(1) vira O(n), e o serviço cai com pouquíssimo tráfego. Foi um CVE em massa em 2011, atingindo praticamente todas as linguagens. A mitigação padrão hoje é semente aleatória por processo (e SipHash como função), de modo que o atacante não pode prever os buckets.

Em Go

Você não escolhe a política — e essa é a diferença mais visível em relação a Java, onde HashMap expõe capacidade inicial e fator de carga.

Como o map de Go evoluiu:

O tophash (e o metadado das Swiss Tables) é a otimização que importa entender: em vez de comparar a chave inteira em cada slot, o map compara um byte do hash primeiro. Só quando esse byte casa é que a chave completa é comparada. Isso troca comparações caras por comparações baratas — o mesmo tipo de raciocínio de um índice de banco.

Proteção contra hash flooding: semente aleatória por processo, desde sempre. É por isso que a ordem de iteração varia entre execuções mesmo com as mesmas chaves.

Seu único controle: make(map[K]V, n) para dimensionar antecipadamente e evitar rehashes, e a escolha do tipo da chave — chave grande significa hash mais caro e comparação mais caro em toda operação.

Respostas às perguntas-guia

1. Por que colisão é inevitável, e não um bug da função de hash?

Conceito: casa dos pombos — há mais chaves possíveis que buckets. A função de hash boa minimiza colisões; nenhuma as elimina.

Em Go: o map foi projetado assumindo colisão como caso normal — os grupos de 8 slots existem justamente para absorvê-la sem sair da linha de cache.

2. Encadeamento separado vs endereçamento aberto: o que cada um paga?

Conceito: encadeamento paga ponteiros e cache misses, e ganha simplicidade, tolerância a carga alta e remoção trivial. Endereçamento aberto paga fragilidade (carga < 1, clustering, tombstones) e ganha localidade.

Em Go: o histórico da linguagem é um deslocamento de um para o outro — de buckets encadeados para Swiss Tables — porque em hardware moderno a localidade vale mais que a simplicidade.

3. O que acontece com remoção em endereçamento aberto?

Conceito: esvaziar o slot quebra a cadeia de sondagem e torna elementos posteriores inacessíveis. Precisa de tombstone, e tombstones degradam a busca até o rehash.

Em Go: o delete marca o slot (não é um "vazio" real) exatamente por isso. E é por isso que um map que teve muitas remoções não devolve memória — em Go o map nunca encolhe: para recuperar memória você cria um novo map e copia.

4. Como um atacante transformaria colisões em negação de serviço?

Conceito: enviando chaves escolhidas para colidir — cada inserção percorre a cadeia inteira, e O(1) vira O(n) com custo mínimo para o atacante.

Em Go: inviável de fora, pela semente aleatória por processo. Mas atenção: isso protege o map builtin. Se você implementa seu próprio índice com um hash fixo (FNV, CRC32) sobre entrada de usuário, você reintroduz a vulnerabilidade.

Trade-offs

Do conceito:

• Encadeamento: robusto, simples, mais lento no caso comum.
• Endereçamento aberto: mais rápido no caso comum, frágil no limite, remoção complicada.
• Hash rápido e não-semeado vs semeado: o segundo custa alguns nanossegundos e remove uma classe inteira de DoS. Para chave que vem de fora, não é escolha.

Em Go:

• Nada configurável: menos botões, menos tuning possível — e menos como errar.
• Map que nunca encolhe é uma pegadinha de memória real em cache de vida longa; a solução é recriar o map periodicamente.
• Semente aleatória custa a ordem de iteração determinística, que você não deveria querer de qualquer forma.

Exemplo prático

Os dois esquemas à mão, incluindo o bug da remoção sem tombstone:

package main

import "fmt"

func h(k string, n int) int { // hash proposital ruim: só o primeiro byte
	if k == "" {
		return 0
	}
	return int(k[0]) % n
}

// ---------- Encadeamento separado ----------
type Encadeado struct{ buckets [][]struct{ K string; V int } }

func NovoEncadeado(n int) *Encadeado {
	return &Encadeado{buckets: make([][]struct{ K string; V int }, n)}
}
func (m *Encadeado) Put(k string, v int) {
	i := h(k, len(m.buckets))
	for j := range m.buckets[i] {
		if m.buckets[i][j].K == k {
			m.buckets[i][j].V = v
			return
		}
	}
	m.buckets[i] = append(m.buckets[i], struct{ K string; V int }{k, v})
}
func (m *Encadeado) Get(k string) (int, bool) {
	for _, e := range m.buckets[h(k, len(m.buckets))] {
		if e.K == k {
			return e.V, true
		}
	}
	return 0, false
}

// ---------- Endereçamento aberto, com e sem tombstone ----------
const vazio, morto = 0, 2 // 0=vazio 1=ocupado 2=tombstone

type Aberto struct {
	ks     []string
	vs     []int
	estado []int
	usarTombstone bool
}

func NovoAberto(n int, tomb bool) *Aberto {
	return &Aberto{ks: make([]string, n), vs: make([]int, n),
		estado: make([]int, n), usarTombstone: tomb}
}
func (m *Aberto) Put(k string, v int) {
	i := h(k, len(m.ks))
	for n := 0; n < len(m.ks); n++ {
		j := (i + n) % len(m.ks)
		if m.estado[j] != 1 || m.ks[j] == k {
			m.ks[j], m.vs[j], m.estado[j] = k, v, 1
			return
		}
	}
}
func (m *Aberto) Get(k string) (int, bool) {
	i := h(k, len(m.ks))
	for n := 0; n < len(m.ks); n++ {
		j := (i + n) % len(m.ks)
		if m.estado[j] == vazio {
			return 0, false // para a sondagem: aqui está o bug, se houve remoção
		}
		if m.estado[j] == 1 && m.ks[j] == k {
			return m.vs[j], true
		}
	}
	return 0, false
}
func (m *Aberto) Delete(k string) {
	i := h(k, len(m.ks))
	for n := 0; n < len(m.ks); n++ {
		j := (i + n) % len(m.ks)
		if m.estado[j] == 1 && m.ks[j] == k {
			if m.usarTombstone {
				m.estado[j] = morto // "removido, mas continue sondando"
			} else {
				m.estado[j] = vazio // BUG: quebra a cadeia
			}
			return
		}
	}
}

func main() {
	// "ab", "ax", "az" colidem: mesmo primeiro byte
	e := NovoEncadeado(4)
	for i, k := range []string{"ab", "ax", "az"} {
		e.Put(k, i)
	}
	v, _ := e.Get("az")
	fmt.Println("encadeado, colidindo, acha az:", v == 2) // true

	for _, tomb := range []bool{false, true} {
		a := NovoAberto(8, tomb)
		a.Put("ab", 1)
		a.Put("ax", 2) // colide com ab -> sonda pro proximo slot
		a.Put("az", 3) // colide -> sonda mais
		a.Delete("ax") // remove o do MEIO da cadeia
		_, achou := a.Get("az")
		fmt.Printf("aberto tombstone=%-5v ainda acha az? %v\n", tomb, achou)
	}
}

A última saída é o ponto da nota: sem tombstone, remover um elemento do meio da cadeia esconde os que vinham depois — sem erro, sem panic, sem aviso.

Relacionado

• 6. Hash Map — a estrutura que isto sustenta
• 3. Lista Ligada — o que fica em cada bucket no encadeamento
• 5. Índices — semana 9, o mesmo raciocínio de comparação barata antes da caro
• 4. Mutabilidade — semana 1, chave que muda é o outro jeito de perder o elemento

---

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