Função Hash - Hash function

Uma função hash que mapeia nomes para inteiros de 0 a 15. Há uma colisão entre as chaves "John Smith" e "Sandra Dee".

Uma função hash é qualquer função que pode ser usada para mapear dados de tamanho arbitrário para valores de tamanho fixo. Os valores devolvidos por uma função hash são chamados valores de hash , códigos de hash , digere , ou simplesmente hash . Os valores são geralmente usados para indexar uma tabela de tamanho fixo chamada de tabela hash . O uso de uma função hash para indexar uma tabela hash é chamado de hashing ou endereçamento de armazenamento disperso .

As funções de hash e suas tabelas de hash associadas são usadas em aplicativos de armazenamento e recuperação de dados para acessar dados em um tempo pequeno e quase constante por recuperação. Eles exigem uma quantidade de espaço de armazenamento apenas uma fração maior do que o espaço total necessário para os próprios dados ou registros. Hashing é uma forma de acesso a dados com eficiência computacional e de espaço de armazenamento que evita o tempo de acesso não linear de listas ordenadas e não ordenadas e árvores estruturadas e os requisitos de armazenamento frequentemente exponencial de acesso direto a espaços de estado de chaves grandes ou de comprimento variável.

O uso de funções hash depende de propriedades estatísticas de interação de chave e função: o comportamento do pior caso é intoleravelmente ruim com uma probabilidade infinitamente pequena, e o comportamento do caso médio pode ser quase ótimo ( colisão mínima ).

As funções de hash estão relacionadas a (e muitas vezes confundidas com) somas de verificação , dígitos de verificação , impressões digitais , compactação com perdas , funções de randomização , códigos de correção de erros e cifras . Embora os conceitos se sobreponham até certo ponto, cada um tem seus próprios usos e requisitos e é projetado e otimizado de maneira diferente. As funções hash diferem dos conceitos numerados principalmente em termos de integridade de dados.

Visão geral

Uma função hash recebe uma entrada como uma chave, que é associada a um dado ou registro e usada para identificá-lo para o aplicativo de armazenamento e recuperação de dados. As chaves podem ter comprimento fixo, como um número inteiro, ou comprimento variável, como um nome. Em alguns casos, a chave é o próprio dado. A saída é um código hash usado para indexar uma tabela hash contendo os dados ou registros, ou ponteiros para eles.

Uma função hash pode ser considerada para realizar três funções:

Converta chaves de comprimento variável em valores de comprimento fixo (geralmente comprimento de palavra de máquina ou menos), dobrando-as por palavras ou outras unidades usando um operador de preservação de paridade como ADD ou XOR.
Misture os bits da chave para que os valores resultantes sejam uniformemente distribuídos no keyspace.
Mapeie os valores-chave em valores menores ou iguais ao tamanho da tabela

Uma boa função hash satisfaz duas propriedades básicas: 1) deve ser muito rápida para calcular; 2) deve minimizar a duplicação dos valores de saída (colisões). As funções de hash dependem da geração de distribuições de probabilidade favoráveis para sua eficácia, reduzindo o tempo de acesso a quase constante. Altos fatores de carregamento da tabela, conjuntos de chaves patológicas e funções hash mal projetadas podem resultar em tempos de acesso quase lineares no número de itens na tabela. As funções de hash podem ser projetadas para fornecer o melhor desempenho no pior caso, bom desempenho sob altos fatores de carregamento de tabela e, em casos especiais, mapeamento perfeito (sem colisão) de chaves em códigos de hash. A implementação é baseada em operações de bit de preservação de paridade (XOR e ADD), multiplicação ou divisão. Um adjunto necessário para a função hash é um método de resolução de colisão que emprega uma estrutura de dados auxiliar como listas vinculadas ou sondagem sistemática da tabela para encontrar um slot vazio.

Tabelas de hash

As funções hash são usadas em conjunto com as tabelas hash para armazenar e recuperar itens de dados ou registros de dados. A função hash converte a chave associada a cada datum ou registro em um código hash, que é usado para indexar a tabela hash. Quando um item deve ser adicionado à tabela, o código hash pode indexar um slot vazio (também chamado de balde), caso em que o item é adicionado à tabela lá. Se o código hash indexa um slot completo, algum tipo de resolução de colisão é necessária: o novo item pode ser omitido (não adicionado à tabela), ou substituir o item antigo, ou pode ser adicionado à tabela em algum outro local por um procedimento especificado. Esse procedimento depende da estrutura da tabela de hash: no hash encadeado , cada slot é o cabeçalho de uma lista ou cadeia vinculada, e os itens que colidem no slot são adicionados à cadeia. As cadeias podem ser mantidas em ordem aleatória e pesquisadas linearmente, ou em ordem serial, ou como uma lista de auto-ordenação por frequência para acelerar o acesso. No hashing de endereço aberto , a tabela é testada começando do slot ocupado de uma maneira especificada, geralmente por teste linear , teste quadrático ou hashing duplo até que um slot aberto seja localizado ou toda a tabela seja testada (overflow). A procura do item segue o mesmo procedimento até que o item seja localizado, uma vaga aberta seja encontrada ou toda a mesa tenha sido pesquisada (item que não está na tabela).

Usos especializados

