Please enable JavaScript.

Coggle requires JavaScript to display documents.

Os trade-offs de espaço e tempo, Hashing - Coggle Diagram

- - - - Hashing
      - Indexação com árvores binarias
- - - - O mais simples - chamado de sondagem linear - verifica a célula seguinte àquela onde ocorre a colisão. Se essa célula estiver vazia, a nova chave é instalada lá; se a próxima célula já estiver ocupada, a disponibilidade do sucessor imediato dessa célula é verificada e assim por diante.
        
        Observe que se o fim da tabela hash for alcançado, a pesquisa será quebrada para o início da tabela; ou seja, é tratado como um array circular.
        
        Se a célula h (K) estiver vazia, a pesquisa não foi bem-sucedida. Se a célula não estiver vazia, devemos comparar K com o ocupante da célula: se eles forem iguais, encontramos uma chave correspondente; se não forem, comparamos K com uma chave na próxima célula e continuamos dessa maneira até encontrarmos uma chave correspondente (uma pesquisa bem-sucedida) ou uma célula vazia (uma pesquisa malsucedida).
        
        Embora as operações de pesquisa e inserção sejam diretas para esta versão de hashing, a exclusão não é.
        
        Por exemplo, se simplesmente excluirmos a chave ARE do último estado da tabela hash no exemplo, não poderemos encontrar a chave SOON depois. De fato, depois de calcular h (SOON) = 11, o algoritmo encontraria esse local vazio e relataria o resultado da pesquisa malsucedido.
        
        Uma solução simples é usar "exclusão preguiçosa", por exemplo, para marcar locais previamente ocupados por um símbolo especial para distingui-los dos locais que não foram ocupados.
  - - - Os clusters são más notícias no hashing porque tornam as operações de dicionário menos eficientes.
        
        Conforme os clusters se tornam maiores, a probabilidade de que um novo elemento seja anexado a um cluster aumenta; além disso, grandes clusters aumentam a probabilidade de que dois clusters se aglutinem após a inserção de uma nova chave, causando ainda mais clustering.
        
        Várias outras estratégias de resolução de colisão foram sugeridas para aliviar esse problema.
        
        Um dos mais importantes é o double hashing. Sob este esquema, usamos outra função hash, s (K), para determinar um incremento fixo para a sequência de sondagem a ser usada após uma colisão no local l = h (K).
        
        Análise matemática de double hashing provou ser bastante difícil. Alguns resultados parciais e uma experiência prática considerável com o método sugerem que, com boas funções de hashing, tanto o double hash primário quanto o secundário são superiores ao teste linear.
        
        Mas seu desempenho também se deteriora quando a tabela fica quase cheia. Uma solução natural em tal situação é o rehashing: a tabela atual é verificada e todas as suas chaves são realocadas em uma tabela maior.
- - - - Em geral, uma função hash precisa satisfazer requisitos um tanto conflitantes:
        
        Uma função hash precisa distribuir as chaves entre as células da tabela hash da maneira mais uniforme possível. (Este requisito torna desejável, para a maioria dos aplicativos, ter uma função hash dependente de todos os bits de uma chave, não apenas de alguns deles.)
        
        Uma função hash deve ser fácil de calcular.
        
        O tamanho de uma tabela hash não deve ser excessivamente grande em comparação com o número de chaves, mas deve ser suficiente para não comprometer a eficiência de tempo da implementação
        
        Obviamente, se escolhermos o tamanho m de uma tabela de hash para ser menor do que o número de chaves n, teremos colisões - um fenômeno de duas (ou mais) chaves sendo hash na mesma célula da tabela de hash.
        
        Mas as colisões devem ser esperadas mesmo se m for consideravelmente maior do que n
        
        Na verdade, no pior caso, todas as chaves podem ser criptografadas para a mesma célula da tabela de hash. Felizmente, com um tamanho de tabela de hash apropriadamente escolhido e uma boa função de hash, essa situação acontece muito raramente.
        
        Ainda assim, todo esquema de hashing deve ter um mecanismo de resolução de colisão. Esse mecanismo é diferente nas duas versões principais de hashing: hashing aberto (também chamado de encadeamento separado) e hashing fechado (também chamado de endereçamento aberto).
- - - - Normalmente queremos ter um fator de carga proximo de 1.
      - Tê-lo muito pequeno implicaria em muitas listas vazias e, portanto, no uso ineficiente do espaço; tê-lo muito grande significaria listas vinculadas mais longas e, portanto, tempos de pesquisa mais longos.
      - Mas se nós temos a taxa de ocupação em torno de 1, temos um esquema incrivelmente eficiente que possibilita a busca por uma dada chave pelo preço de, em média, uma ou duas comparações!
        
        É verdade que, além das comparações, precisamos gastar tempo calculando o valor da função hash para uma chave de pesquisa, mas é uma operação de tempo constante, independente de n e m.
        
        Observe que estamos obtendo essa eficiência notável não apenas como resultado da engenhosidade do método, mas também à custa de espaço extra.