Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hashing, Closed Hashing - Coggle Diagram
Hashing
Hashing é baseado na ideia de distribuir chaves por um array unidimensional chamado de Tabela de Hash.
A distribuição é feita computando para cada uma das chaves o valor de uma função pré definida, chamada função hash
-
A função hash vai depender da característica das chaves do dicionário, podendo ser um resto de divisão, ou uma posição no alfabeto, etc;
A função hash deve distribuir as chaves entre as células da tabela hash de maneira mais uniforme possível e ela deve ser de fácil computação.
Uma tabela hash não deve ser excessivamente grande comparada com o número de chaves, mas deve ser suficiente para não sacrificar a eficiência temporal da implementação.
Se temos uma tabela hash de tamanho menos que o número de chaves, vamos ter colisões, ou seja, duas chaves apontando para a mesma célula da tabela.
No pior caso, todas as chaves podem apontar para uma mesma célula. Felizmente, isso raramente acontece, mas mesmo assim precisamos ter um mecanismo de resolução de colisão.
Open Hashing
Em Open Hashing, chaves são armazenadas em listas ligadas que são conectadas a células de uma tabela hash.
Se a função hash distribui n chaves entre m células da hash table uniformemente, então cada lista deve ter tamanho n/m. A razão que esse tamanho define é chamado de fator de carregamento/ load factor da tabela hash e faz um papel crucial na eficiência do hashing.
Em média, o número de ponteiros (Nós) analisados em buscas com retorno positivo é S ( Mais ou menos 1 + Load Factor/2 ) e com retorno negativo é U (Load factor)
Quase igual a procurar em uma lista ligada normal, o que a gente ganhou no hashing foi uma redução do tamanho da lista por m, que é o tamanho da tabela hash.
Não queremos que o Load Factor seja distante de 1, se ele for muito pequeno, significa que temos listas ligadas maiores e tempo de busca maior. Se for bem próximo de 1, então temos um esquema extremamente eficiente.
-
Closed Hashing
Todas as chaves são armazenadas na própria tabela hash sem o uso de listas ligadas. A tabela deve, então, ser PELO MENOS tão grande quanto a quantidade de chaves.
Para resolver conflitos temos Linear Probing, estratégia que checa a célula depois da qual a colisão acontece.
Se a célula está vazia, então a nova chave é colocada ali. Se já está ocupada, então a próxima célula é checada e assim sucessivamente.
Se chegar no fim, ele volta para o começo. Para buscar, primeiro vamos computar o hash da chave que queremos buscar e depois checar se a chave está naquela posição e , caso a posição não for vazia, se o conteúdo daquela célula é a chave.
A deleção é o maior problema nessa versão de hashing. Se deletamos uma chave, não vamos poder acessar a chave que está na célula que sucede a célula deletada.
Solução é Lazy Deletion, ou seja, marcar células previamente ocupadas com um símbolo especial para diferenciar células que nunca foram antes ocupadas.
A performance de Linear Probing reduz com o aumento de células preenchidas, por um fenômeno chamado Cluster, ou seja, uma sequência de células ocupadas contíguamente. Eles vão fazer as operações menos eficientes, pois vamos ter que checar várias vezes até achar uma célula vazia.
Double Hashing
Usamos outra função para determinar um incremento fixo para o linear probing conseguir "pular" algumas células. No entanto, essa abordagem também piora quando a tabela enche.
-
-