As funções de hash também são usadas para construir caches para grandes conjuntos de dados armazenados em mídia lenta. Um cache é geralmente mais simples do que uma tabela de pesquisa com hash, pois qualquer colisão pode ser resolvida descartando ou escrevendo de volta o mais antigo dos dois itens em conflito.

As funções hash são um ingrediente essencial do filtro Bloom , uma estrutura de dados probabilísticos com espaço eficiente que é usada para testar se um elemento é membro de um conjunto .

Um caso especial de hashing é conhecido como hashing geométrico ou método de grade . Nesses aplicativos, o conjunto de todas as entradas é algum tipo de espaço métrico e a função de hash pode ser interpretada como uma partição desse espaço em uma grade de células . A tabela é muitas vezes uma matriz com duas ou mais índices (chamado um arquivo de grade , de índice de grade , grade balde , e nomes similares), e a função hash retorna um índice tuplo . Este princípio é amplamente utilizado em computação gráfica , geometria computacional e muitas outras disciplinas, para resolver muitos problemas de proximidade no plano ou no espaço tridimensional , como encontrar pares mais próximos em um conjunto de pontos, formas semelhantes em uma lista de formas, imagens semelhantes em um banco de dados de imagens e assim por diante.

As tabelas de hash também são usadas para implementar matrizes associativas e conjuntos dinâmicos .

Propriedades

Uniformidade

Uma boa função hash deve mapear as entradas esperadas tão uniformemente quanto possível em seu intervalo de saída. Ou seja, cada valor de hash no intervalo de saída deve ser gerado com aproximadamente a mesma probabilidade . O motivo desse último requisito é que o custo dos métodos baseados em hash aumenta drasticamente à medida que aumenta o número de colisões - pares de entradas mapeadas para o mesmo valor de hash. Se alguns valores de hash são mais prováveis de ocorrer do que outros, uma fração maior das operações de pesquisa terá que pesquisar um conjunto maior de entradas de tabela em conflito.

Observe que este critério requer apenas que o valor seja uniformemente distribuído , não aleatório em nenhum sentido. Uma boa função de randomização (exceto questões de eficiência computacional) é geralmente uma boa escolha como função hash, mas o inverso não precisa ser verdadeiro.

As tabelas de hash geralmente contêm apenas um pequeno subconjunto de entradas válidas. Por exemplo, a lista de sócios de um clube pode conter apenas cerca de cem nomes de sócios, dentre o conjunto muito grande de todos os nomes possíveis. Nesses casos, o critério de uniformidade deve valer para quase todos os subconjuntos típicos de entradas que podem ser encontrados na tabela, não apenas para o conjunto global de todas as entradas possíveis.

Em outras palavras, se um conjunto típico de $m$ registros for convertido em hash para $n$ slots de tabela, a probabilidade de um balde receber muito mais do que $m / n$ registros deve ser muito pequena. Em particular, se $m$ for menor que $n$ , muito poucos buckets devem ter mais de um ou dois registros. Um pequeno número de colisões é virtualmente inevitável, mesmo se $n$ for muito maior do que $m$ - veja o problema do aniversário .

Em casos especiais, quando as chaves são conhecidas com antecedência e o conjunto de chaves é estático, uma função hash pode ser encontrada que atinge uniformidade absoluta (ou sem colisão). Essa função hash é considerada perfeita . Não existe uma maneira algorítmica de construir tal função - a busca por uma é uma função fatorial do número de chaves a serem mapeadas versus o número de slots de mesa nas quais elas estão conectadas. Encontrar uma função de hash perfeita em mais do que um conjunto muito pequeno de chaves geralmente é computacionalmente inviável; a função resultante é provavelmente mais complexa computacionalmente do que uma função hash padrão e fornece apenas uma vantagem marginal sobre uma função com boas propriedades estatísticas que produz um número mínimo de colisões. Veja a função hash universal .

Teste e medição

Ao testar uma função hash, a uniformidade da distribuição dos valores de hash pode ser avaliada pelo teste qui-quadrado . Este teste é uma medida de adequação: é a distribuição real de itens em baldes versus a distribuição esperada (ou uniforme) de itens. A fórmula é: ${\ displaystyle {\ frac {\ sum _ {j = 0} ^ {m-1} (b_ {j}) (b_ {j} +1) / 2} {(n / 2m) (n + 2m-1 )}}}$

onde: é o número de chaves, é o número de baldes, é o número de itens no balde ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle b_ {j}}$ ${\ displaystyle j}$

Uma proporção dentro de um intervalo de confiança (0,95 - 1,05) é indicativo de que a função hash avaliada tem uma distribuição uniforme esperada.

As funções hash podem ter algumas propriedades técnicas que tornam mais provável que tenham uma distribuição uniforme quando aplicadas. Um é o critério estrito de avalanche : sempre que um único bit de entrada é complementado, cada um dos bits de saída muda com uma probabilidade de 50%. O motivo dessa propriedade é que os subconjuntos selecionados do keyspace podem ter baixa variabilidade. Para que a saída seja distribuída uniformemente, uma pequena quantidade de variabilidade, mesmo um bit, deve se traduzir em uma grande quantidade de variabilidade (isto é, distribuição no espaço de tabela) na saída. Cada bit deve mudar com uma probabilidade de 50% porque, se alguns bits relutarem em mudar, as chaves se agrupam em torno desses valores. Se os bits quiserem mudar muito rapidamente, o mapeamento está se aproximando de uma função XOR fixa de um único bit. Testes padrão para esta propriedade foram descritos na literatura. A relevância do critério para uma função hash multiplicativa é avaliada aqui.

