algoritmos e estrutura de dados 3-Hashing

Prévia do material em texto

UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados III. 
TABELAS HASH 
(Tabelas de Espalhamento ou Tabelas de Dispersão) 
 
1. Introdução 
 
Os algoritmos que realizam a pesquisa linear (complexidade O(N)) e a pesquisa binária 
(complexidade O(log2N)) comparam a chave procurada com todas ou com parte das chaves 
armazenadas na estrutura de dados que contém os registros, logo o tempo médio de resposta dos 
mesmos aumenta com o aumento do número N de registros. 
Existe uma técnica surpreendentemente simples e eficiente chamada hashing, que permite 
armazenar e localizar um registro através de um cálculo aritmético baseado no valor de sua chave. 
Deste modo, o tempo de resposta médio para executar estas operações independe do tamanho da 
tabela, portanto são feitas a um custo constante, ou complexidade O(1). É aplicada principalmente em 
compiladores, verificadores de ortografia, gerenciadores de bancos de dados, entre numerosas 
outras aplicações. 
O princípio básico da técnica hashing é simples: em vez de o índice de cada registro ser 
definido segundo a posição relativa de sua chave em relação às demais, o índice é calculado de 
forma absoluta através de uma função conveniente, chamada função de hashing, ou função de 
espalhamento. Em outras palavras, a função de hashing transforma ou converte o valor da chave de 
cada registro num índice (endereço ou posição) da tabela hash (normalmente um vetor), permitindo 
armazenar e acessar diretamente cada registro. Estes índices calculados (endereços da tabela onde 
os registros serão armazenados e pesquisados) parecem ser aleatórios, não havendo uma conexão 
óbvia entre eles e as chaves que lhe deram origem. 
Infelizmente existe um inconveniente: duas ou mais chaves distintas podem ser indexadas 
com o mesmo índice de entrada na tabela e quando isso ocorre, diz-se que houve uma colisão. Como 
dois registros não podem ocupar a mesma posição na tabela, é necessária a utilização de algum 
método para contornar o problema das colisões. A inserção, pesquisa e exclusão de registros através 
de hashing consiste basicamente: 
1) Na transformação da chave K de cada registro num índice ou endereço, através de uma 
função h(K), chamada função de hashing, ou de espalhamento. 
2) No tratamento das colisões, que ocorrem quando dois ou mais registros com chaves 
distintas são indexados com um mesmo índice ou endereço. 
 
2. Funções de Hashing 
 
Uma função de hashing ideal deve ser facilmente computada e deve transformar os valores 
das chaves em índices uniformemente distribuídos, aparentemente aleatórios, para diminuir o número 
de colisões. Para uma tabela de tamanho M, a função de hashing h(K) deve gerar índices dentro do 
intervalo [0, M-1]. Qualquer função que contemple estes requisitos pode ser utilizada como função 
de hashing, todavia as funções mais utilizadas são as baseadas no método da divisão e da 
multiplicação. 
 
UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados III. 
2.1 Método da Divisão 
É simples e eficiente tanto no que diz respeito à rapidez (aritmética de inteiros) como no 
espalhamento dos registros, conforme a escolha do tamanho tabela. Consiste em dividir o valor da 
chave K pelo tamanho M da tabela, tomando-se como índice do registro o resto desta divisão: 
 
 h(K) = K mod M 
 
Chaves de outros tipos de dados como strings, por exemplo, podem ser facilmente 
transformadas em números inteiros, uma vez que toda informação é representada no computador 
como uma seqüência de bits, que pode ser interpretada como a representação binária de um inteiro. 
Para que haja uma distribuição mais uniforme dos registros e menor incidência de colisões, M 
não deve ser uma potência de 2, tampouco um número par. Mais que isso, é recomendável que M 
seja um número primo, não próximo de uma potência de 2. 
 
