088985430612

Univale União das Escolas Superiores do vale do ivaí
Luiz Fernando Prachum
Pedro Henrique de Sousa
RIVELINO PROENÇA MOTTA willian roberto grymuza

cURSO DE PROCESSAMENTO DE DADOS
3º semestre

Árvores Binárias Hashing

IVAIPORÃ
2007

Luiz Fernando Prachum
Pedro Henrique de Sousa
RIVELINO PROENÇA MOTTA willian roberto grymuza

cURSO DE PROCESSAMENTO DE DADOS
3º semestre

Árvores Binárias Hashing

Trabalho apresentado ao Curso de Processamento de Dados da UNIVALE União das Escolas Suériores do Vale do Ivaí, na disciplina de Estrutura de Dados, como requisito parcial para obtenção de nota. Orientador Professor: Lucas Mello Leão

IVAIPORÃ
2007
Hashing

DEFINIÇÃO

A estrutura de dados HASH é largamente utilizada para organização dos arquivos em discos nos banco de dados, uma particularidade do HASH é sua utilização em memória para melhorar o tempo de busca de elementos armazenados em listas encadeadas. A idéia básica é criar uma série de sub-listas no lugar de uma única lista maior, a partir da aplicação de uma determinada função (chamada função de hashing) sobre a chave de busca do elemento, decide-se em qual das sub-listas o elemento deve ser ou estar armazenado. Procede-se, então, uma busca na sub-lista determinada. Portanto, ao invés de realizar a busca em toda a lista, faz-se uma busca num subconjunto da lista. Assim, consegue-se uma busca eficiente, embora os elementos não fiquem dispostos ordenadamente, o hash permite uma melhora na eficiência da localização individual dos elementos em relação às listas. A questão principal é escolher uma função de hashing adequada para garantir uma distribuição uniforme dos elementos nas sub-listas, pois existe uma variedade enorme nas funções de hashing. Os ponteiros iniciais de cada sub-lista são dispostos num vetor. O número de sub-listas, isto