Tabela de Dispersão Encadeada

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.