Tratamento de colisões

●
Endereços-base: podem ser mapeados para duas ou
Tabelas de Dispersão mais chaves distintas o que implica em colisão;
Tratamento de Colisões por Encadeamento ●
Fator de carga: α=𝑛/𝑚 , onde n é o número de
chaves armazenadas e m o tamanho da tabela;
Prof. Rafael Lima
●
Fator de carga aumenta → aumenta a possibilidade
de colisões;
●
Métodos de tratamento de colisões são necessários!
2

Nesta aula: 1.a Encadeamento Exterior

[Link] de Colisões por Encadeamento ●
Consiste em manter m
(a) Encadeamento Exterior listas encadeadas, uma
(b) Encadeamento Interior
para cada endereço-base;
●
Inserção no fim:
percorre a lista para
garantir que a chave não
é duplicada.

3 (Szwarcfiter e Markenzon, 2010) 4

1.b Encadeamento Interior 1.b Encadeamento Interior: Separação fixa

●
Em algumas aplicações não é desejável a ●
Divide a tabela em duas partes fixas: p+s = m
manutenção de uma estrutura exterior à tabela de ●
O espaço p para os endereços-base, e s para os
dispersão sinônimos
●
É possível resolver o problema de colisões mediante ●
h(x) deve mapear endereços na faixa de [0, p-1]
o emprego de listas encadeadas que compartilham o
mesmo espaço de memória que a tabela; ●
Cada nó possui o espaço para a chave e o ponteiro
para o próximo compartimento;
●
Esse método é denominado encadeamento interior.
5 6
1.b Encadeamento Interior: Separação fixa 1.b Encadeamento Interior
●
n=5 chaves, m=7, sendo ●
Outra forma é não diferenciar as duas zonas da
p=4 e s=3 tabela.
●
h(x) = x mod 4 – Qualquer endereço pode ser de base ou colisão.
●
Efeito indesejado: colisões secundárias.
Zona reservada à colisões se encontra completa. – Coincidência de endereços para chaves que não são
S Novas inclusões com endereços-base iguais a 0 ou 3,
implicam em overflow. Apesar de ainda ter espaço na
tabela.
sinônimas;

(Szwarcfiter e Markenzon, 2010) 7 8

1.b Encadeamento Interior – Colisões

1.b Encadeamento interior – Colisões secundárias
secundárias - Exemplo
●
Em caso de colisão, a nova chave x é inserida no ●
h(x) = x mod 7
primeiro espaço vazio d.
– A partir do compartimento onde ocorreu a colisão; ou
– A partir do final da tabela;
●
h(19) = 5, porém a posição 5 já está com 14,
●
Suponha y, tal que h(y) = d, haverá colisão entre x e onde h(14)=0.
y. ●
A lista dos endereços com base 5 se mistura
à lista com base 0.
Isto provoca a fusão das listas que contém chaves possuindo
(Szwarcfiter e Markenzon, 2010)
endereço base h(y) e h(x)→diminui a eficiência!
9 10

1.b Encadeamento interior – remoção 1.b Encadeamento interior - Algoritmos

●
Em princípio, não se pode apenas remover ●
Possíveis estados de cada compartimento:
uma chave! – Vazio
– Suponha x esteja no compartimento d, na lista ●
Jamais foi utilizado para armazenar qualquer chave;
encadeada L; – Ocupado
y Contém uma chave armazenada;
– [Link] = y ●

– Suponha que removamos x;

d x – Liberado
●
Quando está ocupado por alguma chave x cuja remoção é solicitada.
– Caso h(y) = d, uma busca por y retornaria que ●
Nesse caso, o nó que contém x não deve ser removido da lista.
não está na tabela ●
Posteriormente, x pode ser substituída nesse nó por alguma outra chave.
●
Nessa ocasião, o compartimento torna-se, novamente, ocupado.
11 12
 1.b Encadeamento interior: Algoritmos -
suposições
1.b Endereçamento Interior - Busca
●
𝑇[𝑖].𝑐ℎ𝑎𝑣𝑒 armazena a chave;
●
𝑇[𝑖].𝑒𝑠𝑡𝑎𝑑𝑜 ∈ {“ocupado”, “𝑛ã𝑜 𝑜𝑐𝑢𝑝𝑎𝑑𝑜”}
●
Inicialização:
– 𝑇[𝑖].𝑝𝑜𝑛𝑡=𝑖, ∀𝑖 0 ≤ 𝑖 < 𝑚
– 𝑇[𝑖].𝑒𝑠𝑡𝑎𝑑𝑜= “𝑛ã𝑜 𝑜𝑐𝑢𝑝𝑎𝑑𝑜”, ∀𝑖 0 ≤ 𝑖 < 𝑚
●
Cada compartimento i é parte de uma lista encadeada com as
Resultado a=1:
possíveis colisões da chave armazenada em i.
– chave x foi encontrada no compartimento end.
●
T é tida como uma lista circular.
13 (Szwarcfiter e Markenzon, 2010) 14

1.b - Endereçamento Interior - Busca 1 Começo realizando a busca.

2 Se não encontrarmos a
chave...

End. Interior - Inserção

Resultado a=2:
3
Se o valor de end for válido, então já é o
1) end≠λ: então end=j, onde j é um compartimento não ocupado compatível com local apropriado para inserir a chave.
h(x);
2) end=λ: caso contrário
(Szwarcfiter e Markenzon, 2010) 15 (Szwarcfiter e Markenzon, 2010) 16

4 Senão, temos que tentar

encontrar onde inserir...

5 Se o espaço j está ocupado, então siga

em frente buscando o próximo local
End. Interior - Inserção

End. Interior - Inserção

7 Achei um compartimento
não ocupado!

6 8
Se saiu do laço anterior com i=m+1 → varreu
toda a lista e não há espaço para a chave. Mantém o vínculo das listas.
(Szwarcfiter e Markenzon, 2010) 17 (Szwarcfiter e Markenzon, 2010) 18
 1.b Encadeamento Interior - Remoção
Obrigado por sua atenção!

Referências:
Szwarcfiter e Markenzon. Estruturas de Dados e Seus Algoritmos. LTC, 2010.

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to
algorithms. MIT press, 2009.

(Szwarcfiter e Markenzon, 2010) 19 20