Estruturas de Dados
Hashing
Prof. Ricardo J. G. B. Campello
Parte deste material é baseado em adaptações e extensões de slides
disponíveis em http://ww3.datastructures.net (Goodrich & Tamassia).
Motivação
Árvores AVL permitem realizar as operações
básicas de busca, inserção e remoção de itens
em tempo O(log n), o n é o no. de itens
É possível conseguir desempenho melhor ???
1
Hashing
Uma abordagem para tentar obter desempenho
superior àquele das árvores AVL é conhecida
como hashing
Essa abordagem utiliza uma estrutura de dados
denominada tabela hash
Também denominada tabela de dispersão
Tabela Hash
Uma tabela hash para um dado tipo de chave
consiste de:
Uma função hash h
Um arranjo (tabela) de tamanho N
Uma função hash h mapeia chaves de um dado
tipo em inteiros em um intervalo fixo [0, N − 1]
O valor inteiro h(k) ∈ [0, N − 1] é chamado de valor
hash da chave k
2
Tabela Hash
Aplicação em Mapas / Dicionários:
Item com chave k armazenado no índice i = h(k)
da tabela
O índice é calculado, não procurado
Tabela Hash - Exemplo
Tabela hash para um mapa
armazenando itens (CPF,
Dados Pessoais), onde a
chave CPF é um inteiro
positivo com 11 dígitos
h(k) = 4 últimos dígitos de k
∅
9997
9998
9999
∅
025.612.000-01
981.101.000-02
∅
451.229.000-04
…
No exemplo ao lado utilizase um arranjo de tamanho
N = 10.000 e a seguinte
função hash:
0
1
2
3
4
200.751.799-98
∅
Pode haver conflitos...?
3
Colisões
Colisões ocorrem quando diferentes
chaves são mapeadas sem distinção
na mesma célula da tabela
Colisões podem ocorrer tanto na
fase de codificação das chaves (h1)
como na fase de compressão (h2)
Ocorrendo na fase de codificação,
não há como serem revertidas na
fase de compressão
Colisões requerem tratamentos a
posteriori que, por sua vez,
demandam esforço computacional
Funções hash devem ser simples e
rápidas de calcular, minimizando ao
máximo colisões
0∅
1
2∅
3∅
4
612-0001
229-0004
101-0004
Note que é impossível
evitar completamente
colisões se o fator de
carga (load factor) λ de
uma tabela hash for λ>1
Esse fator é definido
como a razão entre o no.
n de chaves pelo tamanho
da tabela N: λ = n/N
Funções Hash
Uma função hash é composta das
seguintes sub-funções:
Código Hash (hash code):
h1: chaves → inteiros
Função de Compressão:
h2: inteiros → [0, N − 1]
Usualmente, quando se assume
que já se dispõe de uma
codificação inteira das chaves,
refere-se à função de compressão
sozinha como “função hash”
O código hash (quando
necessário) é aplicado
primeiro; em seguida a
função de compressão é
aplicada ao resultado:
h(k) = h2(h1(k))
A meta da função hash é
“dispersar” as chaves de
forma que essas ocupem
a tabela da forma mais
uniforme possível
4
Códigos Hash
Casting:
Interpretação dos bits da chave como um inteiro
Por exemplo, para chaves numéricas em ponto
flutuante:
k = m*10−e
Uma alternativa é somar os inteiros
correspondentes à mantissa e o expoente do
número em representação de ponto flutuante
h1(k) = m + e
Códigos Hash
Soma de Componentes:
A idéia de somar inteiros correspondentes a partes de uma
representação pode ser estendida para qualquer chave k que
possa ser representada por uma série k0, k1, ..., km−1 de inteiros
Em outras palavras:
m−1
h1 (k ) = ∑ ki
i =0
Útil em muitos casos, mas incapaz de distinguir chaves distintas
que diferem entre si apenas pela ordem das componentes ki
Esse é o caso de chaves tipo string, representadas como séries
de inteiros dados pelos códigos ASCII de cada um dos seus
caracteres (ou pela ordem alfabética do caractere)
5
Códigos Hash
Acumulação Polinomial:
Ao invés de uma soma simples, utiliza-se o seguinte
polinômio:
h1(k) = k0 + k1 a + k2 a2 + … + km−1am−1
para um valor fixo de a
Funciona bem, em especial para strings
p. ex. as escolhas empíricas a = 33, 37, 39 ou 41 geram em
torno de apenas 6 colisões para 50.000 palavras em Inglês !
Muitas vezes basta tomar apenas um subconjunto dos m (p.
ex. 10) primeiros / últimos caracteres da string
Códigos Hash
Acumulação Polinomial (Nota):
h1(k) = k0 + k1 a + k2 a2 + … + km−1am−1
Esse polinômio pode ser avaliado em tempo O(m)
utilizando a Regra de Horner:
Os seguintes polinômios são calculados recursivamente em
tempo O(1):
p0(k) = km−1
pi (x) = km−i−1 + api−1(k)
i = 1, 2, …, m −1
Tem-se h1(k) = pm−1(k)
6
Funções de Compressão
Resto da Divisão:
h2(y) = | y | mod N
Exemplo:
Códigos hash: y = [200, 205, 210, 215, ..., 595, 600]
Para N = 101, tem-se:
h2(y) = [99, 3, 8, 13, ..., 90, 95]
pois os múltiplos de 101 são 101, 202, 303, 404, 505, ...
Note que não ocorre qualquer colisão nesse caso
Nota:
O módulo |.| permite lidar com códigos hash negativos...
mas faz com que esses conflitem com suas contrapartidas
positivas...
Funções de Compressão
Resto da Divisão (cont.):
O tamanho N da tabela é usualmente escolhido primo
A razão formal está relacionada com a teoria dos números
Informalmente, tem-se que padrões do tipo y = pN+q para q inteiro
positivo e p = 0,1,2,... são menos comuns em códigos hash para N
primo
Note que qualquer código hash seguindo este padrão possui o
mesmo valor h2(y) !
Exemplo: y = [200, 205, 210, 215, ..., 595, 600]
Para N = 101, já vimos que não ocorre qualquer colisão
Já para N = 100, cada código terá o mesmo valor hash de ao
menos outros 3 códigos !
7
Funções de Compressão
Resto da Divisão (cont.):
Heurística:
Estimar a quantidade de chaves n e definir N como o no.
primo que mais aproxima o fator de carga λ = n/N desejado
Exemplo:
n = 2000 chaves e fator de carga desejado λ = 3
escolhe-se N = 701 como no. primo mais próximo de 2000/3
Funções de Compressão
Existem outras funções de compressão:
Multiplicação-Divisão
Multiply, Add and Divide (MAD)
Funções Universais
De formas distintas, essas funções buscam reduzir a
sensibilidade à escolha de N e/ou minimizar a
probabilidade de colisões.
8
Tratamento de Colisões
Colisões ocorrem quando dois
itens são mapeados na mesma
célula da tabela
Um método simples e eficiente de
lidar com colisões que não podem
ser evitadas é conhecido como
encadeamento externo
0
1
2
3
4
∅
025-612-0001
∅
∅
451-229-0004
981-101-0004
ou separate chaining
Nesse método, cada célula da
tabela aponta (ponteiro) para
uma lista dos itens mapeados
naquela célula
O tempo adicional para percorrer
essas listas e o espaço extra para
armazená-las são as razões pelas
quais colisões devem ser evitadas
ao máximo
Rehashing: Em aplicações
dinâmicas, quando o número
de colisões aumenta muito em
função do fator λ = n/N,
pode-se criar uma nova tabela
e re-dispersar as chaves
Performance
Hipótese:
função hash eficiente, que distribua de maneira uniforme as
chaves, ou seja, distribuição de probabilidade de atribuição de
chaves é uniforme sobre o conjunto de células da tabela
O tamanho médio (esperado) das listas para separate
chaining é O(n/N)
Logo, fazendo o tamanho da tabela ser proporcional ao
número de chaves, ou seja, N ≡ O(n), faz-se o tamanho
médio das listas para separate chaining ser O(1)
Pode-se fazer isso estimando de antemão o no. típico de
chaves que estarão usualmente armazenadas na tabela
ou via rehashing ...
9
Performance (cont.)
Nesse caso, todas as operações (busca,
inserção e remoção) executam na média em
tempo constante assumindo que a função
hash e as operações de remoção e inserção
nas listas também executam em tempo cte.
No pior caso, quando todas as chaves são
mapeadas em uma mesma célula, recai-se
essencialmente na implementação baseada
em lista, com busca e remoção em O(n)
Porque inserção é O(1) mesmo nesse pior caso... ?
Comparação com AVL
Busca
Tabela
Hash
O(1)
Inserção Remoção Notas
O(1)
esperado
Árvores O(log n)
pior caso
AVL
O(1)
esperado
O(log n)
O(log n)
pior caso
pior caso
O(n) no pior caso para
busca e remoção
implementação simples
implementação complexa
10
Variantes e Casos Particulares
Endereçamento aberto: Denominada open addressing em
inglês, é uma estratégia de tratamento de colisões na qual um item
em colisão é alocado a uma outra célula disponível da tabela
Trata-se de uma abordagem voltada a aplicações onde se tem
restrições severas de memória, que podem ser minimizadas ao
preço de um maior esforço de processamento
A idéia é, em caso de conflito ao tentar inserir um novo item,
percorrer (sondar) a tabela buscando por uma célula não ocupada
Diferentes estratégias de sondagem:
linear, quadrática, hashing duplo...
Estratégias específicas também para busca e remoção de elementos
O fator de carga nunca pode exceder 1 pois cada célula da tabela
armazena um único item
Variantes e Casos Particulares
Endereçamento direto:
Denominado direct addressing em inglês, trata-se de um caso
muito particular de hashing onde as chaves são naturalmente
inteiros em {0, 1,..., N−1}
Nesse caso, a função hash é dispensável, não há colisões se
chaves forem únicas e todas as operações são O(1)
O problema é que, como não se pode reduzir N pois os valores
das chaves estão naturalmente entre 0 e N−1, perde-se o
controle sobre o fator de carga
Nesse caso, se o no. de chaves é tal que n << N, o endereçamento
direto implica uma perda de espaço pela alocação de uma tabela de
tamanho muito superior ao necessário
11
Variantes e Casos Particulares
Hashing Perfeito:
Em aplicações muito particulares onde o conjunto de chaves é
estático e conhecido a priori, pode-se projetar um hashing
perfeito
por exemplo, conjunto de palavras reservadas de uma linguagem
de programação (aplicação em compiladores)
Esse tipo de hashing executa todas as operações de busca,
inserção e remoção em tempo O(1) no Pior Caso
Exercícios Sugeridos
•
Capítulo 8 (Goodrich & Tamassia, 2002)
•
Capítulo 8 (Szwarcfiter & Markenzon, 1994)
•
Capítulo 5 (Ziviani, 2004)
24
12
Bibliografia
M. T. Goodrich & R. Tamassia, Data Structures and
Algorithms in C++/Java, John Wiley & Sons, 2002/2005
M. T. Goodrich & R. Tamassia, Estruturas de Dados e
Algoritmos em Java, Bookman, 2002
J. L. Szwarcfiter & L. Markenzon, Estruturas de Dados e seus
Algoritmos, LTC, 1994
N. Ziviani, Projeto de Algoritmos, Thomson, 2a. Edição, 2004
T. H. Cormen et al., Introduction to Algorithms, MIT Press,
2nd Edition, 2001
25
13