Eficiência

Em aplicativos de armazenamento e recuperação de dados, o uso de uma função hash é uma compensação entre o tempo de pesquisa e o espaço de armazenamento de dados. Se o tempo de busca fosse ilimitado, uma lista linear não ordenada muito compacta seria o melhor meio; se o espaço de armazenamento fosse ilimitado, uma estrutura acessível aleatoriamente indexável pelo valor-chave seria muito grande, muito esparsa, mas muito rápida. Uma função hash leva uma quantidade finita de tempo para mapear um keyspace potencialmente grande para uma quantidade viável de espaço de armazenamento pesquisável em uma quantidade limitada de tempo, independentemente do número de chaves. Na maioria dos aplicativos, a função hash deve ser computável com latência mínima e, secundariamente, em um número mínimo de instruções.

A complexidade computacional varia com o número de instruções necessárias e a latência das instruções individuais, sendo os mais simples os métodos bit a bit (dobragem), seguidos pelos métodos multiplicativos, e os mais complexos (mais lentos) são os métodos baseados em divisão.

Como as colisões devem ser raras e causar um atraso marginal, mas são inofensivas, geralmente é preferível escolher uma função hash mais rápida em vez de uma que precise de mais computação, mas economize algumas colisões.

As implementações baseadas em divisão podem ser uma preocupação particular porque a divisão é microprogramada em quase todas as arquiteturas de chip. Divide ( módulo ) por uma constante pode ser invertido para se tornar uma multiplicação pelo multiplicativo-inverso do tamanho da palavra da constante. Isso pode ser feito pelo programador ou pelo compilador. Divide também pode ser reduzido diretamente em uma série de shift-subtracts e shift-add, embora minimizar o número de tais operações necessárias seja um problema assustador; o número de instruções de montagem resultantes pode ser superior a uma dúzia e sobrecarregar o oleoduto. Se a arquitetura tiver unidades multifuncionais de hardware, a multiplicação por inversa é provavelmente uma abordagem melhor.

Podemos permitir que o tamanho $n$ da tabela não seja uma potência de $2$ e ainda não tenhamos que realizar nenhum resto ou operação de divisão, já que esses cálculos às vezes são caros. Por exemplo, seja $n$ significativamente menor que $2 b$ . Considere uma função geradora de números pseudo - aleatórios $P (tecla)$ que é uniforme no intervalo $[0, 2 b - 1]$ . Uma função hash uniforme no intervalo $[0, n -1]$ é $n P (chave) / 2 b$ . Podemos substituir a divisão por um deslocamento de bit à direita (possivelmente mais rápido) : $nP (chave) >> b$ .

Se as chaves estão sendo hash repetidamente, e a função hash é cara, o tempo de computação pode ser economizado ao pré-computar os códigos hash e armazená-los com as chaves. A correspondência de códigos hash quase certamente significa que as chaves são idênticas. Essa técnica é usada para a tabela de transposição em programas de jogos, que armazena uma representação hash de 64 bits da posição do tabuleiro.

Universalidade

Um esquema de hashing universal é um algoritmo aleatório que seleciona uma função de hashing $h$ entre uma família de tais funções, de forma que a probabilidade de uma colisão de quaisquer duas chaves distintas seja $1 / m$ , onde $m$ é o número de valores de hash distintos desejado - independentemente das duas teclas. O hashing universal garante (em um sentido probabilístico) que o aplicativo da função hash se comportará tão bem como se estivesse usando uma função aleatória, para qualquer distribuição dos dados de entrada. No entanto, ele terá mais colisões do que hash perfeito e pode exigir mais operações do que uma função de hash de propósito especial.

Aplicabilidade

Uma função hash é aplicável em uma variedade de situações. Uma função hash que permite apenas certos tamanhos de tabela, strings apenas até um certo comprimento ou não pode aceitar uma semente (ou seja, permitir hash duplo) não é tão útil quanto uma que o faz.

Determinístico

Um procedimento hash deve ser determinístico - o que significa que, para um determinado valor de entrada, ele deve sempre gerar o mesmo valor hash. Em outras palavras, deve ser uma função dos dados a serem hash, no sentido matemático do termo. Esse requisito exclui funções hash que dependem de parâmetros de variáveis externas, como geradores de números pseudo-aleatórios ou a hora do dia. Também exclui funções que dependem do endereço de memória do objeto que está sendo hash nos casos em que o endereço pode mudar durante a execução (como pode acontecer em sistemas que usam certos métodos de coleta de lixo ), embora às vezes seja possível refazer o hash do item.

O determinismo está no contexto da reutilização da função. Por exemplo, Python adiciona o recurso de que as funções hash usam uma semente aleatória que é gerada uma vez quando o processo Python é iniciado, além da entrada a ser hash. O hash Python ( SipHash ) ainda é uma função hash válida quando usado em uma única execução. Mas se os valores forem persistentes (por exemplo, gravados no disco), eles não podem mais ser tratados como valores hash válidos, pois na próxima execução o valor aleatório pode ser diferente.

