01115

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (890 palavras )
  • Download(s) : 0
  • Publicado : 14 de novembro de 2012
Ler documento completo
Amostra do texto
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 sejaencontrada. 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 debusca 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 7dí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 100produtos. 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 umarray 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. Issorepresenta 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 |...
tracking img