Descrição
Uma tabela de dispersão encadeada
consiste em um vetor de listas ligadas. Cada lista armazena dados na qual todos
os elementos foram posicionados especificamente na posição indicada da tabela
pelo espalhamento. Para inserir um elemento, primeiro se passa a chave (bloco
de dados do elemento) para a função de espalhamento processar e retornar a
codificação do valor para ser usado como índice na tabela e em qual lista deve
ser adicionado.
Para procurar ou remover um
elemento, calculamos novamente o espalhamento através da chave, para encontrar
a lista que armazena o elemento na tabela, para então percorrer a mesma lista
até encontrar o elemento desejado. Devido a cada posição da tabela referenciar
uma lista encadeada, não existe limite de elementos para este tipo de tabela de
dispersão, entretanto conforme a tabela aumenta demasiadamente começa a gerar
degradação no desempenho.
Tratamento de Colisão
Quando duas chaves geram o
espalhamento para a mesma posição, ocorre uma colisão. Tabelas de dispersão encadeadas
solucionam de forma simples tal problema, os elementos são posicionados na
lista encadeada relacionada ao índice na tabela que compartilham ente si,
diferente do caso de endereçamento aberto em que é preciso realizar um novo calculo
de espalhamento.
Com o armazenamento em lista, elimina
o limite de recipientes pelo tamanho da tabela, a lista encadeada irá armazenar
tantos elementos quanto à memória possa permitir. Um dos problemas relacionados
a isto é que o numero excessivo de colisões para uma determinada posição,
tornará a lista cada vez mais longa, levando-se cada vez mais tempo para
acessar seus elementos.
O ideal é que cada lista da
tabela cresça na mesma proporção que as demais, mantendo-se no mesmo tamanho e
o menor possível, ou seja, distribuir todos os elementos na tabela de forma
equilibrada e aleatoriamente, esta situação perfeita é conhecida como espalhamento
uniforme e na pratica dificilmente será alcançada devendo ser considerado como
um objetivo a ser almejado.
Coeficiente de carregamento
Mesmo se fosse possível conseguir
o espalhamento uniforme, o tempo de execução aumentaria caso fosse mantido uma
tabela pequena em relação à quantidade de elementos a ser inserido, a situação
se deve ao fato de que cada lista na tabela irá se tornar cada vez maior, por
isto se torna importante se preocupar com o coeficiente
de carregamento que podemos definir como:
α = n / m
Aonde n é o numero total de elementos distribuídos na tabela e m é a faixa do valor de espalhamento que
vem a ser o tamanho da tabela, o coeficiente de carregamento em uma tabela de
dispersão encadeada indica o numero máximo de elementos que podemos achar em
cada uma das listas encadeadas de armazenamento que fazem parte da tabela.
Para exemplificar, imagine que
temos uma tabela com 500 listas e um total de 4000 elementos, o coeficiente de
carregamento para tabela seria α= 2000/500
= 4, neste caso espera-se encontrar um total de quatro elementos a cada
posição da tabela. Lembrando que espalhamento uniforme é apenas desejado, mesmo
tendo o modelo ideal calculado pelo coeficiente de carregamento, na pratica
será encontrado apenas um valor aproximado do calculado, o quão perto irá
depender da seleção da função de espalhamento.
Desempenho
Optando por utilizar lista
encadeada ordenada, a busca terá melhor desempenho, uma vez que a lista não
precisa ser percorrida até o fim para identificar se um elemento está presente na
lista, o tempo médio de busca é metade do tamanho da lista, mais 1 ao selecionar
qual lista da tabela, interessante notar o fato de que busca que retornam
resultados vazios tende a ser mais rápidas que as pesquisas que tem sucesso.
Um ponto negativo da tabela de
dispersão encadeada é a o fato de requerer mais espaço quanto à programação, se
comparar o processo de adicionar os dados de forma direta com o de referencia dos
ponteiros para nó. Entretanto, baixo custo de memória e CPU rápidas reduz o
impacto dessa desvantagem tornando a tabela de dispersão encadeada a escolha
ideal.
Na próxima postagem teremos código exemplo para tabela dispersão encadeada utilizando as rotinas de lista
encadeada apresentadas anteriormente.
Nenhum comentário:
Postar um comentário