Baixe o app para aproveitar ainda mais
Prévia do material em texto
dibio@unb.br Assuntos ● Transformações de Chave (Hashing), espalhamento ● Colisões – Uso de Listas Encadeadas ● Exemplo – Uso de Endereçamento Aberto ● Exemplo – Vantagens e Desvantagens ● Outras Aplicações de “Hashing” dibio@unb.br Transformações de chave (Hashing), espalhamento dibio@unb.br Transformações de chave (Hashing), espalhamento dibio@unb.br Transformações de chave (Hashing), espalhamento dibio@unb.br Função de transformação Hashing) dibio@unb.br Funções de transformação dibio@unb.br Funções de “Hashing” dibio@unb.br Como mapear? dibio@unb.br Funções de transformação (método mais utilizado) dibio@unb.br E as colisões? ● Quando mais de um registro estiver relacionado à mesma chave? dibio@unb.br Colisões dibio@unb.br Opções para lidar com Colisões em “Hashing” dibio@unb.br Opções para lidar com Colisões em “Hashing” ● Uso de Listas Encadeadas ● Endereçamento Aberto dibio@unb.br Uso de Listas Encadeadas dibio@unb.br Uso de Listas Encadeadas dibio@unb.br Exemplo dibio@unb.br Exemplo dibio@unb.br Exemplo dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Exemplo em C (estrutura de dicionário com listas encadeadas) dibio@unb.br Comentários dibio@unb.br Endereçamento Aberto dibio@unb.br Endereçamento Aberto dibio@unb.br Exemplo dibio@unb.br Exemplo dibio@unb.br Exemplo dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Exemplo em C, dicionário com endereçamento aberto dibio@unb.br Comentários dibio@unb.br Vantagens e Desvantagens de “Transformações de Chave” dibio@unb.br Comentários sobre uso de “Transformações de Chave” dibio@unb.br Comentários sobre uso de “Transformações de Chave” dibio@unb.br Outras aplicações de “hashing” dibio@unb.br Referências ● Celes, W.; Cerqueira, R. & Rangel, J.L. Introducão a Estruturas de Dados, Editora Campus (Elsevier), RJ, 2004. ● Cormen, T.; Leiserson, C. & Rivest, R. Algoritmos: teoria e prática, Campus Editora, RJ, 2002. ● Tenenbaum, A.; Langsam, Y. & Augenstein, M. Estruturas de Dados usando C, Makron Books, RJ, 1995. ● Ziviani, N. Projetos de Algoritmos com Implementações em Pascal e C, Cengage Learning, SP, 2004. Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42
Compartilhar