Please enable JavaScript.

Coggle requires JavaScript to display documents.

Set, Hashing, Compensações espaço-tempo - Coggle Diagram

- - - - Meio Termo
        
        Eficiência de Pesquisa
        
        Eficiência União Interseção
    - - Arrays
        
        Pouco sofisticada
      - Hash e árvores de pesquisa equilibrada
        
        Mais sofisticada
- - - - Conjuntos
        
        Coleção desordenada de itens
        
        Não pode conter elementos iguais/repetidos
      - Listas
        
        Pode conter elementos iguais
        
        Coleção ordenada de itens
      - Cotornando diferenças
        
        Contorna-se através da introdução de um multiset ou bag
        
        Coleção não ordenada de itens não necessariamente distintos
- - - - Maior a probabilidade de aglutinação de clusters após a inserção de nova chave
        
        Mais agrupamento
  - - - Solução
        
        Usar lazy delection para marcar lugares anteriormente ocupados por um símbolo especial, distinguindo de locais nunca ocupados
      - Problema
        
        Exclusão que deixa uma célula vazia e não tem como saber se já houve algum elemento nessa célula
  - - - Se h(k) é vazia
        
        Pesquisa mal sucedida
      - Se h(k) tiver elementos
        
        Compara K com os ocupantes da célula
        
        Se forem diferentes
        
        Comparamos K com uma chave nas próximas células até achar o que estamos procurando ou achar uma célula vazia (pesquisa mal sucedida)
        
        Se forem iguais
        
        Encontramos a chave
  - - - Análise matemática
        
        Superior ao linear probing
        
        Mas o desempenho se deteriora quando a tabela está perto de ficar cheia
        
        Solução
        
        Rehashing
        
        A tabela atual é verificada e todas as suas chaves são colocadas em uma tabela maior
      - Outra função hash para determinar um incremento fixo na sequência a ser usada após uma colisão num local l = h(k)
      - Funções recomendadas
        
        Tabelas Pequenas
        
        k = 8 - k mod8
        
        k = m - 2 - k mod (m-2)
        
        Tabelas Maiores
        
        k = k mod97 + 1
      - Garantir que cada localização na tabela seja sondada
        
        Incremento e tamanho da tabela devem ser primos entre si
    - - Verifica a célula seguinte àquela que ocorreu a colisão
        
        Tratado como um array circular
        
        Do fim, volta-se para o início
        
        Se estiver ocupada, a disponibilidade do sucessor é verificada, e assim por diante...
        
        Se tiver vazia, a nova chave é instalada lá
- - - - Hashing Fechado
        
        Endereçamento Aberto
      - Hashing Aberto
        
        Encadeamento separado
- - - - Verifica se a chave realmente é a que está na célula correspondente
    - - Comprimento dos links
        
        Que por sua vez dependem do tamanho do dicionário e da tabela
      - Qualidade da hash function
    - - n/m=Fator de carga da tabela hash
        
        Papel Crucial na eficiência do hash
      - Fator de carga
        
        Desejável
        
        Próximo de 1
        
        Eficiência Alta
        
        Busca com custo de 1 ou 2 comparações
        
        Precisa de tempo constante para calcular a função hash
        
        Custo de espaço extra
        
        Muito pequeno
        
        Lista Quase Vazia
        
        Uso ineficiente do espaço
        
        Muito grande
        
        Listas longas e tempo de pesquisa muito longo
    - - O ganho com a hash é a redução do tamanho médio da lista por um fator m (tamanho da hash table)
  - - - Procura-se uma chave e deleta da lista
        
        Θ(1) time no caso médio
        
        O número de chaves (n) é quase igual ao tamanho da tabela hash (m)
    - - Feitas no fim de uma lista geralmente, mas pode ser modificado
- - - - Função hash dependente de todos os bits de uma chave
- - - - Ordem da letra do alfabeto
- - - - Hashing
        
        Θ(1) time no caso médio
        
        Θ(n) time no pior caso
      - Árvores de pesquisa balanceadas
        
        Θ(logn)
        
        Para o caso médio e o pior caso
      - Preservação de ordenação
        
        Ao contrário das árvores, o hashing não preserva o ordenamento de chaves
        
        Menos eficiente em aplicações que precisam iterar as chaves em ordem ou querem consultas de intervalo, como limite inferior e superior
  - - - Verificar se posições geradas num jogo de xadrez por computador já foram consideradas
    - - Armazenar grandes dicionários em disco
      - Acesso ao disco
        
        É caro quando comparado às análises realizadas na memória principal
        
        Local calculado por uma função hash em hashing extensível
        
        Indica o endereço do disco de um depósito que pode conter até b chaves
        
        Quando um depósito é identificado, todas as chaves são lidas na memória principal e procura a chave em questão
- - - - Manter informação sobre uma entidade que o registro representa
    - - Identificar entidades representadas pelos registros
- - - - Métodos de contagem para classificação
      - Boyer Moore- Algoritmo para correspondência de string
- - - - Ao contrário do aprimoramento de entrada
- - - - Leva a um algoritmo mais rápido