Hashing (Espalhamento)
• Permite agilizar o processo de consulta de
informações
• Não requer a realização de ordenação sobre um
conjunto de dados: pesquisa binária e nem a
utilização tabelas de índices
• Tornando a operação de inserção, tão rápida
quanto a realização de consulta
• Internet: segurança na troca de mensagens pela
Internet - integridade de uma mensagem
• Integridade de uma mensagem – assegurar que a
mensagem original não foi modificada um byte
sequer
Hashing - Internet
Hashing - Conceitos
• A função Ψ : E [1 ..n] mapea cada
elemento de E à sua classe específica
• A função Ψ é denominada de função
de espalhamento ou função de
hashing
• O valor de hashing Ψ (x), indica a
respectiva classe que contém o
elemento x, ou seja, x ∈ Ψ (x).
• Cardinalidade de um conjunto C indica
o número de elementos contidos em
C, sendo representada por |C|
• Função ótima Abs(|Ci| - |Cj| ) ≤ 1,
para 1 ≤ i < j ≤ n
Hashing - Exemplo
• E = { a, b, c, d, e, f, g, h,i,j}
• Ψ é uma função hashing qualquer que realiza um
espalhamento dos elementos de E em quatro classes
distintas conforme abaixo:
Ψ(a) = 1 Ψ(c) = 3 Ψ(e) = 1 Ψ(g) = 3 Ψ(i) = 4
Ψ(b) = 2 Ψ(d) = 3 Ψ(f) = 2 Ψ(h) = 1 Ψ(j) = 4
• Então, temos 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
Hashing - Exemplo
• Ocorreu uma função de hashing ótima
• Todas as 4 classes tem praticamente o mesmo
número de elementos, ou seja, o espalhamento foi
uniforme
• Um espalhamento é perfeito, se a função de
hashing para um conjunto E, resultar em |E| classes
distintas e cada uma dessas classes conter
unicamente um elemento de E
• Se existem x∈E e y∈E, tal que x ≠ y mas Ψ(x) =Ψ(y),
dizemos que x e y são sinônimos ou seja ocorreu a
chamada colisão
Hashing - Representação
• Pode-se utilizar um vetor de listas
• Cada índice do vetor representa uma das possíveis
classes
• Cada lista armazena os elementos de determinada
classe
Hashing - Função
Hashing - Função
• Função de hashing ideal: capaz de mapear n chaves
em exatamente n endereços, sem a possibilidade de
ocorrer de uma colisão sequer
• De forma prática, é satisfatório obter funções de
hashing capazes de resultar num mapeamento
razoável, distribuindo as n chaves de forma
aproximadamente uniforme entre m endereços, tal
que m < n (significando que sempre teremos
colisões)
Hashing – Principais Tipos
• Método direto: como o próprio nome indica, o valor
do hashing é obtido sem nenhuma manipulação de
algoritmo. Exemplo: histograma.
• Método da subtração: algumas vezes temos chaves
que são consecutivas mas não começam de um.
Exemplo: armazenar dados dos últimos 10 anos.
Hashing – Principais Tipos
• Método da divisão inteira: a idéia é obter o resto da
divisão da chave pelo tamanho da lista. Se o
tamanho da lista for um número primo, são
produzidas poucas colisões. Exemplo: divisão por 7.
• Extração de dígito: são extraídos dígitos
selecionados da chave e utilizados como endereço.
Exemplo: RA dos alunos.
• Método quadrático: a chave é elevada ao quadrado
e o endereço é selecionado do meio do quadrado no
número.
Hashing – Principais Tipos
• Método do folding: a chave é divida em partes cujo
tamanho casa com o endereço requerido. Então a
parte da esquerda e da direita são somadas a parte
central. O que passar do tamanho disponível para o
endereço, é descartado.
• Método da rotação: geralmente não é usado de
forma independente, ao invés disso, é utilizado em
combinação com outros métodos de hashing.
Geralmente métodos simples de hashing têm a
tendência de criar sinônimos. Então o método da
rotação pode ser utilizado para minimizar o
aparecimento das colisões, colocando o último
caracter na frente da chave.
Hashing – Principais Tipos
• Método pseudo-aleatório: a chave é usada como
semente num gerador de número aleatório. O
número aleatório obtido é ajustado para a faixa de
endereço desejada usando o método da divisão.
Hashing – Principais Tipos
• Método pseudo-aleatório: a chave é usada como
semente num gerador de número aleatório. O
número aleatório obtido é ajustado para a faixa de
endereço desejada usando o método da divisão.