TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Aula 10 -Pesquisa Hashing - Função Hash

Por:   •  19/9/2016  •  Trabalho acadêmico  •  619 Palavras (3 Páginas)  •  654 Visualizações

Página 1 de 3

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.

...

Baixar como (para membros premium)  txt (4.2 Kb)   pdf (166.4 Kb)   docx (593.9 Kb)  
Continuar por mais 2 páginas »
Disponível apenas no TrabalhosGratuitos.com