Tabelas hash na prática: colisões, fator de carga e hashing com semente

O que é

Uma tabela hash mapeia uma chave para o índice de um bucket calculando hash(key) mod capacity. Duas chaves que caem no mesmo bucket colidem; a tabela resolve isso por encadeamento (uma pequena lista por bucket) ou por endereçamento aberto (sondagem de outras posições). O fator de carga é o número de entradas dividido pela capacidade. A documentação do HashMap do Java descreve o fator de carga como a medida de quão cheia a tabela pode ficar antes de a capacidade ser aumentada, com valor padrão de 0,75; quando as entradas excedem o fator de carga multiplicado pela capacidade, a tabela passa por rehash, o que percorre todas as entradas. O modelo de dados do Python afirma que os valores de hash de str e bytes recebem um salt imprevisível, diferente a cada processo (randomização de hash, ativada por padrão desde a versão 3.3), e a especificação do Go diz que a ordem de iteração sobre maps não é especificada.

Por que importa

As buscas em O(1) na média dependem de as chaves se distribuírem de maneira uniforme. Um atacante que pode escolher as chaves (nomes de parâmetros de query, nomes de campos JSON, campos de formulário) e conhece a função de hash consegue fazer milhares de chaves colidirem, transformando cada inserção em uma varredura linear e uma única requisição em trabalho quadrático; isso é o hash flooding, e a semente por processo é a defesa padrão. O rehash é O(n) e acontece ao atingir certos limiares, então um laço que insere n itens paga por várias rodadas de rehash: o custo amortizado continua O(1), mas cada inserção individual pode ter picos.

Como aplicar

• Nunca persista, transmita nem compare entre processos qualquer valor de hash gerado pela linguagem; ele muda com a semente, a versão e o build. Em vez de depender da ordem do map, ordene a saída que precisa ser estável.
• Dimensione previamente quando a quantidade for conhecida (HashMap(initialCapacity), make(map[K]V, n)) para evitar rodadas de rehash em laços críticos.
• As chaves não podem mudar enquanto estiverem na tabela; alterar uma chave depois da inserção torna a entrada impossível de encontrar. Objetos iguais devem ter o mesmo hash: defina igualdade e hash em conjunto.
• Ao implementar uma tabela (código embarcado, alocador próprio): use um hash com bom efeito avalanche, aplique uma semente por processo, limite o fator de carga e teste a maior cadeia de sondagem com chaves adversariais.
• Para testes reproduzíveis, fixe a semente de forma explícita (PYTHONHASHSEED) em vez de confiar no acaso, e rode também a suíte com uma semente aleatória.

Armadilhas

Um teste que passa com uma semente e falha com outra revela dependência de ordem no código, e não um teste instável (flaky). Chaves de ponto flutuante: 0.0 e -0.0 são iguais na comparação e precisam ter o mesmo hash; NaN não é igual a si mesmo. Uma tabela usada como cache sem limite de tamanho é um vazamento de memória. Digests criptográficos como SHA-256 são desnecessários para tabelas e lentos; o habitual são funções de hash rápidas, com chave, projetadas para tabelas.