Qual function de hash de inteiros é boa que aceita uma chave de hash inteiro?

Qual function de hash de inteiros é boa que aceita uma chave de hash 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 seu tamanho de hash ( 2^32 no exemplo) e não tenha nenhum fator em comum com ele. Desta forma, a function hash cobre todo o seu espaço hash uniformemente.

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

Eu encontrei o seguinte algoritmo fornece uma distribuição estatística muito boa. Cada bit de input afeta cada bit de saída com cerca de 50% de probabilidade. Não há colisões (cada input resulta em uma saída diferente). O algoritmo é rápido, exceto se a CPU não tiver uma unidade de multiplicação de inteiros integrada. Código C, assumindo que int é 32 bit (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 especial multi-threaded , que calcula o efeito de avalanche (o número de bits de saída que mudam se um único bit de input é alterado; deve ser quase 16 em média), independência de alterações nos bits de saída (os bits de saída não devem depender um do outro) e a probabilidade de uma alteração em cada bit de saída se qualquer bit de input for alterado. Os valores calculados são melhores do que o finalizador de 32 bits usado pelo MurmurHash , e quase tão bom (não exatamente) quanto ao usar o AES . Uma ligeira vantagem é que a mesma constante é usada duas vezes (ela se tornou um pouco mais rápida na última vez que testei, não tenho certeza se ainda é o caso).

Você pode inverter o processo (obter o valor de input do hash) se replace o 0x45d9f3b por 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, eu sugiro usar o seguinte, até pensei que poderia não ser o mais rápido. Este é baseado no splitmix64 , que parece ser baseado no artigo do blog 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 querer olhar para o projeto Hash Function Prospector , onde outras constantes (possivelmente melhores) são listadas.

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

 f(i) = i 

vai ser bom (eu suspeito ótimo, mas eu não posso provar isso).

Esta página lista algumas funções hash simples que tendem a decentemente em geral, mas qualquer hash simples tem casos patológicos onde 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_SHIFT 
  • 32 bits e 64 bits (boa distribuição) em: MurmurHash

  • Função Hash Integer

Há uma boa visão geral sobre alguns algoritmos de hash no Eternally Confuzzled . Eu recomendaria o hash de um de cada vez, de Bob Jenkins, que rapidamente alcança uma avalanche e, portanto, pode ser usado para uma pesquisa eficiente na 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 function hash criptograficamente segura?

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

Eu não acho que podemos dizer que uma function hash é “boa” sem conhecer seus dados antecipadamente! 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 (suponho que você esteja fazendo o hash para uma tabela de hash aqui). Eu pessoalmente usaria uma tabela de hash quando eu sei que tenho um número “finito” de elementos que precisam ser armazenados em uma quantidade limitada de memory. 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 function hash.