Introdução a Hashing_ estrutura de dados_II

Prévia do material em texto

Hashing (Espalhamento) 
 
Uma tabela de hashing é uma estrutura de dados que oferece pesquisa a dados 
muito rápida, não exigindo a ordenação sobre esse conjunto de dados. 
 
Analogia: 
 Loja de Departamento 
 
Conceito: 
 
 Dada a existência de um conjunto E contendo todos os elementos de um 
universo, denomina-se hashing ou espalhamento, o particionamento de E em um 
conjunto finito de classes C1, C2, C3, ..., Cn, sendo n >= 1., observando-se que 
a união de todas as classes resulta no próprio conjunto original E, e que um 
elemento não poderá participar de duas classes simultaneamente. 
 
 Para o mapeamento dos elementos do conjunto E, nas classes C1 .... Cn, é 
necessário a definição de uma função, denominada h (função de espalhamento 
hashing). 
 
Terminologia 
 
Cardinalidade: A cardinalidade de um conjunto C indica o número de elementos 
contidos nesse mesmo conjunto, sendo representada por |C|. 
 
Supondo um conjunto E = {a, b, c, d, e, f, g, h, i, j} e uma função hashing 
qualquer que realiza o espalhamento dos elementos de E em quatro classes 
distintas. 
 
 
 
h(a) = 1 h(c) = 3 h(e) = 1 h(g) = 3 h(i) = 4 
h(b) = 2 h(d) = 3 h(f) = 2 h(h) = 1 h(j) = 4 
Obtem-se então as seguintes classes com as respectivas cardinalidades: 
 
 C1 = {a,e,h} |C1| = 3 
 C2 = {b,f} |C2| = 2 
 C3 = {c,d,g} |C3| = 3 
 C4 = {i,j} |C4| = 2 
 
Analisando as cardinalidades das classes criadas, observa-se que a diferença 
absoluta dessas cardinalidades é no máximo 1, onde constata-se a presença de 
uma função hashing ótima. E, como todas as classes tem praticamente o 
mesmo número de elementos, o espalhamento é denominado uniforme. 
 
Espalhamento Perfeito: Ocorre quando de uma função hashing para um 
conjunto E resultar em |E| classes distintas. 
No exemplo anterior existiria um espalhamento perfeito se o conjunto de 
classes fosse igual a 10 (qtde de elementos da classe), ou seja, a cardinalidade 
do conjunto E = {a, b, c, d, e, f, g, h, i, j}. 
 
Percebe-se que, dado um conjunto E, a pesquisa de um elemento x será muito 
mais eficiente se a pesquisa atuar em uma pequena parte do conjunto E (uma 
única classe), devendo conter então o elemento procurado. Verifica-se que o 
espalhamento pode ser utilizado para reduzir o espaço de busca. 
 
Função hashing ideal: é aquela capaz de mapear n chaves em exatamente m 
endereços, sem a possibilidade de ocorrer uma colisão, ou seja, que, da 
transformação de duas chaves, se obtenha o mesmo endereço físico. 
 
Funções Hashing 
 
Utiliza-se o hashing para manipulação de chaves em banco de dados, pelo 
algoritmo hashing, de forma a se obter como resultado um endereço físico, que 
pode ser usado para localizar o dado armazenado sob a forma de um vetor 
(alocação estática). 
 
 
 
 
 
 
 
 
 
Método da Divisão Inteira: Esse método prevê que o espalhamento será 
realizado obtendo-se o resto da divisão da chave pelo tamanho da tabela 
hashing, obtendo-se então o endereço hashing. 
 
“A transformação da chave de um registro em um valor de índice é 
chamada de hashing e é executada por meio de uma função hash. O 
vetor utilizado para armazenar os registros, com os quais o valor do 
registro é usado, é conhecido como tabela hash”. 
Aplicação do método da divisão inteira : 
 
Considerando a seguinte tabela, onde código é o campo chave: 
 
Código Nome Idade 
49 João 10 
16 Roberto 12 
10 Paulo 15 
41 Rita 20 
2 Fátima 13 
28 Sergio 18 
73 Joana 28 
4 Inês 32 
9 Carlos 29 
57 Fulvio 21 
90 Ana 19 
82 Amélia 20 
 
Define-se que os valores que representam o campo-chave da tabela deverão 
ser espalhados em 5 (cinco) subconjuntos (classes). 
 
A função hashing obtida pelo método da divisão inteira será a seguinte: 
 
h(x) = (chave % 5) 
 
h(x) X % 5 Endereço hashing 
calculado 
H(49) 49 % 5 4 
h(16) 16 % 5 1 
h(10) 10 % 5 0 
h(41) 41 % 5 1 
h(2) 2 % 5 2 
H(28) 28 % 5 3 
H(73) 73 % 5 3 
h(4) 4 % 5 4 
h(9) 9 % 5 4 
H(57) 57 % 5 2 
H(90) 90 % 5 0 
H(82) 82 % 5 2 
 
 
Tratamento de colisões 
 
