Hash

Estruturas de Dados Capítulo 13: Tabelas Hash
13.1. Introdução Uma maneira de organizar dados, que apresenta bons resultados na prática, é conhecida como hashing1, e se baseia na idéia de distribuir os dados em posições aleatórias de uma tabela. Podemos apresentar esta idéia através de um exemplo. Suponhamos que desejamos organizar o cadastro de aproximadamente 500 empregados de uma empresa usando para identificar cada empregado o seu CPF2. Por exemplo, a informação sobre cada empregado pode ser guardada em um registro INFO: typedef struct info INFO, *PT; struct info{ int cpf; char nome[80]; char ender[120]; ... };

Como os CPFs variam entre 000 000 000 e 999 999 999, ignorando-se os “dígitos verificadores”, podemos guardar toda a informação em um vetor
INFO vet[1000000000];

ou para economizar algum espaço, em posições apontadas por componentes do vetor
PT vet[1000000000];

(A economia de espaço viria do fato de que INFO* ocupa menos espaço do que INFO, e do fato de que só precisariam ser representadas em estruturas INFO as informações associadas aos 500 empregados.) Estas duas maneiras tornariam o acesso muito simples: no primeiro caso, a informação sobre o empregado de CPF c estaria em vet[c], e, no segundo caso, em *vet[c]. Em qualquer dos dois casos, entretanto, a idéia é absurda, por causa do espaço total requerido. Uma variante desta idéia procura reduzir o espaço usando um “CPF parcial”, por exemplo, os três últimos dígitos. Neste caso, poderíamos ter um vetor
PT vet[1000];

e a informação sobre o mesmo empregado estaria em *vet[c%1000], usando-se aqui o operador % de C, que representa “módulo”, ou “resto da divisão”. O espaço foi reduzido a um total aceitável, o acesso continua simples, mas um problema adicional surgiu: dois empregados que tem CPFs com os mesmos três últimos dígitos passam a ter as informações guardadas na mesma posição do vetor. Esta situação é chamada de “colisão”, e deve ser resolvida encontrando-se uma posição alternativa