( TODA A MATÉRIA SOBRE A RESOLUÇÃO DE COLISÕES )
Encadeamento Separado (Separate Chainning)
OUTRAS MANEIRAS DE RESOLVER COLISÕES
Existem colisões quando para duas entradas diferentes i, j
h(i) = h(j)
Quando acontecem colisões é necessário resolver o problema
exemplo:
Num universo de 23 pessoas qual a probabilidade de várias fazerem anos no mesmo dia?
365 x 364 x ...
36523
Para 23 elementos, numa tabela de 365 lugares existe 0.5% de probabilidade de existir uma colisão
1- ENCADEAMENTO SEPARADO (SEPARATE CHAINNING)
☺ Cada lugar da tabela vai ter um apontador para uma lista;
☺ Cada lista vai conter os elementos com o mesmo índice
EXEMPLO :
► Temos dois problemas com encadeamento separado:
1- Se todos tiverem o mesmo índice vamos ter apenas uma lista;
2- Não podemos dizer no inicio do problema qual o tamanho das listas
► Tem a vantagem da eliminação de elementos ser muito fácil
► Tem a desvantagem da eliminação ser complicada;
● Cada caixa da tabela tem um apontador que vai apontar para a primeira caixa que
contenha outro elemento com o mesmo indice;
● Há também um apontador para a primeira caixa que está disponível
EXEMPLO :
h(i) = i mod 6
à h(32) = 2 à vai para a casa 2 que vai ter um apontador
para a primeira casa disponivel.
► Existe uma maneira mais performante de implementar a tabela apresentada:
● Em vez do apontador para a próxima casa com o mesmo indíce, existe um campo
com o indíce da outra casa.
procurar 82 : h(82) = 5 → O valor de 5 não é 82, vai-se então ao indíce 4;
→ O valor de 4 não é 82, vai-se então ao indíce 6;
→ O valor de 6 é 82, logo 82 está na tabela.
procurar 58 : h(58) = 3 → O valor de 3 não é 58, vai-se então ao indíce 1;
→ O valor de 1 não é 58, mas não nos é indicada outra caixa,
logo 58 não está na tabela.
eliminar val3 ( h(val3) = 5 )
Apaga-se o elemento da caixa 5 (porque é o val3), vai-se à caixa 4 e leva-se o seu elemento
para a caixa 5.
Mas como a caixa 4 também indica uma caixa 6, põe-se -1 na caixa 4 e indica-se na caixa 5
a caixa 6.
FICA :
Ao eliminar marca-se -1 no campo dos elementos para tornar a caixa disponível.
DESVANTAGEM : para um número pequeno de elementos na tabela vão ser necessárias tantas
comparações como se ela tivesse cheia.
OUTRAS MANEIRAS DE RESOLVER COLISÕES
A passo constante
passo = 1
inserir : 49; 11; 48; 18; 29; 22
h(i) = i mod 11
49 h(49) = 5
11 h(11) = 0
48 h(48) = 4
18 h(18) = 7
29 h(29) = 7 → como a caixa 7 já está ocupada
vai ver a primeira caixa disponível
a partir do 7.
22 h(22) = 0 → como a caixa 0 está ocupada vai inserir na 1.
60 h(60) = 5 → Na caixa 5 não se encontra o 60, logo vou procurar na
próxima caixa.
Como a caixa 6 está vazia, 60 não se encontra na tabela.
22 h(22) = 0 → Na caixa 0 não está o 22, logo vai procurar na próxima caixa.
Como o 22 está lá, ele está na tabela.
☺ A procura vai ser feita através de uma comparação directa, mas a partir de um indíce.
☺ A busca é falsa quando encontra uma caixa vazia antes de encontrar o elemento.
► PROBLEMA ! Secundary Clustering
● Quando existem dois grandes blocos separados por alguns lugares vazios, quando esses lugares
são preechidos, os dois blocos vão juntar-se dando origem a um bloco ainda maior.
● A inserção e a procura vão ser mais lentas quanto maiores forem os blocos.
► O passo pode ser diferente de 1
EXEMPLO :
passo = 3, vai inserir-se no 3º lugar vazio
inserir 11 h(11) = 0
inserir 22 h(22) = 0
► PROBLEMA !
Por EXEMPLO : passo = 4 e m = 12
depois de se inserir 3 colisões, a tabela vai estar cheia (porque 12 é múltiplo de 3)
► SOLUÇÃO !!
Escolher o P (passo) e o m (tamanho da tabela) de forma que :
→ m é primo
ou
→ m = 2P ou P é impar
Si (i) = h(i)
Sk (i) = [ h(i) + β k + α k2 ] mod m
α e β → constantes
Si → primeira tentativa de inserção ou procura de i
► PROBLEMA !
Também vai existir o problema de Secundary Clustering
Nelson Ciriz Nº 10858 Informática de Ensino email: cirisilves@excite.com
Venâncio Raposo Nº 15081 Informática de Ensino