Intervalo definido

Freqüentemente, é desejável que a saída de uma função hash tenha tamanho fixo (mas veja abaixo). Se, por exemplo, a saída for restrita a valores inteiros de 32 bits, os valores de hash podem ser usados para indexar em uma matriz. Esse hashing é comumente usado para acelerar pesquisas de dados. A produção de saída de comprimento fixo a partir de entrada de comprimento variável pode ser realizada dividindo os dados de entrada em blocos de tamanho específico. As funções de hash usadas para pesquisas de dados usam alguma expressão aritmética que processa iterativamente pedaços da entrada (como os caracteres em uma string) para produzir o valor de hash.

Gama Variável

Em muitos aplicativos, a faixa de valores de hash pode ser diferente para cada execução do programa ou pode mudar ao longo da mesma execução (por exemplo, quando uma tabela de hash precisa ser expandida). Nessas situações, é necessária uma função hash que usa dois parâmetros - os dados de entrada $z$ e o número $n$ de valores hash permitidos.

Uma solução comum é calcular uma função hash fixa com um intervalo muito grande (digamos, $0$ a $232 - 1$ ), dividir o resultado por $n$ e usar o resto da divisão . Se $n$ for uma potência de $2$ , isso pode ser feito mascarando e deslocando bits . Quando essa abordagem é usada, a função hash deve ser escolhida de forma que o resultado tenha uma distribuição bastante uniforme entre $0$ e $n - 1$ , para qualquer valor de $n$ que possa ocorrer na aplicação. Dependendo da função, o resto pode ser uniforme apenas para certos valores de $n$ , por exemplo, números ímpares ou primos .

Faixa variável com movimento mínimo (função hash dinâmica)

Quando a função hash é usada para armazenar valores em uma tabela hash que sobrevive à execução do programa e a tabela hash precisa ser expandida ou reduzida, a tabela hash é chamada de tabela hash dinâmica.

Uma função hash que realocará o número mínimo de registros quando a tabela for redimensionada é desejável. O que é necessário é uma função hash $H (z, n)$ -, onde $Z$ é a chave a ser hash e $n$ é o número de valores de hash permitidos - de tal modo que $H (z, n + 1) = H (z, n)$ com probabilidade perto de $n / (n + 1)$ .

Hash linear e armazenamento em espiral são exemplos de funções hash dinâmicas que são executadas em tempo constante, mas relaxam a propriedade de uniformidade para atingir a propriedade de movimento mínimo. O hash extensível usa uma função hash dinâmica que requer espaço proporcional $an$ para calcular a função hash e se torna uma função das chaves anteriores que foram inseridas. Vários algoritmos que preservam a propriedade de uniformidade, mas requerem tempo proporcional $an$ para calcular o valor de $H (z, n)$ , foram inventados.

Uma função hash com movimento mínimo é especialmente útil em tabelas hash distribuídas .

Normalização de dados

Em alguns aplicativos, os dados de entrada podem conter recursos irrelevantes para fins de comparação. Por exemplo, ao pesquisar um nome pessoal, pode ser desejável ignorar a distinção entre letras maiúsculas e minúsculas. Para tais dados, deve-se usar uma função hash compatível com o critério de equivalência de dados usado: ou seja, quaisquer duas entradas consideradas equivalentes devem produzir o mesmo valor hash. Isso pode ser feito normalizando a entrada antes de fazer o hash, colocando todas as letras em maiúsculas.

Hashing de tipos de dados inteiros

Existem vários algoritmos comuns para fazer hash de inteiros. O método que fornece a melhor distribuição depende dos dados. Um dos métodos mais simples e comuns na prática é o método de divisão por módulo.

Função hash de identidade

Se os dados a serem hash forem pequenos o suficiente, pode-se usar os próprios dados (reinterpretados como um inteiro) como o valor hash. O custo de calcular essa função hash de identidade é efetivamente zero. Essa função hash é perfeita , pois mapeia cada entrada para um valor hash distinto.

O significado de "pequeno o suficiente" depende do tamanho do tipo usado como o valor hash. Por exemplo, em Java , o código hash é um número inteiro de 32 bits. Assim, os objetos de Integerponto flutuante de 32 bits e inteiros de 32 bits Floatpodem simplesmente usar o valor diretamente; enquanto o número inteiro de Long64 bits e o ponto flutuante de 64 bits Doublenão podem usar esse método.

Outros tipos de dados também podem usar esse esquema de hash. Por exemplo, ao mapear cadeias de caracteres entre maiúsculas e minúsculas , pode-se usar a codificação binária de cada caractere, interpretado como um inteiro, para indexar uma tabela que fornece a forma alternativa desse caractere ("A" para "a", " 8 "para" 8 ", etc.). Se cada caractere for armazenado em 8 bits (como em ASCII estendido ou ISO Latin 1 ), a tabela terá apenas 2 ⁸ = 256 entradas; no caso de caracteres Unicode , a tabela teria 17 × 2 ¹⁶ =1 114 112 entradas.

