Tabelas hash (HashMap, Set, Dictionary)

Como funciona

A função hash transforma a chave num número; o resto da divisão pelo número de baldes dá o índice. Buscar uma chave é calcular o hash e olhar um balde só — por isso O(1) na média, não importa se são 10 ou 10 milhões de itens.

Colisões e fator de carga

Chaves diferentes podem cair no mesmo balde. A solução clássica é uma lista por balde (o HashMap do Java vira árvore quando a lista passa de 8). Para as listas ficarem curtas, a tabela cresce quando itens ÷ baldes passa do fator de carga (0,75 no Java): dobra os baldes e redistribui tudo.

Cuidados

• Chaves precisam de equals e hashCode coerentes (em Kotlin, data class já gera; em Swift, Hashable).
• Não mude um objeto depois de usá-lo como chave: o hash muda e ele "some".
• A ordem de iteração não é a de inserção, exceto em LinkedHashMap (padrão do mutableMapOf no Kotlin) e no Map do JavaScript.

// O(pedidos × clientes): procura o cliente na lista a cada pedido
const comNome = pedidos.map((p) => ({
  ...p,
  cliente: clientes.find((c) => c.id === p.clienteId)?.nome,
}));

// O(pedidos + clientes): indexa uma vez, consulta em O(1)
const porId = new Map(clientes.map((c) => [c.id, c.nome]));
const comNome = pedidos.map((p) => ({ ...p, cliente: porId.get(p.clienteId) }));