Organização e Recuperação
da Informação - Hashing
Ednaldo Pizzolato
Hashing
• Proposta
– Em lugar de organizarmos a tabela segundo
o valor relativo de cada chave em relação às
demais, a tabela hash leva em conta somente
seu valor absoluto, interpretado como um
valor numérico. Através de uma função
conveniente, a chave é transformada em um
endereço de uma tabela.
Hashing
• Princípio de Funcionamento
– Suponha que existam n chaves a serem
armazenadas em uma tabela T, seqüêncial e
de dimensão m (i.e. [0..m-1]). Cada posição
corresponde a um endereço e pode
armazenar r nós distintos.
– Obs.: quando a tabela se encontra em
memória, é comum que cada endereço
armazene um único nó. Já quando a tabela
está em disco a organização pode ser
diferente.
Hashing
• Acesso Direto
– Quando possuímos uma tabela de tamanho
m e o número de chaves é n, tal que n ≤ m e
mais, cada chave x é armazenada na posição
x da tabela, dizemos que x serve de índice
para sua busca, e que o acesso à informação
é direto.
Hashing
chaves
01 03 00 02 05 04
Tabela
Problema ?
Hashing
chaves
01 03 00 02 05 04
Tabela
Como seria o armazenamento
de chaves cujos valores estivessem entre 1 e 999999?
Hashing
• Função Hash
– Nem sempre as chaves estão no intervalo
[0..m-1], mesmo sendo o número de chaves
menor que m. Por isso, devemos transformar,
de alguma forma, nossa chave x para um
valor no intervalo [0..m-1]. A função h(x), qual
que 0 ≤ h(x) ≤ m-1, responsável por esta
transformação é chamada de função hash.
Hashing
• Colisão
– Infelizmente, a função h(x) não pode garantir
injetividade... Isso significa que podem existir
chaves x e y (onde x ≠ y), tal que h(x) = h(y).
Este fenômeno é chamado colisão. Dizemos
que x e y são sinônimas em relação a h.
Hashing
• Custo
– Pelo
fato
de
não
conhecermos
profundamente a função h e, principalmente,
não conhecermos previamente as chaves que
serão inseridas em uma tabela, podemos
apenas determinar limites inferiores e
superiores para a complexidade da busca.
Estes limites são O(1) (acesso direto) para o
melhor caso, sendo o pior caso, porém O(n).
Hashing
• Propriedades da Função Hash
– Produzir um número baixo de colisões;
– Ser facilmente computável;
– Ser uniforme (distribuição equilibrada de
probabilidade)
Hashing
1
2
A
3
B
4
C
5
D
6
E
7
F
8
G
9
10
• Caso 1 – Melhor
caso.
– A função hash é
perfeita.
Hashing
1
2
A
3
B
4
C
5
D
6
E
7
F
8
G
9
10
• Caso 2 – Pior caso.
– A função hash
apresenta muitas
colisões.
Hashing
1
2
A
3
B
4
C
5
D
6
E
7
F
8
G
9
10
• Caso 3 – Aceitável.
– A função hash
apresenta algumas
colisões.
Hashing
• Funções HASH
– Método da divisão : divide-se a chave x pelo
tamanho da tabela e o resto da divisão é
usado como endereço-base.
• H(x) = x % m
Hashing
• Funções HASH
– Método da dobra (XOR) : Este método transforma uma
chave de k bits (2k > m) em uma chave de j elementos,
tal que 2j ≤ m. Para isso pegamos os k/2 bits da
esquerda e realizamos um XOR com os k/2 bits da
direita, resultando em uma nova chave de k/s bits.
Repetimos o processo até que a chave gerada tenha j
bits.
Exemplo: m = 32, chaves de 10 bits (quanto vale j neste caso?)
71 = 00010 00111  00010 XOR 00111 = 00101 = 5
46 = 00001 01110  00001 XOR 01110 = 01111 = 15
Hashing
• Funções HASH
– Método da análise de dígitos;
– Método do meio do quadrado;
Hashing
• Tratamento de Colisão
Como já vimos, anteriormente, é impossível
evitar que ocorram colisões. Um método para
diminuir o número de colisões é diminuir o fator
de carga da tabela, que é definido por
α = n/m
Essa preocupação deve ser tomada quando o
número de colisões cresce rapidamente
quando o fator de carga aumenta. No entanto,
tal providência não é suficiente.
Hashing
• Encadeamento exterior
Cada endereço guarda um ponteiro para uma
lista (inicialmente vazia). Cada entrada é
colocada na posição final da fila referente a
seu endereço. Algoritmos de inserção,
remoção e busca são semelhantes aos de uma
lista comum.
Hashing
• Encadeamento exterior
Custo médio de busca sem sucesso
1 m
n
CM   Li   
m i 1
m
Onde |Li| é o comprimento da fila i
Hashing
• Encadeamento exterior
Custo médio de busca com sucesso
1 n1 
j
n(n  1)
 1