A mesma técnica pode ser usada para mapear códigos de país de duas letras como "us" ou "za" para nomes de países (26 ² = 676 entradas de tabela), códigos postais de 5 dígitos como 13083 para nomes de cidades (100 000 entradas), etc. valores de dados inválidos (tal como o código de país "xx" ou o código postal 00000) pode ser deixado indefinido na mesa ou mapeado para alguns apropriado valor "nulo".

Função hash trivial

Se as chaves forem distribuídas de maneira uniforme ou suficientemente uniforme no keyspace, de modo que os valores das chaves sejam essencialmente aleatórios, eles podem ser considerados como já 'hash'. Nesse caso, qualquer número de bits na chave pode ser discado e agrupado como um índice na tabela hash. Uma função hash simples seria mascarar os bits m inferiores para usar como um índice em uma tabela de tamanho 2 ^m .

Dobrando

Um código hash dobrável é produzido dividindo a entrada em n seções de m bits, onde 2 ^ m é o tamanho da tabela, e usando uma operação bit a bit de preservação de paridade como ADD ou XOR, para combinar as seções. A operação final é uma máscara ou mudanças para eliminar quaisquer bits em excesso na extremidade superior ou inferior. Por exemplo, para um tamanho de tabela de 15 bits e valor de chave de 0x0123456789ABCDEF, existem 5 seções 0x4DEF, 0x1357, 0x159E, 0x091A e 0x8. Adicionando, obtemos 0x7AA4, um valor de 15 bits.

Quadrados médios

Um código hash de quadrados médios é produzido pela quadratura da entrada e extração de um número apropriado de dígitos médios ou bits. Por exemplo, se a entrada for 123.456.789 e o tamanho da tabela hash 10.000, elevar a chave ao quadrado produz 15.241.578.750.190.521, então o código hash é considerado os 4 dígitos do meio do número de 17 dígitos (ignorando o dígito alto) 8750. Os quadrados médios método produz um código hash razoável se não houver muitos zeros à esquerda ou à direita na chave. Esta é uma variante do hashing multiplicativo, mas não tão boa porque uma chave arbitrária não é um bom multiplicador.

Hashing de divisão

Uma técnica padrão é usar uma função de módulo na tecla, selecionando um divisor que é um número primo próximo ao tamanho da mesa . O tamanho da mesa é geralmente uma potência de 2. Isso dá uma distribuição de . Isso dá bons resultados em um grande número de conjuntos de chaves. Uma desvantagem significativa do hashing de divisão é que a divisão é microprogramada na maioria das arquiteturas modernas, incluindo x86, e pode ser 10 vezes mais lenta do que a multiplicação. Uma segunda desvantagem é que ele não divide as chaves agrupadas. Por exemplo, as teclas 123000, 456000, 789000, etc. módulo 1000 são mapeadas para o mesmo endereço. Essa técnica funciona bem na prática porque muitos conjuntos de chaves já são suficientemente aleatórios e a probabilidade de que um conjunto de chaves seja cíclico por um grande número primo é pequena. ${\ displaystyle M}$ ${\ displaystyle h (K) = K \ mod M}$ ${\ displaystyle \ {0, M-1 \}}$

Codificação algébrica

A codificação algébrica é uma variante do método de divisão de hashing, que usa a divisão por um módulo polinomial 2 em vez de um inteiro para mapear n bits em m bits. Nesta abordagem, postulamos um polinômio de grau . Uma chave pode ser considerada como o polinômio . O restante usando o módulo 2 de aritmética polinomial é . Então . Se for construído para ter t ou menos coeficientes diferentes de zero, então as chaves que compartilham menos do que t bits têm a garantia de não colidir. ${\ displaystyle M = 2 ^ {m}}$ ${\ displaystyle m}$ ${\ displaystyle \ mathrm {Z} (x) = x ^ {m} + \ zeta _ {m-1} x ^ {m-1} + ... + \ zeta _ {0}}$ ${\ displaystyle K = (k_ {n-1} ... k_ {1} k_ {0}) _ {2}}$ ${\ displaystyle K (x) = k_ {n-1} x ^ {n-1} + ... + k_ {1} x + k_ {0}}$ ${\ displaystyle K (x) \ mod {Z (x)} = h_ {m-1} x ^ {m-1} + ... + h_ {1} x + h_ {0}}$ ${\ displaystyle h (K) = (h_ {m-1} ... h_ {1} h_ {0}) _ {2}}$ ${\ displaystyle Z (x)}$

Z uma função de k, t e n, um divisor de 2 ^k -1, é construída a partir do campo GF (2 ^k ). Knuth dá um exemplo: para n = 15, m = 10 e t = 7 ,. A derivação é a seguinte: ${\ displaystyle Z (x) = x ^ {10} + x ^ {8} + x ^ {5} + x ^ {4} + x ^ {2} + x + 1}$

Let ser o menor conjunto de inteiros ${\ displaystyle S}$ ${\ displaystyle \ ni \ {1,2, ..., t \} \ subseteq S \ land (2j) \ mod n \ in S \ forall j \ in S}$

