Please enable JavaScript.

Coggle requires JavaScript to display documents.

M7 (Capítulo 1, Capítulo 7, 7.3) - Coggle Diagram

- - - - 1º: Não tem elementos repetidos
      - 2º: Não tem ordem
    - - Estrutura de dados que faz essas 3 operações: Dicionário.
- - - - 1º: input enhacement:
        
        pré processar o input para acelerar a resolução do problema.
      - 2º: prestructturing:
        
        usa memória extra para facilitar o acesso de dados.
      - 3º: dynamic programming:
        
        registra soluções para subproblemas sobrepostos de um determinado problema.
- - - - Chave que nomeia uma categoria específica de algum tópico. Pode armazenar informações.
    - - Array unidimensional onde as keys são armazenadas. O número de chaves é denotado pela letra 'n' e o número de células da hash table é denotado pela letra 'm'.
    - - Função que recebe o argumento Key e retorna um inteiro que dirá sua posição na hash table.
    - - Localização da key na hash table
    - - Open Hashing(Separate Chaining):
        
        As keys são armazenadas em uma linked list anexadas às células da hash table
        
        Load factor = n/m. Determina a eficiência do hashing e quanto mais próximo de 1, melhor.
        
        Search, insertion e delete tem eficiência constante.
      - Closed Hashing(Open Addressing):
        
        As keys são armazenadas na hash table sem o auxílio de linked list, portanto a table tem que ter número de células 'm' PELO MENOS igual ao número de chaves 'n'.
        
        Maneira mais simples e comum de checar colisões:
        
        Linear probing:
        
        Se há colisões de posição de chaves diferentes então é verificado se a célula seguinte está livre. Se sim, a chave é armazenada nela. Se não, continua-se verificando.
        
        Cluster: Sequência contínuas de células ocupadas quando a linear probing é utilizada.
        
        Procurando por uma chave:
        
        Calcula-se a hash function daquela chave e procura-se a chave na posição obtida pela hash function. Caso a chave não esteja lá, procura-se na chave seguinte,, até que a chave seja achada.
        
        Rehashing: A hash table atual é escaneada e passada para uma hash table maior.