Olavo Rangel da Conceição
Set
Space and Time Trade-Offs
Hashing
Open Hashing
Closed Hashing
Coleção Não ordenada
Elementos do conjunto
Pode ser vazio
Definidos
Lista Explicita
Propriedade Especifica
Engloba Todos os Elementos do Conjunto
Operação dos Conjuntos
Checking Membership
União de Dois Conjuntos
Intersecção de Dois Conjuntos
Aplicação Informatica
Conjuntos que são Subconjuntos do Conjunto U
Estrutura de Lista
Indicar Elementos do Conjunto
Aplicavel Em Conjuntos Finitos
Se o Conjunto U tem n elementos
Qualquer outro subconjunto de U será menor ou igual a n
Bit Vector
Operações
Busca Determinado Item
Adição de Item
Exclusão de Item
Dicionário
Problema
Set Union Problem
Diferenças Entre Conjunto e Lista
Lista não pode Ter Elementos Identicos
Multiset
Conjunto é uma Coleção Não ordenada de Elementos
Lista é Uma Coleção Ordenada
Algumas Vezes Vale a Pena Deixar o Conjunto Ordenado
Bastante Conhecido
Teoricos
Profissionais da Computação
Antes dos Computadores Eletrônicos
Pré-Computar Valores da Função
Armazenar Em Tabela
Util
Usado até Hoje
Desenvolvimento de Algoritmos
Input Enhancement
Counting Methods
Sorting
Prestructuring
Hashing
Indexing with B-Trees
Tempo e Espaço
Dynamic Programming
Registro de Solução
Overlapping de Subproblemas
Problema
Não precisam Competir entre Si
Solução Algoritmicas
Contempla os Dois Problemas
Compressão de Dados
Redução de Tamanho é a Meta
Não é Tecnica para Resolver outros Problemas
Maneira Eficiente
Implementação Dicionarios
Registros
Vários Campos
Distribuição de Chaves
Matriz Unidimensional
Hash Table
Manter Tipo de Informação do Registro
Key
Computando
Chaves
Valor
Função Predefinida H
Hash Function
Atribui Numero entre 0 e m-1
Endereço Hash
Hash Table Size Não Deve Ser Grande
Numero de Chaves
Mas Deve Ser Grande o Suficiente para Não Comprometer a Eficiência
Distribuir Key
Mais Uniforme Possivel
Precisa ser Fácil de Computar
Chaves
Armazenada
Linked Lists
Anexadas as Células da Tabela Hash
Fazer uma Busca
Eficiência Depende do Tamanho da Linked List
Que Depende do Tamanho do Dicionario e da Tabela
Colocar Chave de Busca
Mesmo Procedimento
Criar Tabela
Ratio
Alfa = n/m
Load Factor
Importante
Boa Eficiência
Chaves Armazenadas
Hash Table
Linear Probing
Onde Ocorre Colisão
Verifica Próx Cell
Empty Cell
Full Cell
Nova Chave Instalada
Verificar o Próx
Fim
Busca Volta para o Inicio
Matriz Circular
Operação
Busca
Inserção
Eliminação
Simples
Complexa
Solução
Lazy Deletion
Cluster
Hash Table Ficando Cheia
Performance Deteriora
Sequência de Células
Contiguamente Ocupadas
Operação Dicionario
Menos Eficiente
Grandes Clusters
Aumenta Probabilidade de Colisões
Aliviar problema
Aliviar Problema
Double Hashing
Analise Matematica Dificil
Boa Implementação Hash
Superior Linear probing
Desempenho Piora
Ao ficar cheio
Solução
Rehashing
Tabela Atual
Escaneada
Chaves Realocadas
Tabela Maior