Existirão casos, onde, durante o processo de espalhamento, seja observada uma 
colisão ao menos. 
 
 
 
 
 
 
A forma mais utilizada para tratamento de colisões é o chamado Encadeamento 
Separado, ou Espalhamento Externo, onde o vetor utilizado para definição de 
cada classe contém o ponteiro para listas encadeadas. 
 
“Colisão é o evento que ocorre quando o algoritmo de 
espalhamento produz o endereço para a inserção de um 
elemento, mas tal endereço já está ocupado por outro elemento 
sinônimo”. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Índ 
0 
1 
2 
3 
4 
h(x) X % 5 Endereço hashing 
calculado 
H(49) 49 % 5 4 
h(16) 16 % 5 1 
h(10) 10 % 5 0 
h(41) 41 % 5 1 
h(2) 2 % 5 2 
H(28) 28 % 5 3 
H(73) 73 % 5 3 
h(4) 4 % 5 4 
h(9) 9 % 5 4 
H(57) 57 % 5 2 
H(90) 90 % 5 0 
H(82) 82 % 5 2 
Amélia82 20 
codig
 
Ana 90 
nome idade prox 
19 
Rita 41 20 
Fúlvio 57 21 
Joana 73 28 
Inês 4 32 Carlos9 29
codig
 
Paulo 10 
nome idade prox 
15 
Roberto 16 12 
Fátima 2 13 
Sérgio 28 18 
João 49 10
Espalhamento como Estrutura de Dados 
 
 
 
 
 
 
 
 
- Implementação com Vetores: Cada posição do vetor será utilizada para 
representar cada uma das classes obtidas por meio da função hashing, 
denomina h(x). 
 
Declaração em C: 
 Hashing 
 
Inserir excluir 
elemento ...... elemento
dados dados 
 Material Extra 
 
Outros Métodos utilizados para realizar o espalhamento 
 
1) Método Direto: Utilizado sem aplicação de nenhum algoritmo (tabelas com 
pequenas quantidades de dados). 
Ex: Acumulativo de vendas ao longo do ano armazenadas em um vetor de 12 
posições 
Vendasanuais[mes] = vendasanuais[mês] + totalvendido 
 
 
 
2) Método da Subtração: Aplicado quando são utilizadas chaves consecutivas, 
excetuando-se as que iniciam por um. (tabelas com pequenas quantidades de 
dados). 
Ex: Chaves consecutivas que iniciam por 1000 indo até 1100 
 
 
 
3) Extração de dígito: Nesse método, a função hashing prevê a extração de 
dígitos e esses são utilizados como endereço hashing. 
Ex: Supondo um código de funcionário composto por seis dígitos, pode-se 
determinar que a função hashing resultará como endereço hashing o primeiro, o 
terceiro e o quarto dígito desse campo chave. 
 
Chave da Tabela Endereço Hashing 
547790 577 
856430 864 
523233 532 
 
 
4) Método Quadrático: Nesse método o endereço hashing será obtido em duas 
fases: 
1º) Eleva-se a chave da tabela ao quadrado 
2º) Retira-se o endereço do meio dessa chave que foi elevada ao quadrado. 
 
Ex: Chave: 911 
1º)911 * 911 = 829921 (911 ao quadrado) 
2º) 2992 (retirando os elementos do meio do número que foi elevado ao 
quadrado) 
 
 
5) Método do Folding (ou desdobramento): Nesse método o endereço hashing 
é obtido dividindo-se a chave em partes cujo tamanho se enquadra com o 
endereço exigido. 
 
a) Folding Shift: Logo após a realização do desdobramento, a parte da 
esquerda e da direita são somadas a parte central, o que passando do 
tamanho central sendo descartado. 
 
Ex: Chave: 123456789 
123 456 789 
 
 123 
 456 + 
 789 . 
1368 (o número um é descartado) 
 
b) Folding Boundary: Logo após a realização do desdobramento, inverte-se a 
parte da esquerda e da direita, e só após essa inversão essa duas partes são 
somadas a parte central, o que passando do tamanho central sendo 
descartado. 
 
Ex: Chave: 123456789 
124 456 789 
 
 321 (invertido) 
 456 + 
 987 (invertido) 
1764 (o número um é descartado) 
 
 
 
6) Método da Rotação: Geralmente utilizado em combinação com outros 
métodos, esse método prevê a rotação do último dígito para o início da chave, 
em seguida aplicando outro método paradeterminação do endereço hashing. 
 
Chave Original Rotação Chave Rotacionada 
700101 700101 170010 
700102 700102 270010 
700103 700103 370010 
700104 700104 470010 
700105 700105 570010