Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sets - Coggle Diagram

- - - - Hashing
        
        ADT
        
        Definição
        
        Tem uma hash table, que contem diversas chaves. Cada uma dessas chaves indica um elemento desse set.
        
        Hash-function: É uma função criada para gerar as chaves para serem colocadas no array.
        
        Hash table não deve ser muito maior que a quantidade de chaves
        
        Deve conseguir distribuir chaves diferentes sempre que possivel
        
        Deve ser facil do computador calcular
        
        Operações
        
        Search
        
        Checar a existência de um elemento no set
        
        Add
        
        Adiciona um novo elemento no set
        
        Remove
        
        Remove um determinado elemento do set
        
        Implementação
        
        Open hashing
        
        Consiste em criar um array para a hash table, dentro de cada um dos indices do array existe uma linked list apontando para cada um dos elementos. Caso haja repetição, essa lista cresce. Se não houver elemento, a lista é vazia
        
        Add: basicamente usar a hash function e colocar o elemento da lista do indice
        Remove: Analisar em que indice esse elemento estaria, analisar a lista dentro e remover de dentro dela
        Search: Analisar em que indice esse elemento estaria, analisar a lista dentro e responder se o elemento existe
        
        Closed hashing
        
        Linear Probing
        
        Consiste em criar um array para a hash table, dentro de cada um dos indices do array existe um unico elemento. Caso um elemento queira ser adicionado em um indice que existe outro elemento, ele deve ser inserido no proximo espaço vazio
        
        Add: Usar a hash function e descobrir o lista do indice que o elemento deveria estar, caso não haja elemento, adicionar, se houver, verifica o proximo e faz o mesmo processo.
        Remove: Analisar em que indice esse elemento estaria, caso estiver vazio, não tem esse elemento, caso estiver preenchido, verificar se esse é o elemento que se deseja remover. Se não for, passar pro proximo elemento e fazer o mesmo processo.
        Search: Analisar em que indice esse elemento estaria, caso estiver vazio, não tem esse elemento, caso estiver preenchido, verificar se esse é o elemento que se deseja encontrar. Se não for, passar pro proximo elemento e fazer o mesmo processo.
        
        Double Hashing
        
        Consiste em criar um array para a hash table, dentro de cada um dos indices do array existe um unico elemento. Caso um elemento queira ser adicionado em um indice que existe outro elemento, ele será submetido a outra hash function, que indicará outro local
        
        Add: Usar a hash function e descobrir o lista do indice que o elemento deveria estar, caso não haja elemento, adicionar, se houver, usa a segunda hash function para repetir o processo.
        Remove: Analisar em que indice esse elemento estaria, caso estiver vazio, não tem esse elemento, caso estiver preenchido, verificar se esse é o elemento que se deseja remover. Se não for, usar a segunda hash function e com o novo indice, repetir o processo
        Search: Analisar em que indice esse elemento estaria, caso estiver vazio, não tem esse elemento, caso estiver preenchido, usar a segunda hash function e repetir o processo com o novo indice
      - B-tree
- - - - Checar a existência de um elemento no set
    - - Adiciona um novo elemento no set
    - - Remove um determinado elemento do set