Práticas para funções hash

Prévia do material em texto

Práticas para funções hash 
Uma boa função hash é essencial para o bom desempenho de uma tabela hash. As colisões 
geralmente são resolvidas por algum tipo de pesquisa linear, portanto, se a função tende 
a retornar valores semelhantes, as pesquisas resultantes tornam-se lentas. 
Em uma função de hash ideal, alterar um único bit na chave deve alterar metade dos bits 
no hash, e essa alteração deve ser independente das alterações causadas por outros bits. 
da chave. 
 
Uma vez que uma função hash pode ser difícil de projetar ou computacionalmente cara 
para executar, muito esforço foi gasto no desenvolvimento de estratégias de resolução de 
colisão que mitigam o desempenho de hash ruim. No entanto, nenhuma dessas estratégias 
é tão eficaz quanto desenvolver uma boa função hash pronta para uso. 
É desejável usar a mesma função hash para matrizes de qualquer tamanho concebível. 
Para isso, o índice de sua localização na matriz da tabela hash é geralmente calculado em 
duas etapas: 
1. Um valor hash genérico é calculado, preenchendo um número inteiro natural da 
máquina. 
2. Este valor é reduzido a um índice válido no vetor, encontrando seu módulo em 
relação ao tamanho da matriz. 
O tamanho do vetor das tabelas hash geralmente é um número primo. Isso é feito para 
evitar a tendência de hashes de inteiro grandes terem divisores comuns com o tamanho 
da tabela de hash, o que causaria colisões após o cálculo do módulo. No entanto, o uso de 
uma tabela de tamanho principal não substitui uma boa função hash. 
Um problema bastante comum que ocorre com funções hash é o congestionamento. O 
agrupamento ocorre quando a estrutura da função hash faz com que as chaves comumente 
usadas tendam a ficar muito próximas umas das outras ou consecutivamente na tabela 
hash. Isso pode degradar o desempenho significativamente quando a tabela se enche 
usando certas estratégias de resolução de colisão, como a medição linear. 
Ao depurar o tratamento de colisão em uma tabela hash, geralmente é útil usar uma função 
hash que sempre retorna um valor constante, como 1, causando colisão em cada inserção. 
Funções hash mais usadas: 
 
1. Hash da divisão: 
Dado um dicionário D, um número m> = | D | (m maior ou igual ao tamanho do dicionário) 
e esse é um primo não perto de uma potência de 2 ou de 10. Com k sendo a chave para 
procurar eh (k) a função hash, temos h (k) = k% m (Resto da divisão k / m). 
 
2. Hash de multiplicação 
Se por algum motivo for necessária uma tabela hash com tantos elementos ou ponteiros 
quanto uma potência de 2 ou uma potência de 10, será melhor usar uma função hash de 
multiplicação, independentemente do tamanho da tabela. Escolha um tamanho de mesa 
m> = | D | (m maior ou igual ao tamanho do dicionário) e um certo número irracional φ 
(geralmente 1 + 5 ^ (1/2) / 2 ou 1-5 ^ (1/2) / 2 é usado. 
 
Resolução de colisão 
Se duas chaves geram um hash apontando para o mesmo índice, os registros 
correspondentes não podem ser armazenados na mesma posição. Nestes casos, quando 
uma caixa já está ocupada, devemos encontrar outro local para armazenar o novo registro, 
e fazê-lo de forma que possamos encontrá-lo quando necessário. 
Para dar uma ideia da importância de uma boa estratégia de resolução de colisões, 
considere o seguinte resultado, derivado do paradoxo das datas de nascimento. Mesmo se 
assumirmos que o resultado de nossa função hash gera índices aleatórios distribuídos 
uniformemente por todo o vetor, e mesmo para vetores com 1 milhão de entradas, há 95% 
de chance de que pelo menos uma colisão ocorra antes de atingir 2.500 registros. 
Existem várias técnicas de resolução de colisão, mas as mais populares são o 
encadeamento e o endereçamento aberto. 
Na técnica de encadeamento mais simples, cada célula na matriz faz referência a uma 
lista de registros inseridos que colidem nessa célula. A inserção consiste em encontrar a 
caixa correta e adicionar ao final da lista correspondente. A exclusão consiste em 
pesquisar e remover da lista. 
A técnica de encadeamento tem vantagens sobre o endereçamento aberto. Primeiro, a 
exclusão é simples e, segundo o crescimento da mesa pode ser adiado por muito mais 
tempo, pois o desempenho diminui muito mais lentamente, mesmo quando todas as caixas 
já estão ocupadas. 
Na verdade, muitas tabelas de hash encadeadas podem nunca exigir crescimento, uma vez 
que a degradação do desempenho é linear à medida que a tabela é preenchida. Por 
exemplo, uma tabela hash encadeada com o dobro do número recomendado de itens serão 
duas vezes mais lenta em média que a mesma tabela em sua capacidade recomendada. 
As tabelas hash encadeadas herdam as desvantagens das listas vinculadas. Quando 
pequenas quantidades de informações são armazenadas, a despesa extra de listas 
vinculadas pode ser significativa. Além disso, as viagens pelas listas têm um desempenho 
de cache muito fraco. 
Outras estruturas de dados podem ser usadas para encadeamento em vez de listas 
vinculadas. Usando árvores de auto equilíbrio, por exemplo, o tempo teórico do pior caso 
diminui de O (n) para O (log n). No entanto, como cada lista deve ser pequena, essa 
estratégia geralmente é ineficiente, a menos que a tabela de hash seja projetada para 
funcionar na capacidade máxima ou que haja taxas de colisão particularmente altas. 
Os vetores dinâmicos também podem ser usados para diminuir o espaço extra necessário 
e melhorar o desempenho do cache quando os registros são pequenos.