Tabelas Hash¶
Uma tabela hash mapeia chaves para posições de um array. Como chaves distintas podem ser mapeadas para a mesma posição, toda implementação precisa de uma estratégia para colisões.
Contrato¶
Em coleções Java baseadas em hash, objetos iguais devem possuir códigos hash iguais:
A recíproca não é obrigatória. Colisões são válidas e devem ser resolvidas. Chaves mutáveis são perigosas: alterar o estado relevante à igualdade após a inserção pode tornar uma entrada inalcançável pela busca comum.
Estratégias para colisões¶
- Encadeamento separado: cada bucket armazena várias entradas.
- Endereçamento aberto: entradas que colidem sondam outras posições; a remoção exige um marcador ou uma política de reorganização cuidadosa.
O fator de carga relaciona as entradas armazenadas aos buckets disponíveis.
O redimensionamento mantém sob controle o comprimento esperado da cadeia ou da
sondagem, ao custo de rehashing ocasional Θ(n).
Complexidade¶
Busca, inserção e remoção têm custo esperado O(1) sob uma distribuição hash
eficaz e um fator de carga controlado. O pior caso pode ser linear.
Implementações Java podem usar defesas adicionais contra colisões, mas o código
cliente ainda deve implementar um hashing correto e bem distribuído.
Uma chave de valor¶
record Coordinate(int row, int column) {}
Map<Coordinate, String> labels = new HashMap<>();
labels.put(new Coordinate(2, 3), "target");
Records derivam de seus componentes a igualdade e o hashing baseados em valor, o que torna esse record imutável adequado como chave.
Exercícios¶
- Explique por que um código hash constante é correto, mas ineficiente.
- Compare encadeamento separado e sondagem linear sob carga elevada.
- Projete a igualdade de um identificador que não diferencie maiúsculas de minúsculas.