Hashing Extensível
• o espaço de endereços disponíveis não é fixo
• utilizado em hashing de arquivos dinâmicos (mudam de tamanho)
ideia: combinar técnicas de hashing + árvore de busca de base (trie)
Exemplo 1:
Trie: (able, abrahms, adams, anderson, andrews, baird)
b
l
able
r
abrahms
d
a
adams
e
n
anderson
d
b
r
baird
andrews
26 letras do alfabeto, a-z  máximo fator de subdivisão de um nó = 26 (base 26)
Exemplo: base 10
Trie: (1136, 1153, 1629, 3182, 7263, 7268, 7521)
1
3
1136
5
1153
1629
6
1
3
3182
7
7263
8
7268
6
2
5
3
5
7521
Hashing e tries
• Trabalha-se com árvores de base 2
• As chaves nas folhas constituem buckets contendo chaves
A
0
1
0
1
B
Parte do
endereço
C
01
10
11



Bucket
A
B
C
Problema: Como representar uma trie de modo a se obter uma busca
com complexidade constante O(1) ?
Ideia : Considerar um vetor de endereços hashing, com cada
elemento apontando para um bucket, e obtido a partir da
definição de uma árvore binária completa dos respectivos
endereços.
A
0
1
0
B
1
C
árvore binária completa
0
A
0
1
1
0
B
1
C
0
A
0
1
1
0
B
1
C
vetor de endereços
apontador extra para eventual overflow de A
00
01
A
10
B
11
C
2 níveis na árvore binária  vetor de tamanho 4
apontador extra para eventual overflow de A
00
A
01
10
B
11
C
00
A
01
D
10
B
11
C
overflow de A
Exemplo:
0
A
0
1
1
0
1
00
01
B
C
A
10
B
11
C
Overflow do bucket B  subdividir o ramo da árvore conduzindo
ao bucket B; criar a árvore binária completa; definir o vetor de
endereços
• Subdivisão do ramo da árvore
A
0
1
0
B
1
D
0
1
C
• Criação da árvore binária completa
0
0
1
0
A
0
1
1
1
0
B
1
D
0
1
0
C
1
3 níveis na árvore binária  vetor de tamanho 8
• Definição do vetor de endereços
000
001
010
A
011
100
B
101
D
110
111
C
Busca por Casamento Parcial
• evita definição de listas invertidas na consulta de registros por
chaves secundárias
• baseia-se no conceito de códigos de assinaturas
Exemplo de registro
Aluno:
RA
bits
Nome
Cidade
1
16
s1
CR
17
21
s2
Renda Familiar (RF)
22
26 27
s3
32
s4
assinaturas disjuntas
(diferentes funções de hashing)
• Os bits de cada campo dos registros terão valor 1 de acordo com as respectivas
funções de hashing
Exemplos de assinaturas:
s1  hash(Nome) mod 16  1
 1 , se cidade começacom A - E
 2, se cidade começacom F - J

s2  3, se cidade começacom K - M
 4, se cidade começacom N - R

 5, se cidade começacom S - Z
(para bits de 1 a 16)
(para bits de 17 a 21)
 1 , se 0  CR  2
 2, se 2  CR  4


s3   3, se 4  CR  7
4, se 7  CR  8
5, se 8  CR  10


1, se RF  1000,00
2, se 1000 RF  2000,00

3, se 2000,00 RF  4000,00
s4  
4, se 4000,00 RF  7000,00
5, se 7000,00 RF  10000,00

6, se RF  10000,00
(para bits de 22 a 26)
(para bits de 27 a 32)
A busca
Exemplo de consulta:
RF = 3000,00 AND CR = 8 AND Cidade = Campinas
Assinatura da consulta:
1
16
17
21
22
1
s1
25
1
s2
s3
26 27 29
32
1
s4
Extrair todos os registros cuja assinatura contém 1 na posição indicada pela
assinatura de consulta; verificar os falsos positivos devido a oclusões da função
de hashing
 Extrair registros que respondem positivamente à pergunta:
NOT (assinaturade registros)AND (assinatura de consulta)   ?
Árvores de Assinaturas
• Combina as assinaturas de registros numa estrutura multínivel de
árvores, através de um OR de diferentes subconjuntos destas assinaturas
• Otimiza o processo de busca secundária por assinaturas de registros
..
assinatura da consulta: 0 0 0 1 0 01
.
OR
OR
0 0 0 1 0 01
0 0 0 1 0 01
assinaturas
nível 1
(adicionadas aos
registros originais)
.
.
.
assinaturas
nível 2
sub-árvore a ser verificada na
consulta
assinaturas
nível 3