Fabio

2 Pesquisa de dados 3.1 Metodos de pesquisa
Pesquisa sequencial; Pesquisa binária; Pesquisa digital; Árvores de busca e Transformação de chave (ou tabela hashing) 3.2 Tabelas Hash * A estrutura de dados HASH é largamente utilizada para organizaçäo dos arquivos em discos nos banco de dados, veremos aqui, uma particularidade do HASH utilizada 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 aa 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 pemite uma melhora na eficiência da localizaçäo idividual dos elemento em relaçäo as 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 é, a dimensäo deste vetor, define o tamanho da chamada tabela de hash. * A forma mais comum da funçäo hashing é a aplicaçäo, no campo chave de ordenaçäo, da funçäo módulo pelo tamanho da hash table e o resultado desta operaçäo indica qual a sub-lista do elemento. Caso o campo chave de ordenaçäo näo seja numerico, pode-se utilizar artifícios para transformá-lo em um campo numeriro e, entäo, aplicar