01115

Hashing
Todas as estratégias de busca utilizadas até agora (seqüencial, indexada, busca binária, árvore binária e árvores multiway) realizam algumas comparações para que uma determinada chave seja encontrada. Algumas técnicas realizam mais comparações do que outras e isso influencia diretamente a performance do método. Mas como essas comparações desnecessárias podem ser eliminadas do processo de busca e a chave ser acessada diretamente? Para isso será considerado que cada chave a ser pesquisada é independente, ou seja, não depende do valor de outros elementos (o arquivo é desordenado).
Considere que um pequeno comerciante vende na sua loja pouco menos de 100 produtos. Ele deseja fazer um cadastro que leve em consideração o código do produto. Cada embalagem possui um código com 7 dígitos. Se o cadastro de produtos fosse implementado uma forma seqüencial ou indexada de representação em array, seria necessária uma array de pelo menos 9.999.999 posições para armazenar menos de 100 produtos. Isso é inaceitável, pois o espaço alocado desnecessariamente é extremamente grande. Uma forma mais inteligente de armazenamento seria transformar cada código de produto em um índice válido de um array de 100 posições (note-se que o número de produtos é menor ou igual a 100). Uma função que transforma uma chave em um índice dentro de um intervalo válido de valores é chamada de função hashing. Se h é uma função hashing e chave o elemento a ser pesquisado dentro de uma tabela, então h(chave) é a hash da chave e representa a posição dentro da tabela onde o registro com a chave chave está localizado.
A Tabela a seguir apresenta um exemplo de função hashing. Dado um conjunto de chaves que possuem 7 dígitos, a aplicação da função sobre uma chave retorna seus últimos 3 dígitos. Isso representa que a tabela terá 1000 posições. Por exemplo: h(9837561) = 561. Esta função pode ser facilmente obtida através de: h(chave) = chave % 1000.

|Posição |Chave |Registro |