Home

Aula 18 :      Resolução de colisões

Introdução: 

                Tal e qual como nos diz o titulo desta aula, a aula refere-se a resolução de colisões, que neste caso são colisões em tabelas de HASH dadas na aula passada ou seja quando inserimos um valor num determinado índice de uma tabela de HASH teremos de verificar sempre se esse índice já tem algum valor. Se sim teremos de resolver esses casos para não perdermos valores da tabela.

                Nesta aula falaremos de quatro tipos de resolução de colisões :

                - Encadeamento separado

                - Encadeamento entrelaçado 

                - Probing linear

                - Probing quadrado

Existem outros tipos de resolução de colisões o que podem ser consultados na bibliografia recomendada no final da pagina.

Encadeamento separado:

              Este tipo de resolução de colisões envolve a construção de adicionais estruturas de dados, o que permite que  que vários números ou outro tipo de dados predefinidos ( inteiros, decimais, caracteres ) com a mesma função de HASH possam ser armazenados na tabela de HASH sem perigo de colisões. 

                Um dos tipos de dados utilizados pode ser as listas, então cada índice da tabela de HASH tem que conter um ponteiro para esse tipo de dados. 

                Para armazenar um numero numa tabela de HASH, teremos primeiro que verificar qual a função de HASH para esse numero.

 A formula de calculo da funçao de HASH, h(x), é da seguinte forma :

                        h(x)= x mod m

em que x representa o numero que queremos armazenar na tabela e m o tamanho dessa mesma tabela. 

                Depois deste passo feito só nos falta inserir esse valor na tabela, o que se pode ser tornar complicado se não resolvermos os casos das colisões; então nesse caso na própria função inserir teríamos de fazer a verificação se o índice  correspondente ao valor da função de HASH  relativa ao numero já estava preenchida. Se sim teremos de inserir esse valor na lista que correspondente a essa casa, caso contrario basta inserir o valor nesse índice da tabela.

 Reparemos agora no caso da tabela de HASH apresentada na figura 1 :

                         ( figura 1 )

                Se nesta figura tivéssemos de inserir os valores 12 19 15 e 26, então calculando a função de HASH  para cada numero e sabendo pela dimensão da tabela da figura 1 que o parâmetro m = 7 teremos:

        h (12) = 12 mod 7 = 5

        h (19) = 19 mod 7 = 5   

        h (15) = 15 mod 7 = 1

        h(26) =  26 mod 7 = 5

 então a tabela de HASH final seria a representada na figura abaixo ( figura 2 ) :

                         ( figura 2 )

NOTA:

                No caso de por algum facto tivéssemos de ir verificar se um numero pertencia a tabela teríamos de procurar só no índice correspondente ao numero a procurar. 

Exemplo de Procura:

Procura de 8

Como a formula de saber a posição de um determinado numero dento de uma tabela de HASH é h(x)= x mod m então :

            h(8) = 8 mod 7 = 1

        Então vamos procurar no índice 1. Procurando o índice 1 na figura b  verificámos que só existe nessa casa da tabela o valor 15, logo podemos afirmar que  o valor 8 não pertence a tabela .

Encadeamento Entrelaçado :

                Este tipo de  resolução de colisões é muito parecido com a resolução do tipo encadeamento separado só que neste caso todos os valores são introduzidos na própria tabela de HASH  sem a utilização es estruturas de dados adicionais. 

Para este tipo de resolução de colisões a tabela de HASH terá de ter dois tipos de dados. Esses tipos de dados são:

- qualquer tipo predefinido ( inteiros, caracteres, decimais)             

- ponteiros

As casas destinadas aos ponteiros ou estão a  Null ou contêm o endereço de outras casas da tabela de HASH  

Quando queremos inserir um valor na tabela teremos de novo de utilizar a função de HASH .

             No caso de haver colisão o valor é colocado na  casa da tabela livre imediatamente a seguir  e o ponteiro da casa onde aconteceu a colisão terá então o endereço da casa livre da tabela onde foi inserido o numero.

Exemplo de inserção:

Insira 7 números numa tabela de HASH.

