Hashing
Prof. Josenildo Silva
[email protected]
IFMA
2012
Esta versão é de 2012.11.21
© 2012, Prof. Josenildo Silva. ([email protected])
Estas notas de aula foram preparadas por Josenildo Silva para a disciplina
Análise e Projeto de Algoritmos do Programa de Mestrado Profissional
IFMA/UEMA baseado nas notas de aulas do Prof. Omar Andres Carmona
Cortes. Fica aqui permitida a utilização, cópia, modificação e distribuição
destas notas para propósitos educacionais, desde que esta nota de copyright
seja mantida em todas as cópias.
Introdução
 Estruturas de busca seqüencial/binária levam
tempo O(n) até encontrar o elemento
desejado
 Em uma árvore o tempo de busca é em torno
de O(lg n)
 Muitas vezes é necessário encontrar a posição
de um elemento em tempo O(1) (perfeita) no
melhor caso e O(n) (muitas colisões) no pior
caso
o Utilizar uma tabela Hash
Tabelas Hash
 Operações suportadas
o inserir(k)
o buscar(k)
o remover(k)
Tabelas Hash
 Uma tabela hash é uma estrutura de dados
que permite acesso a elementos em tempo
O(1) dada uma função de hashing
 Exemplo usando a função mod
20 mod 8 = 4
0
20?
1
2
64
11?
11 mod 8 = 3
3
4
11
20
5
6
7
7
Função de Hashing
 O endereço ou índice que um elemento é
armazenado é encontrado através de uma função
de transformação
o Função de Hashing
 Seja M o tamanho da tabela, a função de hashing
mapeia as chaves de entrada dentro do intervalo
[1...M]
 Formalmente h(kj) [1,M], onde
o kj {k0, ..., km},
o sendo que h retorna mi  [1,M]
Funções de Hashing
 A função deve ser fácil de se computar para não
comprometer o desempenho
 A função deve também fazer uma distribuição
uniforme dentre os índices disponíveis
 Colisões sempre irão ocorrer
 Funções mais comuns
o
o
o
o
Resto da divisão (mod)
Método da multiplicação
Hashing Universal
Hashing Perfeito
Método do Resto da Divisão
Resto da Divisão (MOD)
 Forma mais simples de ser utilizada
 O endereço de armazenamento ou
consulta é o resto da divisão da sua chave
por M, onde M é o tamanho da tabela e x
um número inteiro
o h(x) = x mod M para mi  [0, M-1]
 O resultado estará no intervalo [0, M-1]
Resto da Divisão (MOD)
 Exemplo
o Considere um vetor de tamanho 1001 para
armazenamento e a seqüência de chaves: 1030, 839,
10054 e 2030
o Os respectivos endereços (índices serão)
Chave
1030
10054
839
2030
Endereço (mod 1001)
29
53
839
28
Resto da Divisão (MOD)
 Vantagens
o Fácil de computar
o Rápida
 Desvantagens
o Função depende do valor de M
o M deve ser um número primo
o M > 20
o Alta probabilidade de colisões
Método da Multiplicação
Método da Multiplicação
 Funciona do seguinte modo
o
o
o
o
Multiplica-se a chave k por uma constante A, onde A  [0,1]
Extrai-se o resto da multiplicação com kA mod 1
Multiplique o resultado por m, o tamanho da tabela
Finalmente
 h(k) = m (kA mod 1)
 A escolha de m não é crítico
 Sugere-se A = 0.6180339887
o (D. Knuth “The Art of Programming”)
 Para facilitar a implementação m deve ser uma potência de 2
Método da Multiplicação
 Exemplo: dado um m = 100, a tabela a
seguir mostra onde as chaves serão
inseridas
Chave
1000
2000
3500
150
10
18
h(x)
3
6
11
70
18
12
Chave
25
32
136
357
211
896
h(x)
45
77
5
63
40
75
Hashing Universal
 Com funções de hashing “fixas” é possível prever as
colisões para um conjunto dado de entradas
o Solução: Criar funções de hashing aleatórias
independentes das chaves baseando-se em pesos
aleatórios
 Seja U o universo de chaves e H um conjunto finito de
funções de hashing, onde u  U  {0, 1, ..., m-1}
 H é universal se  x,y  U, onde x  y, {H: h(x) = h(y)} =
H/m
o Escolhendo h aleatoriamente a probabilidade de haver
uma colisão é 1/m
Hashing Universal
 Os pesos são iniciados aleatoriamente a
cada execução do programa, mas
permanecem inalterados até o fim da
execução.
Hashing Universal
 No caso de strings de tamanho n
n 1
K   chave[i ]  p[i];
i 0
h( K )  K mod M
Hashing Universal
Hashing Perfeito
 Transforma/mapeia um conjunto de chaves
