Please enable JavaScript.

Coggle requires JavaScript to display documents.

Conjuntos e Dicionários - Coggle Diagram

- - - - Em geral, a eficiência da pesquisa depende dos comprimentos das listas ligadas, que, por sua vez, dependem dos tamanhos do dicionário e da tabela, bem como da qualidade da função hash. Se a função hash distribuir n chaves entre as m células da tabela hash uniformemente, cada lista terá cerca de n / m chaves. A razão α = n / m, chamada de load factor da tabela hash, desempenha um papel crucial na eficiência do hash. Em particular, o número médio de ponteiros (chain links) inspecionados em pesquisas bem-sucedidas, S, e pesquisas malsucedidas, U, acaba sendo S ≈ 1+ α 2 e U = α, respectivamente, sob as premissas padrão de busca por um elemento selecionado aleatoriamente e uma função hash distribuindo chaves uniformemente entre as células da tabela.
      - Normalmente, deseja-se que o load factor não esteja longe de 1. Se ele for muito pequeno, isso implicaria em muitas listas vazias e, portanto, no uso ineficiente de espaço; tê-lo muito grande significaria listas ligadas mais longas e, portanto, tempos de pesquisa mais longos. Mas se tiver o load factor em torno de 1, tem-se um esquema incrivelmente eficiente que torna possível procurar uma determinada chave pelo preço, em média, de uma ou duas comparações. É verdade que, além das comparações, precisa-se 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. Observa-se que está-se obtendo essa eficiência notável não apenas como resultado da engenhosidade do método, mas também à custa de espaço extra.
      - As duas outras operações de dicionário - inserção e exclusão - são quase idênticas à pesquisa.
        
        Inserções são normalmente feitas no final da lista.
        
        A exclusão é realizada procurando uma chave a ser excluída e, em seguida, removendo-a de sua lista. Portanto, a eficiência dessas operações é idêntica à da pesquisa e são todas (1) no caso médio se o número de chaves n for quase igual ao tamanho da tabela de hash m.
      - No open hashing, as chaves são armazenadas em listas ligadas anexadas às células de uma tabela de hash. Cada lista contém todas as chaves com hash para sua célula.
    - - No closed hash, todas as chaves são armazenadas na própria tabela de hash sem o uso de listas ligadas. (Obviamente, isso implica que o tamanho da tabela m deve ser pelo menos tão grande quanto o número de chaves n.) Diferentes estratégias podem ser empregadas para resolução de colisões. A mais simples - chamada 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á enrolada para o início da tabela; ou seja, é tratado como uma matriz circular.
      - Para pesquisar uma determinada chave K, começamos calculando h(K) onde h é a função hash usada na construção da tabela. Se a célula h(K) estiver vazia, a pesquisa não foi bem-sucedida. Se a célula não estiver vazia, deve-se comparar K com o ocupante da célula: se eles forem iguais, encontra-se uma chave correspondente; se não forem, compara-se K com uma chave na próxima célula e continua-se dessa maneira até que se encontre 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 de exclusão não é. Uma solução simples é usar "lazy deletion", ou seja, para marcar locais previamente ocupados com um símbolo especial para distingui-los dos locais que não foram ocupados. A análise matemática da sondagem linear é um problema muito mais difícil do que o do encadeamento separado. As versões simplificadas desses resultados afirmam que o número médio de vezes que o algoritmo deve acessar a tabela de hash com o load factor α em pesquisas bem e malsucedidas é , respectivamente, S≈1/2(1+ 1/1− α) e U≈ 1/2(1+ 1/(1− α)²), e a precisão dessas aproximações aumenta com tamanhos maiores da tabela hash.
      - À medida que a tabela de hash fica mais perto de ficar cheia, o desempenho da sondagem linear se deteriora devido a um fenômeno denominado clustering. Um cluster em sondagem linear é uma sequência de células ocupadas de forma contígua (com um possível envoltório (retornar ao início da tabela)).
      - 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 hashing duplo. 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).
        
        Para garantir que cada localização na tabela seja sondada pela sequência, o incremento s(k) e o tamanho da tabela m devem ser relativamente primos, ou seja, seu único divisor comum deve ser 1. (Esta condição é satisfeita automaticamente se m em si é primo.) Algumas funções recomendadas na literatura são s(k) = m - 2 - k mod (m - 2) e s (k) = 8 - (k mod 8) para tabelas pequenas e s (k) = k mod 97 + 1 para os maiores.
        
        A análise matemática de hashing duplo 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 primárias quanto secundárias - o hashing duplo é superior à sondagem linear. Mas seu desempenho também se deteriora quando a tabela fica quase cheia. Uma solução natural em tal situação é refazer o hash: a tabela atual é verificada e todas as suas chaves são realocadas em uma tabela maior.
- - - - Primeiro, um conjunto não pode conter elementos idênticos; uma lista pode. Esse requisito de exclusividade às vezes é contornado pela introdução de um multiset, ou bag, uma coleção não ordenada de itens que não são necessariamente distintos.
      - Em segundo lugar, um conjunto é uma coleção não ordenada de itens; portanto, alterar a ordem de seus elementos não altera o conjunto. Uma lista, definida como uma coleção ordenada de itens, é exatamente o oposto. Esta é uma distinção teórica importante, mas felizmente não é importante para muitas aplicações. Também vale a pena mencionar que se um conjunto for representado por uma lista, dependendo da aplicação em questão, pode valer a pena manter a lista ordenada.