Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 EDOO - Coggle Diagram
MM11 EDOO
Hashing
Motivação
Problema
Buscar em listas grandes é caro.
Solução
Converter chave em posição de armazenamento.
Função Hash
Propriedades desejáveis
Determinística.
Rápida.
Distribuição uniforme.
Transformar chave em índice da tabela.
Tabela Hash
Estrutura
Vetor de posições.
Cada chave é mapeada para um índice.
Chave->função hash -> indice -> acesso ao dado
Operações
Inserção
Calcula hash.
Armazena no índice correspondente.
Busca
Recalcula hash.
Vai diretamente ao índice.
Remoção
Localiza pela chave.
Remove registro correspondente.
Colisões
Definição
Chaves diferentes geram o mesmo índice.
São inevitáveis.
Chaining (Encadeamento)
Cada posição guarda uma lista.
Colisões ficam agrupadas no mesmo bucket.
Implementação simples.
Open Addressing
Linear Probing
Procura próxima posição livre.
Problema: clustering
Quadratic Probing
Saltos quadráticos.
Double Hashing
Segunda função define os saltos.
Melhor dispersão.
Menor concentração de elementos.
Todos os elementos permanecem dentro da tabela.
Fator de Carga
lambda = numero de elementos/tamanho da tabela
baixo lambda: poucas colisões
alto lambda: muitas colisoes
Rehashing
Quando ocorre
Fator de carga torna-se elevado.
Processo
Criar tabela maior.
Recalcular posições.
Reinserir elementos.
Space and Time Trade off
Ideia central
Ganhar desempenho normalmente exige memória extra.
Economizar memória normalmente aumenta o custo computacional.
Menos memória
Busca sequencial.
Reprocessamento de informações.
Estruturas compactas.
Resultado:
Menor espaço.
Maior tempo.
Mais memória
Índices.
Cache.
Lookup tables.
Hash tables.
Resultado:
Maior espaço.
Menor tempo.
Pré-processamento
Exemplos
Ordenação prévia.
Construção de índices.
Estruturas auxiliares.
Fazer trabalho antecipadamente.
Caching
Guardar resultados já calculados.
Evita computações repetidas.
Consome memória adicional.
Escolha da estrutura
Consultas frequentes
Priorizar velocidade.
Recursos limitados
Priorizar economia de memória.
Projeto eficiente
Encontrar equilíbrio entre ambos.
Sets e Dicionaries
Natureza do problema
Armazenar elementos.
Localizar elementos rapidamente.
Inserir e remover dados com eficiência.
Escolher estrutura adequada para cada necessidade.
Set (Conjunto)
Características
Elementos únicos.
Sem duplicatas.
Interesse principal: existência do elemento.
Operações
Insert
Remove
Find
Size
Clear
Dictionary (Mapeamento Chave -> Valor)
Estrutura
Chave identifica registro.
Valor contém informação associada.
Operações
Insert(key, value)
Find(key)
Remove(key)
RemoveAny()
Size()
Implementação dos ADTs
Arrays
Estrutura simples.
Boa localidade de memória.
Inserções podem exigir deslocamentos.
Listas Ligadas
Inserção e remoção flexíveis.
Busca geralmente linear.
Árvores
Mantêm ordenação.
Buscas eficientes.
Tabelas Hash
Priorizam velocidade.
Não mantêm ordem natural dos elementos.