Please enable JavaScript.
Coggle requires JavaScript to display documents.
HASHING - Coggle Diagram
HASHING
Em geral, uma hash function precisa satisfazer requisitos um tanto conflitantes:
O tamanho de uma hash table 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.
Uma hash function precisa distribuir chaves entre as células da hash table como uniformemente possível. (Este requisito torna desejável, para a maioria das aplicações, ter uma hash function dependente de todos os bits de uma chave, não apenas alguns deles.)
Uma hash function deve ser fácil de calcular.
A noção de conjunto desempenha um papel central na matemática.
Um conjunto pode ser descrito como
uma coleção não ordenada (possivelmente vazia) de itens distintos chamados elementos do conjunto.
Um conjunto específico é definido por uma listagem explícita de seus elementos ou especificando uma propriedade que todos os elementos do conjunto e somente eles devem
satisfazer
As operações de conjuntos mais importantes são:
verificar a pertinência de um determinado item em um determinado conjunto
encontrar a união de dois conjuntos, que compreende todos os elementos de um ou de ambos
encontrar a interseção dos dois conjuntos, que compreende todos os elementos comuns entre eles
Os conjuntos podem ser implementados em aplicativos de computador de duas maneiras.
O primeiro considera apenas conjuntos que são subconjuntos de algum grande conjunto U, chamado conjunto universal.
Se o conjunto U tem n elementos, então qualquer subconjunto S de U pode ser representado por uma string de bits, chamada vetor de bits, no qual o i-ésimo elemento é 1 se e somente se o i-ésimo elemento de U está incluído no conjunto S.
Exemplo: se U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, então S = {2, 3, 5, 7} é representado pela string de bits 011010100.
Esta forma de representação de conjuntos permite implementar as operações de conjunto padrão muito rápido, mas à custa de potencialmente usar um grande quantidade de armazenamento.
A segunda e mais comum maneira de representar um conjunto para fins de computação é usar a estrutura de lista para indicar os elementos do conjunto.
Esta opção é viável apenas para conjuntos finitos.
Há dois pontos principais de
distinção entre conjuntos e listas:
Primeiro, um conjunto não pode conter elementos idênticos;
uma lista pode.
Segundo, 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 coleção ordenada de itens, é exatamente o oposto.
Todo esquema de hash deve ter um mecanismo de resolução de colisão. Esse mecanismo é diferente nas duas versões principais de hashing:
Open hashing
No open hashing, as chaves são armazenadas em listas vinculadas anexadas às células de uma hash table. Cada lista contém todas as chaves com hash para sua célula.
Em geral, a eficiência da busca depende dos comprimentos das listas vinculadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como da qualidade da função hash. Se a função hash distribuir n chaves entre m células do
tabela de hash aproximadamente uniformemente, cada lista terá cerca de n/m chaves de comprimento. A razão α = n/m,
chamado de fator de carga da tabela de hash, desempenha um papel crucial na eficiência do hash.
Em particular, o número médio de ponteiros (links de cadeia) inspecionados em pesquisas bem-sucedidas, S, e pesquisas mal sucedidas, U, é:
S = 1 + a/2, sendo a = U
Normalmente, queremos que o fator de carga não esteja longe de 1. Se for muito pequeno implicaria muitas listas vazias e, portanto, uso ineficiente do espaço. No entanto, se for muito
grande significaria listas vinculadas mais longas e, portanto, tempos de pesquisa mais longos.
Se tivermos o fator de carga em torno de 1, temos um esquema incrivelmente eficiente que possibilita a busca de uma determinada chave, em média, pelo preço de uma ou
duas comparações.
As inserções são normalmente feitas no final de uma lista.
1 more item...
Closed hashing
No closed hashing, todas as chaves são armazenadas na própria hash table, sem o uso de listas encadeadas.
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 a
resolução da colisão.
O mais simples - chamado de sondagem linear - verifica a célula seguinte àquela em que ocorre a colisão. Se essa célula estiver vazia, a nova chave será instalada lá. Se a próxima célula já estiver ocupada, a disponibilidade do sucessor imediato dessa célula é verificado, e assim por diante.
Se o final da hash table for atingido, a pesquisa é encapsulada no início da tabela; ou seja, é tratada como um array circular.
Embora as operações de busca e inserção sejam diretas para closed hashing, a exclusão não é.
Uma solução simples é usar a “exclusão preguiçosa”, ou seja, marcar locais anteriormente ocupados com um símbolo para distinguí-los de locais que não foram ocupados.
1 more item...
Uma das estratégias mais importantes é o double hashing.
O double hashing é superior à sondagem linear. Mas seu desempenho também se deteriora quando a tabela fica perto de estar cheia.
Uma solução natural em tal situação é refazer: o tabela atual é verificada e todas as suas chaves são realocadas em uma tabela maior.
Vale a pena comparar as principais propriedades do hash com árvoves de busca balanceada, sua principal concorrente na implementação de dicionários.
Eficiência de tempo assintótica: Com hash, pesquisa, inserção e exclusão pode ser implementado para levar theta(1) no caso médio, mas theta(n) no pior caso. Para árvores de busca balanceada, as eficiências de tempo médias são theta(log n), tanto para o melhor caso, quanto para o pior.
Preservação da ordenação: Ao contrário das árvores de busca balanceadas, o hashing não assume a existência de ordenação chave e geralmente não a preserva.
Uma estrutura de dados que implementa as operações de procurar um determinado elemento, adicionar um novo elemento, e excluir um elemento é chamada de dicionário.
Uma implementação eficiente de um dicionário tem que encontrar um compromisso entre a eficiência da busca e as eficiências das outras duas operações.
Existem várias maneiras de um dicionário
ser implementado.
Eles variam de um uso não sofisticado de arrays (classificados ou não) a técnicas muito mais sofisticadas, como hashing e árvores de pesquisa balanceada.
Dicionário é um tipo de dado abstrato, ou seja, um conjunto com as operações de pesquisa, inserção e exclusão definida em seus elementos.
Os elementos deste conjunto podem ser de natureza arbitrária: números, caracteres de algum alfabeto, cadeias de caracteres e assim por diante.
Hashing é baseado na ideia de distribuir chaves entre um array H[0..m − 1] chamado de hash table.
A distribuição é feita por computação, para cada uma das chaves, o valor de alguma função predefinida h chamada de hash function. Esta função atribui um inteiro entre 0 e m − 1, chamado de hash address, para uma chave.