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