Quais funções de hash de inteiro são boas para aceitar uma chave de hash de inteiro?

Quais funções de hash de inteiro são boas para aceitar uma chave de hash de inteiro?

Método multiplicativo de Knuth:

hash(i)=i*2654435761 mod 2^32

Em geral, você deve escolher um multiplicador que esteja na ordem do tamanho do hash ( 2^32no exemplo) e não tenha fatores em comum com ele. Dessa forma, a função hash cobre todo o seu espaço hash uniformemente.

Edit: A maior desvantagem desta função hash é que ela preserva a divisibilidade, então se seus inteiros forem todos divisíveis por 2 ou por 4 (o que não é incomum), seus hashes também serão. Este é um problema nas tabelas hash - você pode acabar com apenas 1/2 ou 1/4 dos baldes sendo usados.

Descobri que o algoritmo a seguir fornece uma distribuição estatística muito boa. Cada bit de entrada afeta cada bit de saída com cerca de 50% de probabilidade. Não há colisões (cada entrada resulta em uma saída diferente). O algoritmo é rápido, exceto se a CPU não tiver uma unidade de multiplicação de inteiros embutida. Código C, supondo que intseja de 32 bits (para Java, substitua >>por >>>e remova unsigned):

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

O número mágico foi calculado usando um programa de teste multi-thread especial executado por muitas horas, que calcula o efeito da avalanche (o número de bits de saída que mudam se um único bit de entrada é alterado; deve ser quase 16 em média), independência de mudanças de bit de saída (os bits de saída não devem depender uns dos outros) e a probabilidade de uma mudança em cada bit de saída se algum bit de entrada for alterado. Os valores calculados são melhores do que o finalizador de 32 bits usado por MurmurHash e quase tão bons (não muito) quanto ao usar AES . Uma pequena vantagem é que a mesma constante é usada duas vezes (ela a tornou um pouco mais rápida na última vez que testei, não tenho certeza se ainda é o caso).

Você pode reverter o processo (obter o valor de entrada do hash) se substituir o 0x45d9f3bpor 0x119de1f3(o inverso multiplicativo ):

unsigned int unhash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

Para números de 64 bits, sugiro usar o seguinte, mesmo que não seja o mais rápido. Este é baseado em splitmix64 , que parece ser baseado no artigo Better Bit Mixing (mix 13).

uint64_t hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

Para Java, use long, adicione Là constante, substitua >>por >>>e remova unsigned. Nesse caso, a reversão é mais complicada:

uint64_t unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

Atualização: você também pode dar uma olhada no projeto Hash Function Prospector , onde outras (possivelmente melhores) constantes são listadas.

Depende de como seus dados são distribuídos. Para um contador simples, a função mais simples

f(i) = i

será bom (suspeito que seja ótimo, mas não posso provar).

As funções hash rápidas e boas podem ser compostas de permutações rápidas com qualidades menores, como

• multiplicação com um inteiro ímpar
• rotações binárias
• xorshift

Para produzir uma função de hashing com qualidades superiores, como demonstrado com PCG para geração de números aleatórios.

Esta é, de fato, também a receita que rrxmrrxmsx_0 e murmur hash estão usando, consciente ou inconscientemente.

Eu pessoalmente encontrei

uint64_t xorshift(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}

para ser bom o suficiente.

Uma boa função hash deve

1. seja bijetivo para não perder informações, se possível e tenha o mínimo de colisões
2. cascatear tanto quanto possível, ou seja, cada bit de entrada deve inverter cada bit de saída com probabilidade 0,5.

Vejamos primeiro a função de identidade. Satisfaz 1. mas não 2.:

O bit de entrada n determina o bit de saída n com uma correlação de 100% (vermelho) e nenhum outro, eles são, portanto, azuis, fornecendo uma linha vermelha perfeita.

Um xorshift (n, 32) não é muito melhor, produzindo uma linha e meia. Ainda satisfaz 1., porque é invertível com uma segunda aplicação.

Uma multiplicação com um inteiro sem sinal é muito melhor, em cascata com mais força e lançando mais bits de saída com uma probabilidade de 0,5, que é o que você deseja, em verde. Ele satisfaz 1. já que para cada número inteiro ímpar há um inverso multiplicativo.

Combinar os dois dá a seguinte saída, ainda satisfazendo 1. como a composição de duas funções bijetivas produz outra função bijetivo.

Uma segunda aplicação de multiplicação e xorshift resultará no seguinte:

Ou você pode usar multiplicações de campo de Galois como GHash , eles se tornaram razoavelmente rápidos em CPUs modernas e têm qualidades superiores em uma única etapa.

   uint64_t const inline gfmul(const uint64_t& i,const uint64_t& j){           
     __m128i I{};I[0]^=i;                                                          
     __m128i J{};J[0]^=j;                                                          
     __m128i M{};M[0]^=0xb000000000000000ull;                                      
     __m128i X = _mm_clmulepi64_si128(I,J,0);                                      
     __m128i A = _mm_clmulepi64_si128(X,M,0);                                      
     __m128i B = _mm_clmulepi64_si128(A,M,0);                                      
     return A[0]^A[1]^B[1]^X[0]^X[1];                                              
   }