CM   1    1 
 1 
n j 0  m 
2nm
2 2m
Hashing
• Encadeamento interior
Em algumas aplicações, não é desejável a
manutenção de uma estrutura exterior à
tabela hash. Neste caso podemos
implementar listas encadeadas, desde que
estas compartilhem o mesmo espaço de
memória da tabela hash. Desta forma,
dividimos a tabela T em uma área de
endereços, de tamanho p, e uma área de
sinônimos, de tamanho s (s+p = m). Assim,
a função h deve gerar valores em [0..p-1] e
n/m deve ser menor ou igual a 1.
Problema ?
Hashing
• Encadeamento interior
Em algumas aplicações, não é desejável a
manutenção de uma estrutura exterior à
tabela hash. Neste caso podemos
implementar listas encadeadas, desde que
estas compartilhem o mesmo espaço de
memória da tabela hash. Desta forma,
dividimos a tabela T em uma área de
endereços, de tamanho p, e uma área de
sinônimos, de tamanho s (s+p = m). Assim,
a função h deve gerar valores em [0..p-1] e
n/m deve ser menor ou igual a 1.
Overflow
Hashing
• Encadeamento interior
Outra forma de utilizarmos o
encadeamento interno é através da
não reserva de nenhuma área para
sinônimos. Esta técnica elimina a
ocorrência de overflow (uma vez
que n/m < 1), mas produz um efeito
indesejado que é a possibilidade de
colisão de duas chaves x e y onde
h(x) ≠ h(y). Este tipo de colisão é
chamado de colisão secundária.
Hashing
• Remoção
Outro problema sério em uma
tabela hash é a remoção de uma
chave. Neste método, sentiremos
ainda mais os efeitos da eliminação
de uma chave da tabela. Notem que
não podemos simplesmente abrir
um buraco na lista encadeada, o
que criaria problemas (quais?).
Como resolver?
Hashing
• Endereçamento aberto
Neste método, as colisões da tabela
não são encadeadas como no
método de encadeamento interior...
Não há ponteiros. Quando houver
alguma
colisão,
determina-se,
através de uma nova função, qual o
próximo endereço a ser examinado.
Desta forma, teremos uma função h
que leva em conta qual tentativa
estamos realizando:
h(x,k)
onde k indica a k-ésima tentativa.
K=0
Hashing
• Endereçamento aberto
Para encontrar a chave x, deve-se
tentar o endereço-base h(x,0). Caso
esteja ocupado por alguma outra
chave, calcula-se o endereço h(x,1),
e assim por diante, até que a chave
seja encontrada ou h(x,k) aponte
para uma posição vazia.
K=1
Hashing
• Endereçamento aberto - remoção
A remoção de chaves da tabela exige
cuidados especiais. No método do
endereçamento aberto, a remoção
apresenta um problema semelhante
àquele do método do encadeamento
interior. Uma chave não pode ser
removida, de fato, da tabela, pois faria
romper a seqüência de tentativas. A
solução é semelhante à empregada no
método anterior.
K=2
Hashing
• Endereçamento aberto – tentativa linear
A idéia consiste em tentar armazenar a nova chave x
no endereço-base h’(x). Se não for possível, tenta-se
no endereço consecutivo h’(x) + 1. Se este já estiver
ocupado, tenta-se h’(x) + 2... Até que uma posição
vazia seja obtida ou ...(???) Lembre-se que devemos
simular uma lista circular.
h(x,k) = (h’(x) + k) mod m
Problema : longos trechos consecutivos de memória
ocupados, o que se denomina agrupamento
primário.
Hashing
• Endereçamento aberto – tentativa quadrática
A idéia consiste em se obter seqüências de endereços
distantes para endereços-base próximos. Para isso,
utilizamos como incremento, uma função quadrática
em k:
h(x,k) = (h’(x) + c1k + c2k2) mod m
Problema: Consegue evitar os agrupamentos
primários da tentativa linear, mas não impede
agrupamentos de chaves com mesma tentativa inicial.
Os agrupamentos obtidos neste caso são chamados
de secundários.
Hashing
• Endereçamento aberto – double hashing
O método calcula a seqüência de tentativas, de
acordo com a seguinte equação:
h(x,k) = (h’(x) + k.h’’(x)) mod m
Esse método tende a distribuir as chaves na tabela
de forma mais conveniente do que os dois
anteriores. Se x e y são duas chaves distintas, tais
que h’(x) = h’(y), então as seqüências de tentativas
obtidas pelos métodos da tentativa linear e
quadrática são necessariamente idênticas, o que
ocasiona agrupamentos.
Hashing
Load
SUCESSO
FRACASSO
Factor Linear Quad Doubl Linear Quad Double
%
25
1.17 1.16 1.15
1.39 1.37
1.33
50
1.50
1.44
1.39
2.50
2.19
2.00
75
2.50
2.01
1.85
7.50
4.64
4.00
90
5.50
2.85
2.56
50.50 11.40
10.00
95
10.50
3.52
3.15
200.5 22.04
20.00
Hashing
Tam.
SUCESSO
Tabela Linear Quad Double
100
FRACASSO
Linear
6.60
4.62
4.12
50.50
500 14.35
6.22
5.72
250.50
1000 20.15
6.91
6.41
500.50
5000 44.64
7.52
7.02
2500.50
10000 63.00
7.21
7.71
5000.50
Hashing
• Abordagem Matemática
Quando projetamos uma tabela hash, devemos ter
conhecimento estatístico prévio sobre alguns dados
como:
a) prob. de um dado endereço não ser preenchido;
b) prob. de um dado endereço conter exatamente
uma chave;
c) prob. de um dado endereço conter mais de uma
chave.
Hashing
• Abordagem Matemática
A probabilidade de um evento ocorrer exatamente x
vezes num total de r tentativas é dada por:
r x
rx
p( x)   .a .1  a 
 x
