Aula 10 -Pesquisa Hashing - Função Hash

Aula 10 → Pesquisa Hashing  - Função Hash

Pesquisa Hashing

Hash = espalhar/ distribuir

Hashing é um método de pesquisa baseado na transformação do valor da chave de pesquisa por uma função denominada de Hash.
Este método possibilita a ordenação através de funções de distribuição, possibilitando à partir de um simples cálculo de endereço determinar o posicionamento de um dado.

A pesquisa Hashing consiste basicamente em duas etapas:

Passo 1→ Através da função Hash, transformar o valor da chave de pesquisa em um endereço da tabela.

Passo 2→ Considerando que dois ou mais valores das chaves podem ser mapeados para o mesmo endereço da tabela, deve-se aplicar um método para resolver essas colisões.

Função Hash [pic 2]

A Função Hash
Transforma o valor de uma chave de pesquisa K (K pertence ao DCH = Domínio de valores de chaves ) em um inteiro dentro do intervalo [0...(n-1)] onde n é o tamanho da tabela.[pic 3]

Veja a figura abaixo:[pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10]

[pic 11][pic 12][pic 13][pic 14][pic 15]

[pic 16][pic 17][pic 18]

Domínio de valores de chaves[pic 19][pic 20][pic 21]

Inserção com Hash

Para inserir uma chave na tabela hash, primeiro temos que calcular (através de uma função Hash) o valor correspondente na tabela Hash, após calculado, insere-se a chave neste endereço.

Pesquisa com Hash

Para pesquisar um elemento da tabela Hash, basta encontrar para a chave procurada o valor correspondente na tabela Hash e fazer a busca neste endereço.

Existem diversos tipos de Funções Hash. Cada uma com um método próprio, mas todas com o mesmo propósito: Transformar a chave em um valor n tabela Hash.

Vamos ver alguns tipos de Funções Hash.

Função Hash baseada na divisão

Esta função utiliza o resto da divisão do valor da chave K pelo numero de entradas da tabela hash N.

H(k) = K mod N       ou       H(k) = mod (K, N)

Exemplos:

Supondo que N= 100.

Valores de K	Endereço H(K)=mod(k, 100)	Endereço H(k)=mod(K, 103)
102	2	102
1127	27	97
874	74	50
2030	30	73
2027	27	70

[pic 22]

Obs.: a) Melhor que o N seja um número primo para que reduzir as colisões.

     b) Quando a chave for uma String de caracteres pode-se somar os valores correspondentes a cada caractere antes de calcular a função mod, ou seja, o resto da divisão.

Função Hash - Direta

Esta função parte do princípio em que o valor do Hashing é obtido sem nenhuma manipulação de algoritmo.

Exemplos:

Considera-se uma letra de um campo String e o valor do hashing é igual à ordem da letra dentro do alfabeto.

Valores da chave K	Endereço direto H(K)
PAULO	H(U) =21
MARISA	H(R) = 18
JOSE	H(S)= 19
ANTONIO	H(T)= 20

Função Hash - Subtração

Esta função é aplicável em casos onde as chaves tem valores consecutivos mas não começam em 1.

Exemplos:

Código de funcionários que começam em 1000 e vão até 1100.A função hash consiste em subtrair 1000 do valor da chave.