Estruturas de Dados
aula 25: Tabelas de dispersão (pdf, video)
- guardando as coisas em qualquer lugar
plano da aula
1. Introdução
- o que é mais rápido do que a busca binária?
2. Funções de dispersão
- o truque é espalhar as coisas pelas lista — (sabendo onde elas estão)
3. Tabelas de dispersão
- resolvendo as colisões
3.1 Algoritmos para a tabela com encadeamento externo
- busca, inserção e remoção
3.2 Análise
- O(1) em 99,9% dos casos ...
lista de exercícios 25 (pdf)
exercício 1: Tabelas com 2 funções de dispersão
exercício 2: Tabela de dispersão com 2 níveis
↩︎ Voltar