xj, 1  xj  N em um conjunto de inteiros no
intervalo 0  h(xj)  M-1
 Ocorrerá h(xi) = h(xj) se e somente se xi = xj
 Se N=M então tem-se uma função de
transformação perfeita mínima
 Se xi < xj e h(xi) < h(xj) temos uma função de
transformação perfeita mínima com ordem
preservada
Hashing Perfeito
Tratamento de Colisões
 Sempre há a possibilidade de colisões, exceto
para as funções de hashing perfeito
 Existem possibilidade para tratar as colisões
dependendo da forma como a tabela hash é
construída
o Endereçamento Aberto
 Hashing Linear
 Hashing Duplo
o Endereçamento Fechado
Endereçamento Aberto – Hashing
Linear
 No hashing linear busca-se a próxima posição
vazia depois do endereço da chave
 Vantagem: simplicidade
 Desvantagem: a inserção e busca passam a ter
desempenho O(n)
27 mod 8 = 3
0
27?
64
1
2
3
4
11
20
5
6
7
7
Endereçamento Aberto - Hashing
Linear
 Implementação
 A função é calculada até que uma posição
livre seja encontrada
void inserir(Chave ch, Table HashTable){
inteiro i;
i = h(ch); //calculo de endereço
enquanto (HashTable[i] ocupado)
i = (i + 1) mod n;
HashTable[i] = ch;
}
 A busca é feita de modo análogo
Hashing Duplo
 Também chamado de re-hash
 Ao invés de incrementar a posição em 1, uma outra função
de hash auxiliar é utilizada
o h(i,k) = (h1(k) + i * h2(k)) mod M
 Restrições
o M deve ser uma potência de 2
o h2 deve ser sempre ímpar
 Exemplo
o h1(k) = k + 37; // usando número primo
o h2(k) = k + 31; se h2 é ímpar
o h2(k) = (k + 31) + 1; se h2 é par
Hashing Duplo
 Exemplo
h1 = 27 + 37 = 64
h = (64 + 0 * 59) mod 8 = 0
h2 = (27 + 31) + 1 = 59
0
27?
64
1
2
3
4
11
20
5
6
7
7
h = (64 + 1 * 59) mod 8 = 123 mod 8 = 3
h = (64 + 2 * 59) mod 8 = 182 mod 8 = 6
Implementação em C:
http://www.youtube.com/watch?v=272lg-fhklE&feature=related
Fator de Carga
 Quando utilizamos o endereçamento
aberto a medida que inserimos mais
elementos o desempenho da tabela hash
cai, pois ocorrem mais colisões
 O fator de carga  é definido como n/m
 Se o fator de carga é alto então deve-se
expandir a tabela hash
Endereçamento Fechado
 Também chamado de Overflow Progressivo
Encadeado
 Utiliza-se uma lista encadeada para cada
endereço da tabela
 Vantagem
o Não é preciso recalcular endereços
o “Sinônimos” são encontrados em uma única busca
 Desvantagem
o Tratamento em listas pode consumir tempo O(n)
Endereçamento Fechado
 Usando o método tradicional de hashing inserimos os
elementos 20, 25, 36, 39, 41, 51, 60, 61
0
20 mod 8 = 4
25 mod 8 = 1
36 mod 8 = 4
39 mod 8 = 7
41 mod 8 = 1
51 mod 8 = 3
60 mod 8 = 4
61 mod 8 = 5
1
2
3
4
5
6
7
25
41
51
20
61
39
36
60
Exercícios
 Implemente o algoritmo de hashing linear
tradicional com tamanho M e N elementos (M >
N)
o Insira N – 1 elementos e verifique a média de
colisões
o Faça uma expansão quando  for 0.8, insira mais N/2
elementos e verifique a média de colisões
 Faça as mesmas operações acima usando o
Hashing Universal e obtenha as mesmas medidas
Exercícios
 Dado uma tabela hash de 170 posições e um domínio de chaves
no intervalo [1, 1000], com 150 chaves, implemente um programa
que encontre pelo menos 4 colisões usando:
o Resto da divisão
o Multiplicação
 Implemente um programa que armazene 100 chaves quaisquer
em um vetor de 130 posições e expanda a tabela hash quando a
carga for igual a 60%.
 Verifique o desempenho necessário para expandir uma tabela
hash de 10.000 para 30.000 usando o hashing universal, com:
o 5000 chaves
o 9000 chaves
Referências
 Slides do Prof. Omar Carmona
 CORMEN, 3ª. Ed.
 SEDGEWICK, Algorithms. Sec. 3.4
 Slides do Prof. Paulo Feofiloff (IME, USP)