Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM7 - Coggle Diagram

- - - - Essa função atribui um número inteiro entre 0 e m-1, chamado endereço hash, para a chave
        
        No geral a função hash deve satisfazer os seguintes requisitos:
        
        O tamanho da tabela não deve ser excessivamente maior que o número de chaves, mas deve ser o suficiente para não comprometer a eficiência do tempo de implementação
        
        Uma função hash precisa distribuir as chaves da maneira mais uniforme possível
        
        Uma função hash deve ser fácil de calcular
  - - - Mesmo com isso deve se implementar um mecanismo de resolução de colisão, existem duas versões: o hash aberto (encadeamento separado) e o hash fechado (endereçamento aberto)
        
        Hash aberto: as chaves são armazenadas em listas vinculadas anexadas as células de uma tabela hash
        
        A eficiência da pesquisa depende do comprimento da lista encadeada, que, por sua vez, depende do dicionário e tamanho da tabela, bem como a qualidade da função hash
        
        Hash fechado: todas as chaves são armazenadas na própria tabela hash sem o uso lista vinculada (isso implica que o tamanho da tabela m deve ser pelo menos tão grande quando o número de chave n)
        
        Diferentes estratégias podem ser usadas para resolução de colisões, a mais simples chamada sondagem linear verifica se ocorre colisão na célula seguinte, Se essa célula estiver vazia, a chave é instalada ali, mas se a próxima já estiver ocupada, é verificada a disponibilidade do sucessor imediato daquela célula e assim por diante
        
        Se o final da tabela hash for atingido a pesquisa será quebrada no início da tabela, ou seja, é tratado como uma matriz circular
        
        À medida que a tabela hash se aproxima de estar cheia o desempenho da sondagem linhear deteriora-se devido a um fenômeno chamado cluster
        
        Cluster: em sondagem linear é uma sequência de células ocupadas contiguamente (com um possível empacotamento)
        
        Cluster são uma má notícia no hashing porque tornam as operações dicionário menos eficiente
        
        1 more item...