Baixe o app para aproveitar ainda mais
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.
Compartilhar