números a inserir: 15 ; 14 ; 34 ; 13 ; 5 ; 21 ; 27 ;

tabela inicial:

                Para inserir estes valores teremos de primeiro calcular o valor da função de HASH para saber em que índice da tabela o numero será colocado, então:

para 15 : h( 15 ) = 15 mod 7 = 1         para 14 : h( 14 ) = 14 mod 7 = 0       para 34 : h( 34 ) = 34 mod 7 = 6      

para 13 : h( 13 ) = 13 mod 7 = 6           para 5 : h( 5 ) = 5 mod 7 = 5             para 21 : h( 21 ) = 21 mod 7 = 0       

para 27 : h( 27 ) = 27 mod 7 = 6  logo :

Passos de inserção na tabela:

Probing :

Probing linear:

                Este método de resolução de colisões é  um método que tem como finalidade, no caso de haver colisões, a procura de uma nova casa da tabela de HASH através de uma equação linear, que depende de uma constante predefinida e de uma variável k, que se refere ao numero de colisões já ocorridas num determinado indicie da tabela. A equação linear tem como finalidade a procura de um novo índice da tabela. A designação da equaçao geral é s_k(x) e tem como forma geral:

s_k(x) = h(x) + c₁ k 

onde k, depende do número de colisões num determinado índice da tabela com a de HASH e c₁ será uma constante predefinida.    

Verifiquemos agora exemplos de inserção em que existe colisão, sendo a constante c₁ = 2 .Considerando que a tabela inicial é do tipo : 

Exemplo :

Introdução do valor 22 :

Em primeiro lugar teríamos de calcular   h(22) , que  é 0.

Como na tabela inicial temos no índice 0 o valor 0, logo existe uma colisão, então  teremos de calcular a função s₂( x ) 

s₂(x) = 0 +2  × 2  = 4  

Introdução do valor 11 :

Como vimos na introdução do valor 22 temos de calcular primeiro o h(x) correspondente que é h(11) = 0 então basta calcular s₃( x ) considerando que o valor 11 também já esta na tabela:

s₃(x) = 0 + 2 × 3 = 6  logo:

Então se quiséssemos introduzir  22 , 11  na tabela de HASH teríamos a seguinte tabela solução :

Probing quadrático:

                Este tipo de resolução de colisões é praticamente igual ao método anterior só que no caso de haver colisões a expressão de s_k(x) é do tipo quadrático ou seja vamos ter duas constantes c₁ e c₂ e a expressão de s_k(x) será do tipo :

s_k(x) = h(x) + c₁ k + c₂ k² 

onde k, como já vimos no probing linear, depende do número de colisões nesse índice da tabela e as constantes terão de ser predefinidas.

Verifiquemos agora exemplos de aplicação em que existe uma colisão:        

Exemplo :

Introdução do valor 11 :

Em primeiro lugar teríamos de calcular   h(11) , que  é 0.

 Como partimos do principio que na tabela de HASH já estava um valor na casa de índice 0 então  teremos de calcular a função para o probing ou se s₂( x ) 

s₂(x) = 0 + 0 + 2² = 4  

Introdução do valor 22 :

Como vimos na introdução do valor 11 temos de calcular primeiro o h(x) correspondente que é h(22) = 0 então basta calcular s₃( x ) considerando que o valor 11 também já esta na tabela:

s₃(x) = 0 + 0 + 3² = 9  logo:

NOTA :

 Ao salto entre s₂(x) e s₃(x) chama-se passo do probing ou seja

Então se quiséssemos introduzir  0 , 11 , 22  numa tabela de HASH teríamos a seguinte tabela solução :

Bibliografia utilizada para construção da pagina e recomendada para aprofundar conhecimentos dos métodos

NOME  : Data structures , algorithms , and object - oriented , programming 

AUTOR : Gregory L. Heilemain

EDITORA : McGRAW - HILL

NOME  : Fundamentals of data structures in C

AUTOR : Ellis Horowitz , Sartaj Sahn , Susan Andreson Freed

EDITORA : Computer Science Press

NOME  :Introduction to Algorthms

EDITORA : McGRAW - HILL