Please enable JavaScript.

Coggle requires JavaScript to display documents.

Set, Tempo por Espaço, Hashing - Coggle Diagram

- - - - Dessas operações, as mais usadas são a de checagem, inserção e remoção
        
        Uma estrutura de dados que implement essas três operações é chamada dicionário
        
        Como as três operações são importantes, é preciso que essas implementações encontram um equilíbrio em suas eficiências
    - - Considerando um conjunto universo U do qual todos os sets são subconjuntos
        
        Pode-se representar um subconjunto de U como uma cadeia de bits em que cada bit de um elemento pertecente à instersecção do set com U é 1 e todos os outros são 0
        
        Essa representação permite que as operações dos sets sejam mais rápidas, porém é mais custosa em espaço
      - O mais comum é que sets sejam representados pela estrutura de dados lista
        
        Apesar dessa representação, sets e listas são dois conceitos diferentes
        
        Sets não permitem repetição de elementos, listas sim
        
        Há variantes de sets que contornam essa característica, como multiset e bag
        
        Listas são ordenadas, sets não
- - - - Preprocessamento salva resultados de operações após sua execução para que possam ser acessados depois, prestucturing realiza operações e salva seus resultado antes de serem usadas
    - - Trata-se de salvar em uma tabela resultados de subproblemas de um problema maior para que outros subproblemas os possam acessar sem repetir operações
- - - - Existem hash functinos que operam sob inteiros, caracteres, strings, etc
  - - - A distribuição de chaves pela hash table deve ser o quão uniforme possível
        
        A hash function deve ser fácil de se computar
        
        Por isso, é desejável que s hash function dependa de todos os bits de uma chave
      - Mas deve ser o bastante para não comprometer a eficiência de tempo
        
        Também não dever ser menor que o número de chaves, o que tornaria impossível evitar colisões
  - - - Apesar de não se poder evitar totalmente que ocorram, elas podem ser minimizadas usando uma hash table de tamanho adequado e hash function de tamanho o bastante
        
        Ainda assim, todo esquema com hashing dever ter um mecanismo para lidar com colisões
    - - Open Hashing é uma das principais formas de lidar com colisões
        
        Nessa, no lugar de armazenar as chaves na hash table diretamente, armazena-se uma lista ligada
        
        Assim, em casos de colisões, a nova chave é adicionada à lista ligada, permitindo que diversas chaves compartilhem um mesmo valor
        
        Para encontrar uma chave, usa-se a hash function para detecter a presença e/ou determinar em que lista a chave pode estar. Então é possível iterar pela lista até que ela acabe ou a chave seja encontrada
        
        A eficiência dessa busca depende do tamanho da lista, que em si, depende de outros fatores, como o tamanho da hash table e a eficiência da hash function
        
        As operações de inserção e remoção são feitas realizando buscas. Uma vez que a chave seja encontrada, basta inserir ou remover o elemento da lista da chave
      - Fator de Carga
        
        O fator de carga (load factor) expressa quatas chaves são distribuídas por hash address
        
        Ele é um indicativo da eficiência do hashing e ajudar a calcular quantas comparações são feitas em buscas bem ou mal sucedidas por uma chave
        
        Um fator de carga muito baixo indica um número muito superior de células da hash table, ou seja muitos espaços vazios. O que indica ineficiência de espaço
        
        Um valor muito alto, por outro lado, indica muitas colisões. O que gera iineficiência na busca por um valor
        
        O idel é que o fator de carga seja próximo de 1. Assim temos uma grande eficiência de espaço e poucas colisões, o que leva a tempo reduzido de buscas
        
        Closed Hashing
        
        No closed hashing, os valores das chaves são armazenados diretamente na hash table
        
        Isso exige um tamanho minímo para a hash table igual ao número de chaves
        
        Aqui, há diversas formas de lidar com colisões. Entre elas, a mais simples é chamada linear probing
        
        A ideia de linear probing é a seguinte:
        
        Caso ocorra uma collisão ao armazenar uma nova chave, a chave é inserida no hash address seguinte
        
        1 more item...
        
        Uma análise sobre linear probing revela que o número de comparações realizadas em buscas tanto bem quanto mal sucediddas é extremamente pequeno
        
        Entretanto, essa eficiência decai rapidamente quando a hash table se aproxima de estar cheia
        
        1 more item...
        
        Comparações com Árvores de Busca Balanceada
        
        Operações
        
        Com hashing, é possível implementar operações de busca, adição e remoção com classes de eficiência constante para casos médios e linear nos improváveis piores casos
        
        Nas ávores, a classe de eficiência para todas as operações é da classe logaritmica
        
        Ordenação
        
        Diferente das ávores, hashing não se preocupa e nem preserva odernação de itens
        
        1 more item...
        
        Como diferentes implementações de um dicionário, uma oferece vantagens sob a outra. Então faz sentido realizar comparações e verificar qual é mais vantajosa sob certo aspecto
- - - - As funções que expressam essas relações são chamadas hash functions
      - O index da array onde habita uma chave é chamado hash address
      - Hashing oferece uma implementação mais eficiente de dicionários
        
        Além disso, também foram descobertas diversas outras aplicações para hashing
        
        Hoje, é a forma padrão de registrar dados gerados durante a compilação de um programa
        
        Também é usada em alguns algoritmos de Inteligência Artificial
        
        E é usado para registar dicionários em disco