Defina onde e onde os coeficientes de são calculados neste campo. Em seguida, o grau de . Visto que é uma raiz de sempre que é uma raiz, segue-se que os coeficientes de satisfazem então são todos 0 ou 1. Se for qualquer módulo polinomial diferente de zero 2 com no máximo t coeficientes diferentes de zero, então não é um múltiplo do módulo 2. Se segue que a função hash correspondente mapeará as chaves com menos de t bits em comum para índices únicos. ${\ displaystyle P (x) = \ prod _ {j \ in S} (x- \ alpha ^ {j})}$ ${\ displaystyle \ alpha \ in ^ {n} GF (2 ^ {k})}$ ${\ displaystyle P (x)}$ ${\ displaystyle P (x) = | S |}$ ${\ displaystyle \ alpha ^ {2j}}$ ${\ displaystyle P (x)}$ ${\ displaystyle \ alpha ^ {j}}$ ${\ displaystyle p ^ {i}}$ ${\ displaystyle P (x)}$ ${\ displaystyle p_ {i} ^ {2} = p_ {i}}$ ${\ displaystyle R (x) = r _ {(n-1)} x ^ {n-1} + ... + r_ {1} x + r_ {0}}$ ${\ displaystyle R (x)}$ ${\ displaystyle P (x)}$

O resultado usual é que n ficará grande, ou twill ficará grande, ou ambos, para que o esquema seja computacionalmente viável. Portanto, é mais adequado para implementação de hardware ou microcódigo.

Hash de permutação única

Consulte também hashing de permutação exclusivo, que tem o melhor tempo de inserção de pior caso garantido.

Hash multiplicativo

O hash multiplicativo padrão usa a fórmula que produz um valor de hash em . O valor é um valor escolhido apropriadamente que deve ser relativamente primo a ; deve ser grande e sua representação binária uma mistura aleatória de 1s e 0s. Um importante caso prático especial ocorre quando e são potências de 2 e é o tamanho da palavra da máquina . Nesse caso, essa fórmula se torna . Isso é especial porque o módulo aritmético é feito por padrão em linguagens de programação de baixo nível e a divisão inteira por uma potência de 2 é simplesmente um deslocamento para a direita, então, em C, por exemplo, esta função torna-se ${\ displaystyle h_ {a} (K) = \ lfloor (aK {\ bmod {W}}) / (W / M) \ rfloor}$ ${\ displaystyle \ {0, \ ldots, M-1 \}}$ ${\ displaystyle a}$ ${\ displaystyle W}$ ${\ displaystyle W = 2 ^ {w}}$ ${\ displaystyle M = 2 ^ {m}}$ ${\ displaystyle w}$ ${\ displaystyle h_ {a} (K) = \ lfloor (aK {\ bmod {2}} ^ {w}) / 2 ^ {wm} \ rfloor}$ ${\ displaystyle 2 ^ {w}}$

unsigned hash(unsigned K)
{ 
   return (a*K) >> (w-m);
}

e para fixo e isso se traduz em uma única multiplicação de inteiro e deslocamento para a direita, tornando-a uma das funções hash mais rápidas de calcular. ${\ displaystyle m}$ ${\ displaystyle w}$

O hashing multiplicativo é suscetível a um "erro comum" que leva a uma difusão pobre - bits de entrada de valor mais alto não afetam bits de saída de valor inferior. Uma transmutação na entrada que desloca a extensão dos bits superiores retidos para baixo e os XORs ou os ADDs à chave antes que a etapa de multiplicação corrija para isso. Portanto, a função resultante é semelhante a:

unsigned hash(unsigned K)
{
   K ^= K >> (w-m); 
   return (a*K) >> (w-m);
}

Hashing de Fibonacci

O hashing de Fibonacci é uma forma de hashing multiplicativo em que o multiplicador é , onde é o comprimento da palavra da máquina e (phi) é a razão áurea . é um número irracional com valor aproximado 5/3 e expansão decimal de 1,618033 ... Uma propriedade desse multiplicador é que ele distribui uniformemente sobre o espaço da tabela, blocos de chaves consecutivas em relação a qualquer bloco de bits na chave. Chaves consecutivas dentro dos bits altos ou baixos da chave (ou algum outro campo) são relativamente comuns. Os multiplicadores para vários comprimentos de palavra são: ${\ displaystyle 2 ^ {w} / \ phi}$ ${\ displaystyle w}$ ${\ displaystyle \ phi}$ ${\ displaystyle \ phi}$ ${\ displaystyle ^ {w}}$

16: a = 40503 ₁₀
32: a = 2654435769 ₁₀
48: a = 173961102589771 ₁₀
64: a = 11400714819323198485 ₁₀

Zobrist hashing

Hashing tabulação, mais geralmente conhecido como Zobrist hashing depois Albert Zobrist , um cientista da computação norte-americano, é um método para a construção de famílias universais de funções hash através da combinação de pesquisa de tabela com as operações de XOR. Este algoritmo provou ser muito rápido e de alta qualidade para fins de hashing (especialmente hash de chaves de números inteiros).

