什么整数散列函数适合接受整数散列键?

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

这个神奇的数字是用一个 special multi-threaded test program MurmurHash ,并且几乎和使用时一样好(不是很好) AES . 一个微小的优势是,相同的常数被使用了两次(在我上次测试时,它确实使它稍微快了一点,不确定它是否仍然是这样)。

如果替换 0x45d9f3b 具有 0x119de1f3 (修订) multiplicative inverse

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

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 要保持不变,请替换 >> 具有 >>> 移除 未签名

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 项目,其中列出了其他(可能更好)常量。

克努特的乘法方法:

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

通常,您应该选择一个按哈希大小顺序排列的乘数( 2^32 在示例中)并且没有与之相关的公共因素。这样,哈希函数将统一覆盖所有哈希空间。

编辑:这个散列函数最大的缺点是它保留了可整除性,所以如果你的整数都可以被2或4整除(这并不少见),那么它们的散列也会被整除。这是哈希表中的一个问题-最终只能使用1/2或1/4个存储桶。

取决于数据的分布方式。对于简单计数器,最简单的函数

f(i) = i

将是好的(我怀疑是最优的,但我无法证明)。

• 非齐整数乘法
• 二元旋转
• 异或移位

要生成具有优异质量的哈希函数,请参见 PCG 用于生成随机数

事实上,这也是rrxmrrxmsx_0和杂音散列在有意或无意中使用的配方

我个人发现

uint64异或移位(常数uint64&n,整数i){
返回n^(n>>i);
}
uint64\u t散列(const uint64\u t&n){
uint64_t c=17316035218449499591ll;//随机不均匀整数常数;
返回c*xorshift(p*xorshift(n,32),32);

足够好

一个好的散列函数应该

1. 如果可能的话,对不松散的信息进行双射,并且冲突最少
2. 尽可能多且均匀地级联,即每个输入位应以0.5的概率翻转每个输出位

让我们首先看一下标识函数。它满足1。但不是2:

输入位n确定输出位n,其相关性为100%(红色),而没有其他相关性,因此它们为蓝色,给出了一条完美的红线

将这两者结合在一起会得到以下输出,仍然满足1。当两个双射函数的组合产生另一个双射函数时

第二次应用乘法和xorshift将产生以下结果:

uint64\u t const内联gfmul(const uint64\u t&i,const uint64\u&j){
__m128i{};I[0]^=I;
__m128im{};M[0]^=0xb000000000000000ull;
__m128i X=_mm_clmulepi64_si128(I,J,0);
__m128i A=_mm_clmulepi64_si128(X,M,0);
返回[0]^A[1]^B[1]^X[0]^X[1];
}


非齐整数乘法

异或移位

PCG用于生成随机数。

我个人发现
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:

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


"Knuth's multiplicative method")更好的方法是,以0.5的概率级联更强大,翻转更多的输出位,这是您想要的,绿色。它满足1。对于每个不均匀整数,都有一个乘法逆。



第二次应用乘法和xorshift将产生以下结果:

或者可以使用伽罗瓦场乘法,如GHash
   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];                                              
   }

• 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
  

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

• Integer Hash Function

This page 列出了一些简单的散列函数,这些函数通常都很正常,但是任何简单的散列函数都有一些病态的情况,在这些情况下,它不能很好地工作。

这里有一个很好的关于一些散列算法的概述 Eternally Confuzzled . 我推荐鲍勃·詹金斯(Bob Jenkins)的一次一个散列,它可以快速到达雪崩,因此可以用于高效的散列表查找。

答案取决于很多因素,如:

• 你打算在哪里使用它?
• 你打算怎么处理这个杂烩?
• 你需要一个加密的散列函数吗?

Merkle-Damgard 散列函数族,如SHA-1等

我认为在不事先知道数据的情况下,我们不能说散列函数是“好的”!而且不知道你要用它做什么。

对于未知的数据大小,有比哈希表更好的数据结构(我假设您在这里对哈希表进行哈希处理)。当我知道有“有限”数量的元素需要存储在有限的内存中时,我个人会使用哈希表。在开始考虑我的散列函数之前,我会尝试对我的数据做一个快速的统计分析,看看它是如何分布的等等。

对于随机散列值,一些工程师说黄金比例素数(2654435761)是一个糟糕的选择,根据我的测试结果,我发现它不是真的;相反,2654435761很好地分配了散列值。

#define MCR_HashTableSize 2^10

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

哈希表大小必须是2的幂。

我试过:

1. 总数据录入编号/总桶编号=2,3,4;其中,total_bucket_number=哈希表大小;
2. 将哈希值域映射到bucket索引域;也就是说,使用(hash_table_size-1)通过逻辑And运算将哈希值转换为bucket索引,如hash_UInt_GRPrimeNumber()所示;
5. 找出所有铲斗的最大碰撞次数;即最长链长;

根据我的测试结果,我发现黄金比率素数总是有更少的空桶或零空桶和最短的碰撞链长度。

一些整数的散列函数声称是好的,但测试结果表明,当total_data_entry/total_bucket_number=3时,最长链长度大于10(max collision number>10),很多bucket没有映射(空bucket),这是非常糟糕的,与黄金比率素数散列法计算空桶数为零、最长链长为3的结果进行了比较。

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

我一直在使用 splitmix64 answer )自从我找到这根线。然而,我最近偶然发现了佩尔·伊文森的 rrxmrrxmsx_0 ,它产生了比最初的3终结器及其后续版本更好的统计分布( 和其他混合物)。以下是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;
}

in-depth analysis 的最后一步中使用的64位混频器 MurmurHash3