Tabelas de Dispersão
Algoritmos e Estruturas de Dados
Verão 2012
Cátia Vaz
1
Tabelas de endereçamento directo
n 
Endereçamento directo é usado quando o
universo de chaves é pequeno e todas as chaves
são distintas:
n 
Cada posição k, contêm (referência) o elemento com
chave k. Caso esse elemento não exista, T[k]=null.
Cátia Vaz
2
Tabelas de endereçamento directo:
desvantagens
n 
n 
n 
Se o universo U é muito grande, armazenar uma tabela T
de tamanho |U| é impraticável.
O conjunto K de chaves que de facto foi armazenado pode
ser tão pequeno relativamente à dimensão do universo U
que a maior parte do espaço alocado para T está a ser
desperdiçado.
Alternativa: tabelas de dispersão.
n  Embora procurar por um elemento numa tabela de
dispersão possa demorar o mesmo do que procurar um
elemento numa lista ligada ( Θ(N) no pior caso ), sob
certas condições, o tempo expectável para procurar
por um elemento numa tabela de dispersão é O(1).
Cátia Vaz
3
Tabelas de Dispersão
n 
As tabelas de dispersão (hash tables) são
estruturas de dados que associam chaves a valores.
n 
n 
Cada chave é transformada pela função de dispersão
num número que é utilizado para indexar num array para
encontrar os valores associados aquela chave.
As tabelas de dispersão utilizam:
n 
n 
n 
tabela base de indexação;
funções de dispersão (hash functions);
algoritmos para resolução de colisões (se necessário).
Cátia Vaz
4
Tabela Base
n 
Dispersão com índices livres:
n 
n 
n 
Quando o número de elementos pode
ser estimado à partida em N
Tabela de M elementos (M > N)
Dispersão por separação em
listas:
n 
n 
0
Quando o número de elementos a
guardar (N) é desconhecido
Tabela de M listas de elementos
(M < N)
M-1
0
...
...
...
...
...
M-1
...
Cátia Vaz
5
Função de Dispersão
n 
Uma função de dispersão:
n 
n 
n 
n 
n 
n 
Transforma a chave num inteiro [0;M-1] (M tamanho do
array);
Deve distribuir as chaves de forma uniforme e quase
aleatória;
Deve ser rápida de calcular;
Diferentes funções devem ser usadas para diferentes tipos
de dados.
Definição: Colisão - ocorre quando a função de
dispersão devolve o mesmo valor para chaves
distintas
Definição: Função de dispersão ideal - a
probabilidade de ocorrer uma colisão para duas
chaves distintas é 1/M.
Cátia Vaz
6
Função de Dispersão
n 
A função de dispersão mais usada é a divisão:
n 
Chaves pequenas (representáveis por uma palavra
de memória):
n 
n 
n 
tratar as chaves como inteiros (k)
h(k) = k % M
usar um número primo para M.
Cátia Vaz
7
Função de Dispersão
Chave k k%1000 k%1024 k%1021
32699
699
955
027
15114
114
778
820
41502
502
542
662
30444
444
748
835
81699
699
803
019
30651
651
955
021
23670
670
118
187
12219
219
955
988
75745
745
993
191
Cátia Vaz
8
Função de Dispersão
n 
Chaves longas (String)
n 
n 
n 
n 
usar cada caracter como um inteiro (valor da representação
ASCII)
h(k) = k % M
dar um peso a cada caracter correspondente à sua posição na
cadeia
usar um número primo para o tamanho da tabela
static int hash(String s, int M){
int h=0; a=127;
for(int i=0;i<s.length();i++){
h=(a*h + s.charAt(i))%M;
}
return h;}
Cátia Vaz
9
Resolução de Colisões
n 
Para uma tabela de tamanho M, quantas inserções
podem ser feitas até à primeira colisão?
Os algoritmos de resolução de colisões depende do tipo de tabela base
escolhido.
Cátia Vaz
n 
10
Resolução de colisões
n 
Algoritmos de resolução de colisões:
n 
n 
Dispersão com separação em listas, denominado
encadeamento externo (Separate Chaining).
Dispersão com índices livres, denominado
encadeamento interno (Open Addressing ):
n 
n 
n 
Procura Linear (Linear Probing);
Procura Quadrática (Quadratic Probing);
Dupla Dispersão (Double Hashing).
Cátia Vaz
11
Resolução de Colisões:
Encadeamento Externo (Separate Chaining)
n 
n 
n 
Cada posição da tabela tem uma referência para uma lista
Colisões são resolvidas adicionando o elemento ao início da
lista
Remoções são resolvidas removendo o elemento da lista
Ordem de inserção:
77
14
70
70, 72, 14, 77, 19, 75
72
75
hash(k) = k mod 7
19
12
Resolução de colisões:
Encadeamento Externo (Separate Chaining)
13
Resolução de colisões:
Encadeamento Externo (Separate Chaining)
public interface HashFunction<E> {
int hashCode(E e);
boolean equals(E e1, E e2);}
/*Função Hash por omissão*/
public class HashDefaultFunction implements HashFunction<Object> {
private static HashFunction<Object> instance = null;
public static HashFunction<Object> getDefaultInstance(){
if(instance == null) instance = new HashDefaultFunction();
return (HashFunction<Object>)instance;}
public int hashCode(Object o){ return o.hashCode(); }
public boolean equals(Object o1, Object o2){
return o1 == null ? o2 == null : o1.equals(o2);}
private HashDefaultFunction(){}
}
Cátia Vaz
14
Resolução de colisões:
Encadeamento Externo (Separate Chaining)
public class ChainingHashTable<E> {
static class Node<T>{
T value;
Node<T> next;
Node(T v){ value = v;}
}
Node<E>[] v;
int m;
HashFunction<E> ho;
public ChainingHashTable(int len){
this(len,(HashFunction<E>)HashDefaultFunction.getDefaultInstance());}
public ChainingHashTable(int len, HashFunction<E> ho){
v = (Node<E>[]) new Node[len];
m = len;
this.ho = ho; } //(...)}
Cátia Vaz
15
Resolução de colisões:
Encadeamento Externo (Separate Chaining)
public class ChainingHashTable<E> {
//(...)
public class ChainingHashTable<E> {
//(...)
private final int index(E e){
int h=ho.hashCode(e)% m;
return (h<0)?h+m:h;}
public final E search(E key){
int i = index(key);
Node<E> curr = v[i];
while(curr != null){
if(ho.equals(key,curr.value))
return curr.value;
curr = curr.next;
}
return null;
}
public final void insert(E e){
int i = index(e);
Node<E> n = new Node<E>(e);
n.next = v[i];
v[i] = n;}
//(...)}
//(...)}
Cátia Vaz
16
Resolução de colisões:
Encadeamento Externo (Separate Chaining)
public class ChainingHashTable<E> {
//(...)
public final boolean delete(E e){
int i = index(e);
Node<E> curr = v[i];
Node<E> prev = null;
while(curr != null){
if(ho.equals(curr.value,e)){
if(prev == null){ v[i] = v[i].next;}
else{ prev.next = curr.next; }
return true;
}
prev = curr; curr = curr.next;
}
return false;
}//(...)}
Cátia Vaz
17
Encadeamento Externo (Separate
Chaining): análise
n 
n 
Pior Caso do Encadeamento Externo: todas as N
chaves têm o mesmo hash, criando uma lista de
comprimento N. θ(N).
Caso Médio. A performance da dispersão depende de
como a função de dispersão distribui as chaves a
serem armazenadas pelas M posições.
Para o análise do caso médio assume-se o princípio de
dispersão uniforme simples. O algoritmo de procura é:
n 
n 
n 
θ(1 + N/M).
se N=O(M) então O(1 + N/M)=O(1)
18
Resolução de colisões:
Encadeamento interno (Open Addressing )
Inserção: examinar
(probe) sucessivamente
a tabela de dispersão
até encontrar uma
posição vazia. A
sequência de posições
examinadas dependente
da chave a ser inserida.
A função de dispersão
inclui o número de vezes
que a tabela foi
examinada para aquela
chave
19
Resolução de colisões:
Encadeamento interno (Open Addressing )
Procura: examinar a
mesma sequência de
posições que o algoritmo
de inserção examinou
para uma dada chave. A
procura termina ou
quando: ou encontra a
chave; ou examinou M
posições; ou encontra
um espaço livre.
20
Resolução de colisões:
Encadeamento interno (Open Addressing )
Eliminação.
n  Não se pode colocar simplesmente a null na
posição da chave a ser eliminada.
algoritmo de procura inconsistente.
n 
Uma solução será colocar a posição da chave a
ser eliminada com um valor especial ao invés
de ser eliminada.
n 
implica modificação do algoritmo inserção
anterior.
n 
21
Algoritmos de resolução de colisões
Encadeamento interno (Open Addressing )
n 
Procura Linear (Linear Probing);
n 
Procura Quadrática (Quadratic Probing);
n 
Dupla Dispersão (Double Hashing).
h1 e h2, caso se use um m primo, poderão ser:
22
Resolução de Colisões:
Encadeamento Interno-Procura Linear
n 
N < M : método com índices livres.
n 
n 
Dado que há sempre posições livres na tabela, procurar
outra posição.
Procura linear:
n 
se a posição correspondente ao índice devolvido pela
função de dispersão estiver ocupada, ir incrementando o
índice até se encontrar uma posição livre.
0
70
1
14
2
72
3
77
Ordem de inserção: 70, 72, 14, 77, 19, 75
hash(k) = k mod 7
4
5
19
6
75
Cátia Vaz
23
Resolução de Colisões
Procura Linear (Linear Probing)
n 
Desempenho:
n 
n 
n 
n 
n 
os elementos tendem a ficar agrupados (clusters);
os agrupamentos grandes tendem a crescer ainda mais;
o tempo médio de procura tende a crescer para M à
medida que a tabela enche;
operações na tabela de dispersão tornam-se demasiado
lentas quando a tabela atinge 70% - 80% da sua
capacidade.
existem m sequências de examinação (probe) diferentes
24
Resolução de Colisões
Procura Quadrática (Quadratic Probing)
n 
Desempenho:
n 
tem melhores resultados que a procura linear;
n 
A função de hash inicial define a sequência;
n 
n 
elementos que têm a mesma função de hash têm
a mesma sequência logo também tendem a ficar
agrupados (secondary clusters);
Em caso de colisão, existem m sequências de
examinação (probe) diferentes
25
Resolução de Colisões
Dupla Dispersão (Double Hashing)
26
Resolução de Colisões
Dupla Dispersão (Double Hashing)
n 
Desempenho:
n 
é um dos melhores métodos de resolução;
n 
a sequência também depende da chave;
n 
elementos que têm a mesma função de hash têm sequências
distintas
n 
Em caso de colisão, existem m2 sequências de exame (probe)
diferentes
n 
n 
cada par possível (h1(k),h2(k)) assegura uma sequência de
examinação diferente.
Tem que se garantir que a tabela é pesquisada na totalidade:
n 
Usando um m que seja potencia de dois e desenhando h2(k) para produzir
sempre um número impar.
n 
Usando um m primo e desenhando h2(k) para produzir sempre um número
menor que m.
27