Esta página lista algumas funções hash simples que tendem a funcionar decentemente em geral, mas qualquer hash simples tem casos patológicos em que não funciona bem.

• Método multiplicativo de 32 bits (muito rápido) veja @rafal

  #define hash32(x) ((x)*2654435761)
  #define H_BITS 24 // Hashtable size
  #define H_SHIFT (32-H_BITS)
  unsigned hashtab[1<<H_BITS]  
  .... 
  unsigned slot = hash32(x) >> H_SHIFT

• 32 bits e 64 bits (boa distribuição) em: MurmurHash

• Função Hash Inteiro

Há uma boa visão geral de alguns algoritmos de hash em Eternally Confuzzled . Eu recomendaria o hash um por vez de Bob Jenkins, que rapidamente atinge uma avalanche e, portanto, pode ser usado para pesquisa eficiente de tabela de hash.

A resposta depende de muitas coisas como:

• Onde você pretende empregá-lo?
• O que você está tentando fazer com o hash?
• Você precisa de uma função hash criptograficamente segura?

Eu sugiro que você dê uma olhada na família Merkle-Damgard de funções hash como SHA-1 etc.

Não acho que possamos dizer que uma função hash é "boa" sem saber seus dados com antecedência! e sem saber o que você vai fazer com isso.

Existem estruturas de dados melhores do que tabelas de hash para tamanhos de dados desconhecidos (presumo que você esteja fazendo o hash de uma tabela de hash aqui). Eu pessoalmente usaria uma tabela hash quando sei que tenho um número "finito" de elementos que precisam ser armazenados em uma quantidade limitada de memória. Eu tentaria fazer uma análise estatística rápida dos meus dados, ver como eles são distribuídos etc. antes de começar a pensar na minha função hash.

Para valores de hash aleatórios, alguns engenheiros disseram que o número primo de proporção dourada (2654435761) é uma escolha ruim. Com os resultados dos meus testes, descobri que não é verdade; em vez disso, 2654435761 distribui os valores de hash muito bem.

#define MCR_HashTableSize 2^10

unsigned int
Hash_UInt_GRPrimeNumber(unsigned int key)
{
  key = key*2654435761 & (MCR_HashTableSize - 1)
  return key;
}

O tamanho da tabela hash deve ser uma potência de dois.

Eu escrevi um programa de teste para avaliar muitas funções hash para inteiros, os resultados mostram que GRPrimeNumber é uma escolha muito boa.

Eu tentei:

1. total_data_entry_number / total_bucket_number = 2, 3, 4; onde total_bucket_number = tamanho da tabela hash;
2. mapear o domínio do valor hash para o domínio do índice do bucket; isto é, converta o valor do hash em índice de depósito por Lógico e Operação com (hash_table_size - 1), conforme mostrado em Hash_UInt_GRPrimeNumber ();
3. calcular o número de colisão de cada balde;
4. registrar o balde que não foi mapeado, ou seja, um balde vazio;
5. descobrir o número máximo de colisão de todos os baldes; ou seja, o comprimento de corrente mais longo;

Com os resultados dos meus testes, descobri que o Golden Ratio Prime Number sempre tem menos baldes vazios ou balde vazio zero e o menor comprimento da cadeia de colisão.

Algumas funções hash para inteiros são consideradas boas, mas os resultados do teste mostram que quando total_data_entry / total_bucket_number = 3, o comprimento da cadeia mais longa é maior que 10 (número máximo de colisão> 10) e muitos baldes não são mapeados (baldes vazios ), o que é muito ruim, em comparação com o resultado de zero balde vazio e comprimento de corrente mais longo 3 por Hashing de número principal de Golden Ratio.

BTW, com os resultados dos meus testes, descobri que uma versão das funções shifting-xor hash é muito boa (é compartilhada pela mikera).

unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}

Tenho usado splitmix64(apontado na resposta de Thomas Mueller ) desde que encontrei este tópico. No entanto, recentemente me deparei com rrxmrrxmsx_0 de Pelle Evensen , que rendeu uma distribuição estatística tremendamente melhor do que o finalizador MurmurHash3 original e seus sucessores ( splitmix64e outras combinações). Aqui está o snippet de código em C:

#include <stdint.h>

static inline uint64_t ror64(uint64_t v, int r) {
    return (v >> r) | (v << (64 - r));
}

uint64_t rrxmrrxmsx_0(uint64_t v) {
    v ^= ror64(v, 25) ^ ror64(v, 50);
    v *= 0xA24BAED4963EE407UL;
    v ^= ror64(v, 24) ^ ror64(v, 49);
    v *= 0x9FB21C651E98DF25UL;
    return v ^ v >> 28;
}

Pelle também fornece uma análise aprofundada do mixer de 64 bits usado na etapa final MurmurHash3e nas variantes mais recentes.