Exemplo 1: Determinar os índices dos registros com chaves iguais a [33 44 63 66 84 93] para uma 
tabela hash de tamanho 7. 
K h(K) = K mod 7 
33 5 
44 2* 
63 0** 
66 3 
84 0** 
93 2* 
 
Pode-se observar que os registros de chaves 44 e 93 foram indexados com índice 2 e os de 
chaves 63 e 84 foram indexados com o índice 0, ilustrando a ocorrência de duas colisões. 
 
2.2 Método da Multiplicação 
Também é um bom método, porém ligeiramente mais lento uma vez que requer operações de 
ponto flutuante. O índice do registro é obtido multiplicando-se a parte fracionária do produto (K A) pelo 
tamanho M da tabela, tomando-se o piso (parte inteira) desse produto: 
    mod 1h K K A M     
em que 0 < A < 1. Usualmente considera-se 
5 1
0.618033988749894848...
2
A

  
Exemplo 2: Determinar os índices dos registros com chaves iguais a [33 44 63 66 84 93] para uma 
tabela hash de tamanho 7. 
K     0,61803 mod 1 7h K K     
33 2 
44 1 
63 6* 
66 5 
84 6* 
93 3 
 
UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados III. 
 Agora os registros de chaves 63 e 84 colidiram no índice 6 da tabela. A principal vantagem 
deste método é que não há restrição quanto à escolha de M. 
 
3. Fator de Carga ()
 É a razão entre o número de registros e o tamanho da tabela:  = N / M. Quanto menor o fator 
de carga mais posições livres a tabela terá e menor será a probabilidade de duas ou mais chaves 
distintas serem indexadas como o mesmo índice ou posição da tabela. 
 
4. Tratamento de Colisões 
Por melhor que seja a função de hashing e por menor que seja o fator de carga sempre há a 
probabilidade de ocorrência de colisões, que são inerentes à técnica e, portanto, devem ser tratadas 
de algum modo. Basicamente existem dois métodos para o tratamento de colisões: encadeamento e 
endereçamento aberto. 
 
4.1 Encadeamento 
Consiste em criar não uma tabela de registros, mas uma tabela contendo M listas 
encadeadas (L1, L2, ..., LM) inicialmente vazias, ou apontando para nulo. Para armazenar um registro 
de chave K, acessa-se a lista encadeada Lp, na posição p = h(K). Se Lp estiver vazia, aloca-se 
memória para o primeiro nodo de Lp, dentro do qual o registro será armazenado. Se Lp não estiver 
vazia e a chave K não for localizada em Lp, através de uma pesquisa seqüencial “barata”, significa 
que houve uma colisão e um novo nodo será alocado e adicionado à Lp, para armazenar o registro. 
Cada lista encadeada terá em média = N / M registros, sendo possível  > 1. 
Exemplo 3: Armazenar seqüencialmente os registros com chaves [33 44 63 66 84 93] numa tabela 
hash de tamanho 7, com tratamento de colisões por encadeamento. 
 
K h(K) = K mod 7 
33 5 
44 2 
63 0 
66 3 
84 0 
93 2 
 
 
 
4.2 Endereçamento Aberto 
Neste método é necessário que M > N e a estratégia consiste em procurar sucessivos 
endereços alternativos para o novo registro até que um endereço livre seja encontrado. Assim, em 
vez da utilização de uma única função h(K), utilizam-se h0(K), h1(K), h2(K)..., tal que: 
hi(K) = (h(K) + f(i)) mod M i = 0, 1, 2, ..., M1 
h(K) = K mod M 
Conforme a escolha de f(i) tem-se: 
 
 
 
 
 
 
 
63 84 
44 93 
33 
66 
0 
1 
2 
 
3 
4 
 
5 
 
6 
 
 
UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados III. 
4.2.1 Hashing com teste linear: f(i) = i 
 
hi(K) = (h(K) + i) mod M 
 
