tabela de dispersao

Algoritmos e Estruturas de Dados
Tabelas de dispersão fechada

Pesquisas em vector
• pesquisa linear
• pesquisa dicotómica
• mais rápida do que a pesquisa linear mas, para ser utilizada, o vector tem de estar ordenado

Exercício: Faça um programa para ler de um ficheiro nomes de pilotos (considerando que o número do carro é determinado pela ordem de leitura) e, de seguida, permita indicar de forma rápida o número do carro de determinado piloto. Se o nome do piloto não existir, deve apresentar uma mensagem referindo tal facto
2004/05

AED - DI / FCT / UNL

2

Tabelas de dispersão - motivação uma generalização de um vector que, em determinadas condições, permite aceder rapidamente à informação, ainda que esta não esteja ordenada

inserção
• numa inserção, a posição onde se insere o elemento é função do valor do elemento, independentemente da ordem de inserção

• outras operações:

• pesquisa
•
2004/05

remoção
AED - DI / FCT / UNL

3

Função de dispersão e colisão
• função de dispersão: converte a chave genérica do elemento num índice da tabela (a entrada) entrada chave
(elemento)

função de dispersão ...

tabela
• se a função de dispersão indicar a mesma entrada para duas chaves distintas, então surge um problema de colisão
2004/05

AED - DI / FCT / UNL

4

Função de dispersão
•

o desempenho da tabela de dispersão depende da capacidade da função de dispersão distribuir uniformemente as chaves

•

características desejáveis para a função de dispersão:
•

eficiente

•

distribuição uniforme dos elementos pela tabela

• princípios
• função simples
• a dimensão da tabela deve ser um número primo

2004/05

AED - DI / FCT / UNL

5

Resolução de colisões
• dispersão aberta
• cada posição da tabela contem um apontador para uma lista de chaves com a mesma entrada
•

dispersão fechada
• existem sempre posições livres
• cada posição da tabela contem uma só chave. Se o