Tratamento colisão - endereçamento aberto

Prévia do material em texto

Tabela Hash
Tratamento de colisões por endereçamento aberto
emanoelim@utfpr.edu.br
Tratamento de colisões
• Uma função de hashing está sujeita a gerar a mesma posição 
para chaves diferentes, situação que chamamos de colisão. 
• Imagine que a função usada é a de divisão e que o tamanho da 
tabela é 50. Para um item com chave igual a 100, o resto será 0, 
então o item será colocado na posição 0. Mas, para um item 
com chave igual a 400, o resto também será zero, fazendo com 
que a posição 0 seja sobrescrita. 
Tratamento de colisões
• Analogamente, também irão acontecer problemas na busca. 
Considere buscar o item 900. Ele não foi inserido na tabela, mas 
como o resto de 900 por 50 é 0, será mostrado o item 400, que 
está na posição 0. 
Tratamento de colisões
• Colisões podem acontecer com qualquer função de hashing 
escolhida, por isso elas precisam ser tratadas. Assim, podemos 
dizer que uma tabela de hash é formada de duas partes 
principais: 
• A função de hashing;
• Uma estratégia para tratamento de colisões.
Endereçamento aberto
• Uma dessas estratégias é conhecida como endereçamento 
aberto:
• Caso aconteça uma colisão, buscar na tabela outra posição 
ainda não ocupada. 
• Existem diversas formas de fazer isso, entre as mais 
conhecidas estão a sondagem linear, sondagem quadrática 
e o duplo hash.
Endereçamento aberto
• Sondagem linear: se a posição calculada está ocupada, tentar a 
próxima posição, e assim por diante, até achar uma posição 
livre:
int sondagem_linear(int posicao, int i) {
 return (posicao + i) % TABLESIZE;
}
• i define o número da tentativa;
• o número máximo de tentativas é TABLESIZE - 1.
Endereçamento aberto
• Sondagem linear: esta abordagem tem a desvantagem de gerar 
“agrupamentos” (longas sequências de posições ocupadas) 
conforme a tabela começa a ficar cheia. 
• No pior caso, se todas as chaves forem mapeadas para o 
mesmo índice, a complexidade será O(n) - para inserção, busca 
e remoção*.
• O melhor caso será O(1) - nenhuma colisão acontece.
Endereçamento aberto
• Sondagem quadrática: tenta espalhar os elementos usando 
uma equação do segundo grau:
int sondagem_quadratica(int posicao, int i) {
 float c1 = 0.5;
 float c2 = 0.5;
 int nova = (int)(posicao + c1*i + c2*i*i);
 return nova % TABLESIZE;
}
• c1 e c2 são constantes;
• i define o número da tentativa;
Endereçamento aberto
• Sondagem quadrática: requer cuidados ao selecionar os 
valores de c1, c2 e TABLESIZE. 
• Dependendo da escolha, pode ser que a fórmula calcule posições 
repetidas, enquanto algumas posições nunca são calculadas. Assim, 
um item pode acabar não sendo inserido mesmo se houverem 
posições vagas. 
• Uma boa escolha é usar TABLESIZE como uma potência de 2, 
juntamente com c1 = c2 = 0,5. Isso fará com que valores distintos 
sempre sejam gerados. 
Endereçamento aberto
Fone: 
http://wiki.icmc.usp.br/images/4/
44/SCC0601-2oSem2011-Luca
s-Slides12.pdf
A sondagem quadrática 
aumenta o intervalo 
entre uma tentativa e 
outra, diminuindo os 
agrupamentos que 
acontecem com a 
sondagem linear.
Endereçamento aberto
• Sondagem quadrática: apesar de reduzir o agrupamento que 
acontece com a sondagem linear, ainda podem acontecer 
agrupamentos. 
• No pior caso, a complexidade também pode chegar a O(n).
• No melhor caso, a complexidade é O(1) - nenhuma colisão 
acontece.
Endereçamento aberto
• Duplo hash: caso a posição calculada gere colisão, chama-se 
uma segunda função de hash:
int duplo_hash(int chave, int pos_h1, int i) {
 int pos_h2 = h2(chave);
 return (pos_h1 + i*pos_h2) % TABLESIZE;
}
• i define o número da tentativa;
• pos_h1 é a chave gerada pela primeira função de hashing (h1);
• h2 é a segunda função de hashing - ela deve ser diferente da primeira e nunca 
deve dar 0, ou então a mesma posição será gerada novamente.
Endereçamento aberto
• Duplo hash: na prática, em vez de ter duas funções diferentes, 
geralmente é mais rápido definir h2 em termos de h1:
h2(k) = 1, se h1(k) = 0
h2(k) = TABLESIZE - h1(k), se h1(k) > 0
onde o TABLESIZE deve ser preferencialmente um número 
primo.
Endereçamento aberto
• Duplo hash: o duplo hash é a melhor estratégia de 
endereçamento aberto, pois introduz uma maior aleatoriedade 
na hora de redefinir as posições, evitando os agrupamentos. 
• No pior caso (com muito azar), a complexidade ainda será O(n).
• No melhor caso, será O(1) - sem colisões.
Remoção de item
• A operação de remoção requer cuidados. Imagine que 
TABLESIZE é 10, e serão inseridos itens com chaves 10, 20, 30 e 
40. A função de hashing usada é a de divisão e para o 
tratamento de colisões a abordagem é a sondagem linear:
Remoção de item
• A ocupação da tabela após as inserções é dada abaixo:
posição chave
0 10
1 20
2 30
3 40
... ...
9 NULL
Remoção de item
• Se for removido o item 30:
posição chave
0 10
1 20
2 NULL
3 40
... ...
9 NULL
Ao tentar buscar o item de chave 40, a busca irá encontrar o NULL 
na posição 2 e irá encerrar, sem encontrar o item.
Remoção de item
• Uma alternativa é: em vez de remover o item, marcá-lo com uma flag 
que indica que ele é um item “deletado”: 
• Na inserção de um novo item, se a posição tiver um item marcado 
como deletado, a posição pode ser sobrescrita com um novo item;
• Na busca, ao encontrar um item marcado como deletado, a busca não 
termina. Ela segue até achar o item procurado, ou até terminar de 
varrer todas as posições possíveis.
Referências
• Ziviani, N. “Projeto de algoritmos com implementações em C e Pascal”, 
Cengage Learning, 3ª ed., 2010.
• Notas de aula Prof. Luis Gustavo Nonato:
http://www.lcad.icmc.usp.br/~nonato/ED/Hashing/node33.html
• Vídeo aulas sobre tabela hash:
https://www.youtube.com/watch?v=njkANXEMHTY
Vitter, J. S., Flajolet, P. “cap. Average cases analysis of algorithms and data 
structures” em “Handbook of theoretical computer science vol. A - 
algorithms and complexity”, Elsevier, 1990.