O hashing Zobrist foi originalmente introduzido como um meio de representar de forma compacta as posições do xadrez em programas de jogos de computador. Um número aleatório único foi atribuído para representar cada tipo de peça (seis cada para preto e branco) em cada espaço do tabuleiro. Assim, uma tabela de 64x12 desses números é inicializada no início do programa. Os números aleatórios podem ter qualquer comprimento, mas 64 bits era natural devido aos 64 quadrados no tabuleiro. Uma posição foi transcrita percorrendo as peças em uma posição, indexando os números aleatórios correspondentes (espaços vazios não foram incluídos no cálculo) e XOR juntando-os (o valor inicial pode ser 0, o valor de identidade para XOR ou um aleatório semente). O valor resultante foi reduzido por módulo, dobramento ou alguma outra operação para produzir um índice de tabela hash. O hash Zobrist original foi armazenado na tabela como a representação da posição.

Posteriormente, o método foi estendido para fazer hash de inteiros, representando cada byte em cada uma das 4 posições possíveis na palavra por um número aleatório exclusivo de 32 bits. Assim, uma tabela de 2 ⁸ x ⁴ desses números aleatórios é construída. Um inteiro hash de 32 bits é transcrito indexando sucessivamente a tabela com o valor de cada byte do inteiro de texto simples e XORing os valores carregados juntos (novamente, o valor inicial pode ser o valor de identidade ou uma semente aleatória). A extensão natural para inteiros de 64 bits é o uso de uma tabela de 2 ⁸ x8 números aleatórios de 64 bits.

Esse tipo de função tem algumas propriedades teóricas interessantes, uma das quais é chamada de independência de 3 tuplas, o que significa que cada 3 tupla de chaves tem a mesma probabilidade de ser mapeada para qualquer 3 tupla de valores de hash.

Função hash personalizada

Uma função hash pode ser projetada para explorar a entropia existente nas chaves. Se as chaves têm zeros à esquerda ou à direita, ou campos particulares que não são usados, sempre zero ou alguma outra constante, ou geralmente variam pouco, mascarar apenas os bits voláteis e hash sobre eles fornecerá uma função de hash melhor e possivelmente mais rápida. Os divisores ou multiplicadores selecionados nos esquemas de divisão e multiplicativo podem fazer funções hash mais uniformes se as chaves forem cíclicas ou tiverem outras redundâncias.

Hashing de dados de comprimento variável

Quando os valores dos dados são cadeias de caracteres longas (ou de comprimento variável) - como nomes pessoais, endereços de páginas da web ou mensagens de e-mail - sua distribuição geralmente é muito desigual, com dependências complicadas. Por exemplo, o texto em qualquer idioma natural tem distribuições altamente não uniformes de caracteres e pares de caracteres característicos do idioma. Para esses dados, é prudente usar uma função hash que dependa de todos os caracteres da string - e dependa de cada caractere de maneira diferente.

Meio e termina

Funções de hash simplistas podem adicionar o primeiro e o último $n$ caracteres de uma string junto com o comprimento, ou formar um hash de tamanho de palavra a partir dos 4 caracteres do meio de uma string. Isso economiza a iteração na string (potencialmente longa), mas as funções hash que não fazem hash em todos os caracteres de uma string podem se tornar lineares prontamente devido a redundâncias, agrupamento ou outras patologias no conjunto de chaves. Essas estratégias podem ser eficazes como uma função hash personalizada se a estrutura das chaves for tal que o meio, as extremidades ou outros campos sejam zero ou alguma outra constante invariável que não diferencie as chaves; então, as partes invariáveis das chaves podem ser ignoradas.

Dobramento de personagem

O exemplo paradigmático de dobrar por caracteres é somar os valores inteiros de todos os caracteres na string. Uma ideia melhor é multiplicar o hash total por uma constante, normalmente um número primo considerável, antes de adicionar o próximo caractere, ignorando o estouro. Usar 'ou' exclusivo em vez de adicionar também é uma alternativa plausível. A operação final seria um módulo, máscara ou outra função para reduzir o valor da palavra a um índice do tamanho da tabela. A fraqueza desse procedimento é que as informações podem se agrupar nos bits superiores ou inferiores dos bytes, cujo agrupamento permanecerá no resultado hash e causará mais colisões do que um hash aleatório adequado. Os códigos de byte ASCII, por exemplo, têm um bit superior de 0 e as strings imprimíveis não usam os primeiros códigos de 32 bytes, então as informações (códigos de 95 bytes) são agrupadas nos bits restantes de maneira não óbvia.

A abordagem clássica apelidada de hash PJW com base no trabalho de Peter. J. Weinberger, da ATT Bell Labs na década de 1970, foi originalmente projetado para fazer hashing de identificadores em tabelas de símbolos do compilador, conforme apresentado no "Dragon Book" . Esta função hash desloca os bytes 4 bits antes de adicioná-los juntos. Quando a quantidade é encerrada, os 4 bits superiores são deslocados e, se forem diferentes de zero, XOR retornados ao byte inferior da quantidade cumulativa. O resultado é um código hash de tamanho de palavra ao qual um módulo ou outra operação de redução pode ser aplicada para produzir o índice hash final.

Hoje, especialmente com o advento dos tamanhos de palavras de 64 bits, está disponível um hash de strings de comprimento variável muito mais eficiente por blocos de palavras.

Dobragem de comprimento de palavra

