什么整数散列函数是好的,接受整数散列键？

Question

什么整数散列函数是好的,接受整数散列键？

Answer 1

我发现以下算法提供了非常好的统计分布.每个输入位以大约50%的概率影响每个输出位.没有碰撞(每个输入产生不同的输出).除非CPU没有内置的整数乘法单元,否则算法很快.C代码,假设int为32位(对于Java,替换>>为>>>和删除unsigned):

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

幻数是使用一个运行了几个小时的特殊多线程测试程序计算出来的,该程序计算雪崩效应(如果单个输入位发生变化,输出位数会发生变化;平均应该接近16),独立性输出位发生变化(输出位不应相互依赖),以及每个输出位发生变化的概率(如果有任何输入位发生变化).计算值优于MurmurHash使用的32位终结器,并且几乎与使用AES时一样好(不完全).一个小优点是两次使用相同的常数(它确实使我上次测试时的速度略快,不确定是否仍然如此).

如果替换0x45d9f3bwith 0x119de1f3(乘法逆),则可以反转该过程(从散列中获取输入值):

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

对于64位数字,我建议使用以下内容,即使它可能不是最快的.这个基于splitmix64,它似乎基于博客文章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;
}

对于Java,使用long,添加L到恒,更换>>与>>>和删除unsigned.在这种情况下,倒车更复杂:

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;
}

更新:您可能还想查看Hash Function Prospector项目,其中列出了其他(可能更好的)常量.

Answer 2

Knuth的乘法方法:

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

通常,您应该选择一个乘以您的散列大小(2^32在示例中)的乘数,并且没有与之相关的公因子.这样,哈希函数统一覆盖了所有哈希空间.

编辑:这个哈希函数的最大缺点是它保留了可分性,所以如果你的整数都可以被2或4整除(这并不罕见),它们的哈希也是如此.这是哈希表中的一个问题 - 您最终只能使用1/2或1/4的桶.

Answer 3

取决于您的数据如何分布.对于一个简单的计数器,最简单的功能

f(i) = i

会很好(我怀疑是最佳的,但我无法证明).

Answer 4

快速和良好的散列函数可以由质量较差的快速排列组合而成，例如

• 与一个奇数相乘
• 二元旋转
• 异或移位

产生具有优良品质的散列函数，就像用PCG演示的用于随机数生成一样。

这实际上也是 rrxmrrxmsx_0 和 murmur hash 正在使用的配方，有意或无意。

我个人发现

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);
}

要足够好。

一个好的散列函数应该

1. 如果可能的话，是双射的，不会丢失信息，并且冲突最少
2. 级联尽可能多且尽可能均匀，即每个输入位应该以 0.5 的概率翻转每个输出位。

我们先来看看恒等函数。它满足 1. 但不满足 2. ：

输入位 n 确定输出位 n 的相关性为 100%（红色），没有其他相关性，因此它们是蓝色的，给出了一条完美的红线。

xorshift(n,32) 也好不到哪里去，只产生一条半线。仍然满足 1.，因为它与第二个应用程序是可逆的。

与无符号整数的乘法（“Knuth 的乘法方法”）要好得多，级联更强烈，并以 0.5 的概率翻转更多输出位，这是您想要的，绿色。满足1。对于每个奇数，都有一个乘法逆。

将两者结合给出以下输出，仍然满足 1. 因为两个双射函数的组合产生另一个双射函数。

乘法和异或移位的第二次应用将产生以下结果：

或者您可以使用像GHash这样的伽罗瓦域乘法，它们在现代 CPU 上已经变得相当快，并且一步就具有卓越的品质。

   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];                                              
   }

Answer 5

这个页面列出了一些简单的散列函数,这些散列函数通常都很合适,但是任何简单的散列都有病态的情况,它不能正常工作.

Answer 6

• 32位乘法方法(非常快)请参阅@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
  

• 位于:MurmurHash的 32位和64位(良好分布)

• 整数散列函数

Answer 7

自从我发现这个线程以来，我一直在使用splitmix64（在 Thomas Mueller 的回答中指出）。然而，我最近偶然发现了 Pelle Evensen 的rrxmrrxmsx_0，它产生了比原始 MurmurHash3 终结器及其后继者（splitmix64和其他混合）更好的统计分布。下面是 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 还对最后一步中使用的 64 位混音器以及最新变体进行了深入分析。MurmurHash3