onde a é a probabilidade do evento ocorrer uma vez.
Hashing
• Abordagem Matemática
Quando relacionamos este tipo de evento a endereços
em uma tabela hash, podemos dizer que a = 1/m,
onde m é o tamanho da tabela. Desta forma, podemos
calcular a probabilidade de um certo endereço conter
x chaves em uma tabela com r chaves e tamanho m:
 r  1 
p( x)   . 
 x m
x
 1
.1  
 m
rx
Hashing
• Abordagem Matemática
Entretanto, quando m e r são grandes, dizemso que
p(x) tende a:
x
 r  r / m
  .e
m

p ( x) 
x!
Que é conhecida como distribuição de Poisson.
Hashing
• Abordagem Matemática
Exemplo: Suponhamos que existam 1000 endereços
(m=1000) e 500 chaves (r = 500). Se multiplicarmos
1000 pela probabilidade de um dado endereço conter
x chaves associadas a si, teremos o valor esperado do
número de endereços com x chaves (E(x)). Portanto,
E(X) = m.p(x)
x
 r  r / m
  .e
m

p ( x) 
x!
Hashing
• Abordagem
Matemática
x
Com 1000 endereços
(m=1000)
e
500
chaves (r = 500).
Quantos
endereços
devem estar desocupados?
R.: 607
 r  r / m
  .e
m

p ( x) 
x!
0
 500  500 /1000

 .e
1000

1000. p(0)  1000.
0!
Hashing
• Abordagem Matemática
Com 1000 endereços (m=1000) e 500 chaves (r =
500). Quantos endereços devem ter exatamente
uma chave associada a si?
R.: 303
x
 r  r / m
  .e
m

p ( x) 
x!
1
 500  500 /1000

 .e