Os microprocessadores modernos permitirão um processamento muito mais rápido se as cadeias de caracteres de 8 bits não forem misturadas ao processar um caractere por vez, mas interpretando a cadeia como uma matriz de inteiros de 32 ou 64 bits e hash / acumulando essas "palavras amplas" valores inteiros por meio de operações aritméticas (por exemplo, multiplicação por constante e deslocamento de bits). A palavra final, que pode ter posições de byte não ocupadas, é preenchida com zeros ou um valor "aleatório" especificado antes de ser dobrada no hash. O código hash acumulado é reduzido por um módulo final ou outra operação para gerar um índice na tabela.

Hash de conversão Radix

Analogamente à forma como uma string de caracteres ASCII ou EBCDIC representando um número decimal é convertida em uma quantidade numérica para computação, uma string de comprimento variável pode ser convertida como $(x 0 a k -1 + x 1 a k -2 + ... + x k -2 a + x k -1)$ . Este é simplesmente um polinômio em uma raiz diferente de zero $a! = 1$ que leva os componentes $(x 0, x 1, ..., x k -1)$ como os caracteres da string de entrada de comprimento $k$ . Ele pode ser usado diretamente como o código hash ou uma função hash aplicada a ele para mapear o valor potencialmente grande para o tamanho da tabela hash. O valor de $a$ é geralmente um número primo pelo menos grande o suficiente para conter o número de caracteres diferentes no conjunto de caracteres de chaves potenciais. O hashing de conversão Radix de strings minimiza o número de colisões. Os tamanhos de dados disponíveis podem restringir o comprimento máximo da string que pode ser hash com este método. Por exemplo, uma palavra longa dupla de 128 bits hash apenas uma string alfabética de 26 caracteres (ignorando maiúsculas e minúsculas) com uma raiz de 29; uma string ASCII imprimível é limitada a 9 caracteres usando base 97 e uma palavra longa de 64 bits. No entanto, as chaves alfabéticas geralmente têm comprimento modesto, porque as chaves devem ser armazenadas na tabela de hash. As cadeias de caracteres numéricos geralmente não são um problema; 64 bits podem contar até $1019$ ou 19 dígitos decimais com raiz 10.

Rolling hash

Em algumas aplicações, como pesquisa de substring , pode-se calcular uma função hash $h$ para cada substring de $k-$ caracteres de uma determinada string de $n$ caracteres avançando uma janela de largura $k$ caracteres ao longo da string; onde $k$ é um número inteiro fixo e $n$ é maior que $k$ . A solução direta, que é extrair tal substring em cada posição de caractere no texto e calcular $h$ separadamente, requer um número de operações proporcionais a $k$ $\cdot$ $n$ . No entanto, com a escolha adequada de $h$ , pode-se usar a técnica de rolar hash para calcular todos esses hashes com um esforço proporcional a $mk$ $+$ $n,$ onde $m$ é o número de ocorrências da substring.

O algoritmo mais familiar deste tipo é Rabin-Karp com melhor e média performance de caso $O (n + mk)$ e pior caso $O (n \cdot k)$ (com toda a justiça, o pior caso aqui é gravemente patológico: tanto a string de texto quanto substring são compostas de um único caractere repetido, como $t$ = "AAAAAAAAAAA" e $s$ = "AAA"). A função hash usada para o algoritmo é geralmente a impressão digital Rabin , projetada para evitar colisões em cadeias de caracteres de 8 bits, mas outras funções hash adequadas também são usadas.

Análise

O pior resultado para uma função hash pode ser avaliado de duas maneiras: teórica e prática. O pior caso teórico é a probabilidade de que todas as chaves sejam mapeadas para um único slot. O pior caso prático é a sequência de teste mais longa esperada (função hash + método de resolução de colisão). Esta análise considera hashing uniforme, ou seja, qualquer chave será mapeada para qualquer slot particular com probabilidade $1 / m$ , característica das funções hash universais.

Enquanto Knuth se preocupa com o ataque adversário aos sistemas de tempo real, Gonnet mostrou que a probabilidade de tal caso é "ridiculamente pequena". Sua representação era que a probabilidade de $k$ de $n$ mapeamento de chaves para um único slot é onde $α$ é o fator de carga, $n$ $/$ $m$ . ${\ displaystyle {\ frac {e ^ {- \ alpha} \ alpha ^ {k}} {k!}}}$

História

O termo "hash" oferece uma analogia natural com seu significado não técnico ("cortar" ou "bagunçar" algo), dado como as funções de hash embaralham seus dados de entrada para derivar sua saída. Em sua pesquisa para a origem precisa do termo, Donald Knuth observa que, embora Hans Peter Luhn, da IBM pareça ter sido o primeiro a usar o conceito de função hash em um memorando datado de janeiro de 1953, o termo em si só apareceria em publicou literatura no final dos anos 1960, sobre os Princípios do Sistema de Computador Digital de Herbert Hellerman , embora já fosse um jargão muito difundido na época.

Veja também

Notas

Referências

links externos

Calcule o hash de um determinado valor por Timo Denk
The Goulburn Hashing Function ( PDF ) por Mayur Patel
Hash Function Construction for Textual and Geometrical Data Retrieval ( PDF ) Latest Trends on Computers, Vol.2, pp. 483–489, CSCC Conference, Corfu, 2010

Languages

In other projects