Algoritmos e Estruturas de Dados [LEEC] (2024/2025)
Aulas teóricas
Artur Miguel Dias
Teórica 11 (30/mai/2025)
Dicionário implementado usando a técnica da tabela de dispersão.
Slides
DicionarioTabDispersao.c
Implementação do TAD Dicionário usando a técnica da tabela de dispersão.
Eis os pontos mais importantes:
- Uma função especial, chamada função de
dispersão que, aplicada a uma chave, calcula diretamente um inteiro com uma posição válida no vetor.
- A função de dispersão deve ser eficiente O(1), e deve distribuir de forma
uniforme as chaves pelos vários índices do vetor.
- Quando a função de dispersão produz o mesmo índice para
duas chaves diferentes dizemos que temos uma colisão.
- Na biblioteca resolvemos as colisões usando a técnica de dispersão encadeada - cada posição no vetor tem uma lista ligada que guarda os elementos cujas chaves entraram em colisão para essa posição.
- Quando a estrutura de dado enche muito e as listas ligadas começam a ficar longas, é preciso duplicar o tamanho de vetor e reinstalar todos os elementos (rehash).
#20