1000
1000. p(1)  1000. 
1!
Hashing
• Abordagem Matemática
Com 1000 endereços (m=1000) e 500 chaves (r =
500). Quantos endereços devem ter mais de uma
chave associada a si?
R.: 90  m [p(20 + p(3) + ... +p(m)]
= m. (1 – [p(0)+p(1)]) = 90
x
 r  r / m
  .e
m

p ( x) 
x!
1
 500  500 /1000

 .e
1000
1000. p(1)  1000. 
1!
Hashing
• Abordagem Matemática
Com 1000 endereços (m=1000) e 500 chaves (r =
500). Assumindo uma chave por endereço, quanto
de overflow pode ser esperado?
R.: 107  m [1.p(2) + 2.p(3) + ...]
O que indica 107 / 500 = 21.4%
Hashing
• Buckets para tabelas hash
Na maioria das vezes, quando estamos
trabalhando com arquivos, o número de acessos
ao disco é fator crítico ao invés do custo
computacional.
Além
disso,
sempre
que
recuperamos alguma informação do disco, não
lemos apenas o número de bytes correspondentes
à informação desejada, mas sim um bloco (ou
mesmo um conjunto de blocos). O bucket é uma
estrutura capas de armazenar o máximo de
chaves que podem ser recuperadas com um único
acesso a disco. Assim, cada endereço da tabela
hash corresponderá a várias chaves.
Hashing
• Eficiência dos buckets
Quando tínhamos 1 chave
por endereço, havíamos
definido o fator de carga
como sendo α = r / m, onde
r é o número de chaves e
m o tamanho da tabela.
Agora, seja b o número de
chaves por bucket:
r

b.m
Hashing
• Eficiência dos buckets
Quando armazenamos 750 chaves em
1.000 endereços de tamanho 1 temos:
750

 0.75
1000
Hashing
• Eficiência dos buckets
Quando armazenamos 750 chaves em
500 endereços de tamanho 2 temos:
750

 0.75
1000
Hashing
• Eficiência dos buckets
O cálculo do overflow para o caso 1 é:
m . [1.p(2) + 2.p(3) + 3.p(4) + ...] = 222
O mesmo cálculo para o caso 2 é
m. [1.p(3) + 2.p(4) + ...] = 140
Enquanto o primeiro caso obteve um valor esperado
de 222 chaves em overflow (29,6%), o segundo caso
obteve 140 chaves (18.6%). Buckets maiores
diminuem ainda mais a porcentagem de overflow.
Hashing
Carga
%
Tamanho do bucket
1
2
5
10
100
70
28.1
17.0
7.1
2.9
0.0
75
29.6
18.7
8.6
4.0
0.0
80
31.2
20.4
10.3
5.3
0.1
90
34.1
23.8
13.8
8.6
0.8
100
36.8
27.1
17.6
12.5
4.0
Hashing
• Extendible hashing
Arquivos que crescem ou diminuem muito
rapidamente causam, em tabelas hash estáticas
(como as que vimos até o presente momento), uma
queda significativa de desempenho tanto pelo alto
custo computacional gasto com overflow (tabelas
pequenas) quanto pelo alto número de acessos a
disco (tabelas maiores). O extendible hashing é um
tipo de hashing dinâmico capaz de se ajustar a
tabelas que crescem ou diminuem rapidamente,
mantendo as características de acesso “direto” do
hashing, sem perder desempenho (CPU e disco).
Hashing
• Extendible hashing
Definição : No extendible hashing, cada valor de
h(x) é interpretado como uma seqüência de dígitos
binários que servirão de índice para a busca da
chave x. As chaves, por sua vez, serão
armazenadas em buckets. Todas as chaves de um
bucket possuem os i primeiros bits iguais, onde i é
chamado de profundidade do bucket.
Hashing
• Exemplo
Suponhamos que haja um bucket A, cuja função
h(x) tenha gerado valores iniciados pelos bits 01;
um bucket B cujos bits iniciais sejam 10 e um
bucket C com bits iniciais 11. Poderíamos
representar esta situação em uma árvore como a
seguinte:
A
0
0
B
1
1
C
Hashing
• Exemplo
Entretanto, uma estrutura de árvore não pode
prover acesso “direto” que é o que desejamos.
Desta forma, devemos mapear nossa “árvore” para
uma outra árvore completa e depois, para um array,
cujo acesso será direto:
A
0
00
01
0
B
1
10
11
1
C
Hashing
• Crescimento
00
01
10
A
B
11
C
Hashing
• Crescimento
A
00
01
10
D
B
11
C
Hashing
• Crescimento
00
01
10
A
B
11
C