Por procurar endereços alternativos adjacentes, este método tende a produzir seqüências de 
registros aglomerados (clustering) na tabela, tornando a pesquisa um pouco mais “onerosa”. 
Exemplo 4: Armazenar seqüencialmente os registros com chaves [33 44 63 66 84 93] numa tabela 
hash de tamanho 7, com tratamentode colisões por endereçamento aberto com teste 
linear. 
K i hi(K) = (h(K) + i) mod M 
33 0 (33 mod 7 + 0) mod 7 = 5 (ok) 
44 0 (44 mod 7 + 0) mod 7 = 2 (ok) 
63 0 (63 mod 7 + 0) mod 7 = 0 (ok) 
66 0 (66 mod 7 + 0) mod 7 = 3 (ok) 
84 
0 (84 mod 7 + 0) mod 7 = 0 (colisão) 
1 (84 mod 7 + 1) mod 7 = 1 (ok) 
93 
0 (93 mod 7 + 0) mod 7 = 2 (colisão) 
1 (93 mod 7 + 1) mod 7 = 3 (colisão) 
2 (93 mod 7 + 2) mod 7 = 4 (ok) 
 
4.2.2 Hashing com teste quadrático: f(i) = i2 
 
hi(K) = (h(K) + i
2) mod M 
 
Como são procurados endereços alternativos não adjacentes, evita-se a formação de 
agrupamentos, porém podem existir endereços livres na tabela que nunca são testados. Todavia isso 
não chega a ser um problema, a menos que a tabela contenha pouquíssimos endereços livres, o que 
pode e sempre deve ser evitado. 
Exemplo 4: Armazenar seqüencialmente os registros com chaves [33 44 63 66 84 93] numa tabela 
hash de tamanho 7, com tratamento de colisões endereçamento aberto com teste 
quadrático. 
K i hi(K) = (h(K) + i
2) mod M 
33 0 (33 mod 7 + 0) mod 7 = 5 (ok) 
44 0 (44 mod 7 + 0) mod 7 = 2 (ok) 
63 0 (63 mod 7 + 0) mod 7 = 0 (ok) 
66 0 (66 mod 7 + 0) mod 7 = 3 (ok) 
84 
0 (84 mod 7 + 0) mod 7 = 0 (colisão) 
1 (84 mod 7 + 1) mod 7 = 1 (ok) 
93 
0 (93 mod 7 + 0) mod 7 = 2 (colisão) 
1 (93 mod 7 + 1) mod 7 = 3 (colisão) 
2 (93 mod 7 + 4) mod 7 = 6 (ok) 
 
 
 
0 
1 
2 
 
3 
4 
 
5 
 
6 
 
63 
84 
44 
66 
93 
33 
 
0 
1 
2 
 
3 
4 
 
5 
 
6 
 
63 
84 
44 
66 
 
33 
93 
 
UFGD / FACET — Prof. Wellington Lima dos Santos — Algoritmos e Estruturas de Dados III. 
Exercícios 
 
1) Cite alguns exemplos mais comuns de aplicação da técnica hashing. 
 
2) Comente sobre as duas principais características que uma boa função de hashing deve possuir. 
 
3) O fator de carga () de uma tabela hash é definido como = N/M, em que N é o número de 
elementos e M é o tamanho da tabela. Com base nisso, pergunta-se: 
a) Qual das técnicas para tratamento de colisões abordadas no texto deve ser utilizada quando 
 > 1? Explique. 
b) Para uma tabela hash com N = 945,  = 0,84 e com tratamento de colisões por endereçamento 
aberto, quantos endereços livres restarão após a inserção de todos os registros? 
 
4) Esquematize graficamente a tabela hash de tamanho 13, após a inserção seqüencial das chaves 
[28, 31, 45, 51, 58, 63, 65, 73, 79, 85] e considerando o tratamento de colisões por: 
a) Encadeamento. 
b) Endereçamento aberto com teste linear. 
c) Endereçamento aberto com teste quadrático. 
 
 
	1. Introdução