Buscar

13_Tabela Hash

Prévia do material em texto

1
Tabela Hash
1
Estrutura de Dados e 
Algoritmos
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Estruturas vistas até agora
2
� Estruturas lineares: vetor, fila, lista e pilha
� Ordenadas ou não
� Árvores Binárias de Pesquisa
� Ordenadas
� Heaps Binárias
� Chaves com certa ordem
� Todas são estruturas de busca e levam tempo até
encontrar o elemento desejado
8
2
6
4
1
9
5 2 6 1 7 8 4 9
5 2 6 1 4
2
Estruturas vistas até agora
3
� Estruturas lineares: vetor, fila, lista e pilha
� Ordenadas ou não
� Árvores Binárias de Pesquisa
� Ordenadas
� Heaps Binárias
� Chaves com certa ordem
� Todas são estruturas de busca e levam tempo até
encontrar o elemento desejado
8
2
6
4
1
9
5 2 6 1 7 8 4 9
5 2 6 1 4
Será que existe alguma
forma de estruturar os
dados para que as 
pesquisas sejam O(1)?
Problema
4
� Cenário:
� Suponha que desejamos ter inserção, remoção, pesquisa 
em O(1) para um sistema que gerencie os N discentes e 
docentes do DSC/UFCG? Assuma que cada pessoa 
possui um número identificador único no intervalo [1..N].
� Que estrutura de dados vocês escolheriam?
3
Tabela de Acesso Direto
5
Admitindo que K é relativamente pequeno
Tabela de Acesso Direto
6
� Poucos elementos
� Seja k ∈ U = {0,1,2...,m-1}
� Todas as chaves da tabelas são distintas
� Criar Array A
� A[0..m-1]
� A[k] = x, 
� se k = key[x]
� ou A[k] = null
1
3
4
6
7
80
/
/
/
/
/
/
/
key=2
João
key=9
Leila
key=5
Maria
2
5
9
Chaves (K)
h(k) = k
Acesso 
direto
4
Tabela de Acesso Direto
7
� Operações (inserir, remover, pesquisar) utilizando a 
tabela de acesso direto.
Direct-Address-Search(T, k)
return T[k]
Direct-Address-Insert(T, x)
T[key[x]] ← x
Direct-Address-Delete(T, x)
T[key[x]] ← NIL
Tabela de Acesso Direto (Problemas)
8
O que acontece se U for muito grande?
E se K for muito pequeno em relação a U?
O que acontece quando |U| é muito maior que length(T)?
5
Tabelas Hash
9
� Também conhecidas como tabelas de dispersão
� Resolve o problema quando |U| > length(T) 
mantendo o tempo de acesso em O(1) em média.
� Não usa a identidade para mapear chaves em
indices mas uma função de hashing.
� Se |U| > length(T) pelo menos duas chaves são
mapeadas para o mesmo índice (colisão)
� É impossível não ter colisões
� Elas devem ser minimizadas
}1,...,0{: −→ mUh
Tabela Hash
10
� Exemplo de colisão
)(kh
6
Características
11
� Não precisamos ocupar |U| posições na tabela
� Ocupamos menos espaço do que com a tabela de 
acesso direto
� Espaco: O(|K|), onde K é o conjunto de chaves 
guardadas
� Dá para conseguir acesso com tempo O(1) na média
� O elemento com chave k é guardado na posição 
h(k) da tabela
� h é a função hash 
� h tem que ser determinística
Exemplo
12
� Seja h(k)=k%10 uma função hash que mapeia de 
chaves do universo K em {2,5,9,100,107}. Considere 
uma tabela com m=10 células.
/
/
/
/
/
/
/
Universo de 
Chaves (U) 2 
...
9 
...
5 
...
2
5
9
K
7
Exemplo
13
� O que acontece se utilizarmos a função hash 
h(k)=k%10 para inserir os elementos {2,5,9,12}?
/
/
/
/
/
/
/
Universo de 
Chaves (U) 2 
...
9 
...
5 
...
2
5
9
12
Colisões
14
� Tabela hash ideal seria aquela sem colisão
� Impossível quando |U| > m (tamanho da tabela)
� Existem mais chaves que posições
� Duas ou mais chaves são mapeadas em um mesmo 
índice
� Escolher uma boa função hash para minimizar as 
colisões
8
Resolução de Colisões (Abordagens)
15
� Endereçamento fechado
� Elementos com mesmo código hash são colocados na 
mesma posição da tabela (chaining)
� Na verdade, inseridos na cabeça da lista já que existe a idéia
que o o elemento inserido será usado em breve
� Endereçamento aberto
� Chaves com mesmo código hash são colocadas em 
posições diferentes
Endereçamento Fechado: Chaining
16
� Usar uma lista encadeada
9
Exercício
17
� Implemente as operações (inserir, remover, 
pesquisar) utilizando a resolução de conflitos by
chaining.
� Inserir(T,x)
� Remover(T,x)
� Pesquisar(T,k)
Exercício
18
� Implemente as operações (inserir, remover, 
pesquisar) utilizando a resolução de conflitos by 
chaining?
� Inserir(T,x)
� Inserir x na cabeça de T[h(key(x))];
� Remover(T,x)
� Deletar x da lista T[h(key(x))];
� Pesquisar(T,k)
� Buscar x na lista T[h(k)];
10
Exercício
19
� Implemente as operações (inserir, remover, 
pesquisar) utilizando a resolução de conflitos by 
chaining?
� Inserir(T,x)
� Inserir x na cabeça de T[h(key(x))];
� Remover(T,x)
� Deletar x da lista T[h(key(x))];
� Pesquisar(T,k)
� Buscar x na lista T[h(k)];
Faça a análise do pior caso das operações (inserir, remover, pesquisar)
Exercício
20
� Qual seria a tabela final considerando 
endereçamento fechado (resolução por chaining) e 
função de hash h(k)=k%2 e chaves do universo 
K={2,4,6,8}?
11
Exercício
21
� Qual seria a tabela final considerando 
endereçamento fechado (resolução por chaining) e 
função de hash h(k)=k%2 e chaves do universo 
K={2,4,6,8}?
/
8 
...
2
4
6
6 
...
4 
...
2 
...
8
Fator de Carga
22
� A função h faz um hashing uniforme simples
� Chaves possuem igual probabilidade de serem 
mapeadas para qualquer um dos índices
� Cada célula da tabela vai ter um número mais ou 
menos igual de elementos
� Origina a noção de load factor (fator de carga) α
(numero médio de elementos em cada lista)
� n = número de chaves
� m = número de células na tabela
� α = n/m
� Exemplo: qual o fator de carga de uma tabela hash 
com 50 células e 100 chaves?
12
Exercício
23
� Qual o limite assintoticamente restrito usando o fator 
de carga (α) para uma pesquisa?
Exercício
24
� Qual o limite assintoticamente restrito usando o fator 
de carga (α) para uma pesquisa?
...
...
h(ki) 
...
h(kj) 
...
h(kn) 
...
...
T
i
Θ(1+ α)
Aplicar a 
função hash
13
Exercício
25
� Quando uma pesquisa será feita em Θ(1)?
Exercício
26
� Quando uma pesquisa será feita em Θ(1)?
� α = n/m = O(1)
� n = O(m)
...
...
h(ki) 
...
h(kj) 
...
h(kn) 
...
...
T
i
Θ(1+ α)
14
Exercício
27
� Vamos utilizar a função hash h(k) = k%m (m=10) 
para guardar os RGs. Qual o último dígito do RG de 
vocês? Como vai ficar a tabela hash depois de 
inserirmos todos os RGs de vocês? 
� Será que tem alguma função hash melhor?
Exercício
28
� Vamos utilizar a função hash h(k) = k%m (m=10) 
para guardar os RGs. Qual o último dígito do RG de 
vocês? Como vai ficar a tabela hash depois de 
inserirmos todos os RGs de vocês? 
� Será que tem alguma função hash melhor?
Como escolher uma função hash?
15
Características da Função Hashing
29
� Minimizar o número de colisões
� Satisfazer a hipótese de hashing uniforme
� Qualquer chave tem a mesma probabilidade de ser 
mapeada em qualquer um dos m slots. Mas é difícil
� Alguns métodos ajudam
� Divisão
� Multiplicação
� Consideramos as chaves como números
� Fácil de mapear Strings,... para números
Método da Divisão
30
� Usa o resto da divisão para encotrar valores hash
� Neste método a função hash é da forma:
� Método rápido (requer apenas uma divisão)
h(k) = k mod m Número de células da tabela
16
Exercício
31
� Seja K = {2,4,12,10,5}, desenhe a tabela final 
considerando as seguintes funções hash (utilize a 
resolução de conflitos por chaining). As tabelas 
possuem 2, 5 e 10 células
� h=k mod 2
� h=k mod 5
� h=k mod 10
Métododa Divisão
32
� O método da divisão garante boas funções de 
hashing?
� O que basicamente muda entre as funções hash no 
método da divisão?
� Qual(is) valor(es) escolhemos para m?
17
Método da Divisão
33
� O método da divisão garante boas funções de 
hashing?
� O que basicamente muda entre as funções hash no 
método da divisão?
� Qual(is) valor(es) escolhemos para m?
� Não escolha um m tal que tenha um divisor d bem 
pequeno
� Não escolha m = 2r, 
� Escolha m sendo um número primo que não seja 
próximo das potências de 2 ou 10
Exercício
34
� Suponha as chaves {200, 205, 210, 215, 220, ..., 
595}.
� Se eu escolher a função h(k) = k %100. Vai existir 
colisão em alguma célula? Se sim, quantas?
� Se eu escolher a função h(k) = k %101. Vai existir 
colisão? Se sim, quantas?
18
Exercício
35
� Suponha as chaves {200, 205, 210, 215, 220, ..., 
595}.
� h(k) = k %100 : Cada célula preenchida terá quatro chaves
� h(k) = k %101 : Cada célula preenchida terá uma chave
0
...
5
...
10
...
200, 300, 400, 500
205, 305, 405, 505
210, 310, 410, 510
101 202 303 404 505
200 205 210 215 220, ... , 295, 300
099 003 008 013 018, ... , 093, 098
305 310 315 320 325, ... , 395, 400
002 007 012 017 022, ... , 092, 097
Applet
36
� http://www.cse.yorku.ca/~aaw/Hang/hash/Hash.html 
� http://www.engin.umd.umich.edu/CIS/course.des/cis
350/hashing/WEB/HashApplet.htm
19
Método da Multiplicação
37
� Neste método a função hash é da forma:
� k é a chave
� A é uma constante entre (0..1)
� Um bom valor é
� m (número de células) geralmente é 2p, onde p é inteiro
� O valor de m não é crítico como no método da divisão
� Um pouco mais lento do que o da divisão
h(k) = �m (k.A mod 1)	
Extrai a parte fracionária de k.A
...6180339887.02/)15( =−≈A
Exercício
38
� Calcule o codigo hash h = �m (kA mod 1)	 das 
chaves ({2, 3, 4, 5, 6, 10, 15}), onde A = 0.2 e m = 
1000
h(2) = �1000 (2x0.2 mod 1)	 = 400
h(3) = �1000 (3x0.2 mod 1)	 = 600
h(4) = �1000 (4x0.2 mod 1)	 = 800
h(5) = �1000 (5x0.2 mod 1)	 = 000
h(6) = �1000 (6x0.2 mod 1)	 = 200
h(10) = �1000 (10x0.2 mod 1)	 = 000
h(15) = �1000 (15x0.2 mod 1)	 = 000
20
Tabela com Endereçamento Aberto
39
� Até agora vimos a resolução de conflitos por 
chaining (Endereçamento Fechado)
� Precisa de uma estrutura de dados auxiliar (lista)
� E se não tivermos listas para resolver as colisões?
� Precisamos de um número m bem maior de células.
� Chaves que colidam precisam ter seu hash code
“recalculado” para encontrar um slot vazio
� Todas as chaves estão em alguma célula. Cada entrada da 
tabela contém um elemento ou NIL
Outra Forma de Resolver Conflitos
40
� Endereçamento aberto faz uso de um probe.
� Examina a tabela (sequencial ou não) até encontrar um 
slot vazio. 
� A sequência de posições sendo examinadas dependem 
da chave.
� Função hash é estendida
� posição = h(k,p)
� k = chave
� p = probe
21
Exemplo: Inserção
41
� Insira a chave k=100
� Probe h(100,0)
� Probe h(100,1)
� Probe h(100,2)
200
/
/
150
/
/
/
999
/
/
100
Algoritmo: Inserção
42
22
Exemplo: Pesquisa
43
� Pesquisa a chave 
k=100
� Probe h(100,0)
� Probe h(100,1)
� Probe h(100,2)
200
/
/
150
/
/
/
999
/
/
Algoritmo: Pesquisa
44
23
Endereçamento Aberto (Deleção)
45
� Como fazer uma remoção com endereçamento
aberto?
� Podemos atribuir NIL diretamente na posição da chave a 
ser removida? 
Endereçamento Aberto (Deleção)
46
� Como fazer uma remoção com endereçamento
aberto?
� Não podemos simplesmente dizer que o slot esvaziou
colocando NIL
� Usar uma flag (valor especial DELETED) ao invés de NIL
� Alterar as funções 
� Inserir (inserir no flag se ele for DELETED)
� Pesquisar (continuar a pesquisa no flag ao invés de NIL)
24
Exemplo
47
� Remova a chave 
k=100
� Probe h(100,0)
� Probe h(100,1)
� Probe h(100,2)
� Pesquisar até achar a 
chave (remova –
coloque um flag 
DELETED) ou uma 
célula vazia
200
/
100
150
/
/
/
999
/
/
X
E como ficaria a inserção?
Exemplo
48
|| T[j] = DELETED
25
Hashing com Probing
49
� Como escolher a função hash no endereçamento 
aberto usando o probe?
� Por que não utilizar a função h(k,i) = k%m?
� Precisamos usar i para que o endereço mude.
� Três técnicas são usadas para computar as 
sequências de probes
� Linear Probing
� Quadratic Probing
� Double Hashing
Linear Probing
50
� Dada uma função de hash ordinária (obtida por
divisão ou multiplicação):
� O método usa a função de hash da forma: 
� Slots buscados linearmente:
� Fácil de implementar mas apresenta problemas
� Clustering Primário – clusters podem surgir quando slots 
ocupados se agrupam. Isso aumenta o tempo da busca.
}1,...,1,0{:' −→ mUh
mikhikh mod))('(),( +=
]1[
...
]1)('[
)]('[(
−
+
mT
khT
khT
26
Exercício
51
� Seja m=10, h(k) = k mod 5. Utilize o probing linear 
para inserir os valores ({10,15,2,12,4,8})
h(k,i) = (k mod 5 + i) mod 10
Probing Quadrático
52
� Neste método a função hash é da forma:
� c1 e c2 são constantes
� Primeiro elemento buscado T[h’(k)]. Demais variam com 
função quadrática de i.
� Evita o clustering primário
� Pode ocorrer um Clustering Secundário – duas chaves com 
mesmo probe inicial geram mesma sequência de probes
� Mas é melhor do que o anterior
Método da Divisão ou Multiplicação
micickhikh mod))('(),( 221 ++=
27
Exercício
53
� Seja m=10, c1=3, c2=5, h(k) = k mod 5. Utilize o 
probing quadrático para inserir os valores 
({10,15,2,12,4,8}):
h(k,i) = (k mod 5 + 3i + 5i2) mod 10
Exercício
54
� Compare a resposta anterior com o linear probing e 
o endereçamento fechado (h(k) = k mod 10) com 
chaining para inserir os valores ({10,15,2,12,4,8}):
h(k) = k mod 10
h(k,i) = (k mod 5 + i) mod 10
h(k,i) = (k mod 5 + 3i + 5i2) mod 10
28
Hashing Duplo
55
� Um dos melhores métodos para endereçamento aberto
� Neste método a função hash é da forma:
� A sequência de probe depende de duas formas em k.
� Dicas
� Faça h2(k) retornar um número ímpar e m ser um número 2p
� Faça m ser um numero primo e h2(k) retornar um inteiro positivo 
menor que m
� Excelentes resultados
� Produz Θ(m) sequências (se aproxima mais do hashing 
uniforme simples)
Método da Divisão ou Multiplicação
mkhikhikh mod))(.)((),( 21 +=
Exercício
56
� Seja m=24, h1(k) = k mod 5 e h2(k) = k+1 mod 7. 
Utilize o hashing duplo para inserir os valores 
({10,15,2,12,4,8}):
h(k,i) = (k mod 5 + (k+1 mod 7).i) mod 24
29
POSCOMP 2009
57
Fator de Carga
58
� Qual o fator de carga no endereçamento aberto?
� O load factor é ≤1
� Por que?
30
Lidando com Overflow
59
� O que fazer quando o vetor interno da tabela hash 
ficar cheio?
� Duplicar quando estiver cheio?
� Duplicar quando atingir uma certa capacidade?
Rehashing
60
� Quando a capacidade preenchida (exceder 50%), as 
operações na tabela passam a demorar mais, pois o 
número de colisões aumenta
� Expandir o array que constitui a tabela, e 
reorganizar os elementos na nova tabela
� Novo tamanho: número primo próximo ao dobro da tabela 
atual
31
Exemplo
61
Tamanho = 13
34 40 X 11 95
3440 1195
Tamanho = 7
Object put() { ...
if (++size > threshold)
rehash(); ...
}
void rehash() { ...
newcapacity = prime number near 2*buckets;
buckets = new HashEntry[newcapacity];
threshold = (int) (newcapacity * loadFactor); ...
}
Exercício
62
� Quando devemos fazer o rehashing?
� No endereçamento aberto não conseguirmos mais inserir 
um elemento
� Quando metade databela estiver ocupada (limite de 
capacidade)
32
Implementação
63
� Hashtable
� http://www.docjar.com/html/api/java/util/Hashtable.java.html
� Ver funções
� hash()
� O código hash é delegado para cada classe
� containsKey()
� get()
� put()
� remove()
� rehash()
� equals( ) x hashCode( ). 
� a.equals(b) → hashCode(a) = hashCode(b) 
Tabela Hash (Implementação)
64
� Como seria representada uma tabela hash em 
Java?
public interface Hashtable<T> {
public boolean isEmpty();
public boolean isFull();
public int capacity();
public int size();
public void insert(T element);
public void remove(T element) ;
public T search(T element);
public int indexOf(T element);
}
33
Tabela Hash (Implementação)
65
� Separando a tabela de sua função hash?
Hashtable HashFunction
Tabela Hash (Implementação)
66
� Separando a tabela de sua função hash?
Hashtable HashFunction
HashFunctionClosedAddress
int hash(Object element)
HashFunctionOpenAddress
int hash(Object element, int probe)
HashFunctionDivision
HashFunctionMultiplication
HashFunctionLinearProbing
HashFunctionQuadraticProbing
HashFunctionDoubleHashing
34
Tabela Hash (Implementação)
67
� Separando a tabela de sua função hash?
Hashtable HashFunction
HashFunctionClosedAddress HashFunctionOpenAddress
HashFunctionDivision
HashFunctionMultiplication
HashFunctionLinearProbing
HashFunctionQuadraticProbing
HashFunctionDoubleHashing
HashtableClosedAddress HashtableOpenAddress
Referências
68
� Capítulo 12
� 1a edição
� Capítulo 11
� 2a edição

Outros materiais