logo标签列表

哪些整数哈希函数适用于接受整数哈希键？

calgorithmhash
129

有哪些整数哈希函数接受一个整数哈希键且表现良好？

1
另请参阅https://dev59.com/V2nWa4cB1Zd3GeqPxyw0 - redcalx
1
为什么不说 hash(x) = x？ - theonlygusti
11个回答
212

我发现以下算法提供了非常好的统计分布。每个输入位对每个输出位的影响概率约为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位finalizer更好，几乎与使用AES时一样好（不完全相同）。稍微有点优势的是同一个常量被使用了两次（上次测试时确实使它稍微快了一些，不确定现在是否仍然是这样）。

如果你将 0x45d9f3b 替换为其乘法逆元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（混合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;
}

在这种情况下，反转更加复杂：
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;
}

以上内容适用于C语言。对于Java，请使用long，在常量后添加L，将>>替换为>>>并删除unsigned。
更新：您还可以查看Hash Function Prospector项目，其中列出了其他（可能更好的）常量。
7
不，这不是笔误，第二行进一步混合了比特。仅使用一个乘法并不是很好。 - Thomas Mueller
3
根据我编写的一个测试用例，我更改了魔数，因为值0x45d9f3b可以提供更好的混淆和扩散效果。特别是如果一个输出位发生变化，其他每个输出位都以大约相同的概率发生变化（如果输入位发生变化，则所有输出位也以相同的概率发生变化）。你是如何衡量0x3335b369对你更有效的？对你而言，int是32位的吗？ - Thomas Mueller
3
我正在寻找一个适用于64位无符号整数到32位无符号整数的好哈希函数。在这种情况下，上述魔术数字是否仍然相同？我将32位移位而不是16位。 - alessandro
3
我认为在这种情况下，更大的因子会更好，但您需要运行一些测试。或者（这是我做的）首先使用 x = ((x >> 32) ^ x)，然后再使用上面的32位乘法。我不确定哪个更好。您可能还想查看Murmur3的64位终结器。 - Thomas Mueller
2
@SantoshGhimire 是的，在这种情况下，可以反转操作，因为没有碰撞。您只需要在公式中将 0x45d9f3b 替换为其倒数值 0x119de1f3 即可。 - Thomas Mueller
显示剩余41条评论
54

Knuth的乘法哈希方法：

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

一般来说，你应该选择一个乘数，其值与您的哈希大小（在此示例中为2^32）同阶，并且与其没有公共因数。这样，哈希函数可以均匀地覆盖整个哈希空间。

编辑：这个哈希函数最大的缺点是保留了可除性，因此如果您的整数都能被2或4整除（这种情况很常见），那么它们的哈希也会被整除。这在哈希表中会导致问题-你可能只使用了1/2或1/4的桶。

46
虽然与一个著名的名称相关联，但这是一个非常糟糕的哈希函数。 - Seun Osewa
6
如果选择素数表大小，这个哈希函数并不差。此外，它适用于“闭合哈希”。如果哈希值不均匀分布，乘法哈希可确保来自一个值的冲突不太可能“干扰”具有其他哈希值的元素。 - Paolo Bonzini
14
对于那些好奇的人，这个常数被选择为哈希表大小（2^32）除以黄金分割率。 - awdz9nld
8
Paolo: Knuth的方法在某种意义上是“不好”的，因为它不能对高位产生雪崩效应。 - awdz9nld
13
经过仔细检查，发现 2654435761 实际上是一个质数。因此，这可能就是为什么选择它而不是 2654435769 的原因。 - karadoc
显示剩余21条评论
32

取决于你的数据分布方式。对于一个简单的计数器，最简单的函数

f(i) = i

会不错（我觉得可能是最优的，但我无法证明）。

3
问题在于，通常存在一些能被一个公因数整除的大量整数集合（例如，字对齐的内存地址等）。如果你的哈希表恰好也能被这个公因数整除，那么就会导致只有一半（或四分之一、八分之一等）的桶被使用。 - Rafał Dowgird
10
这就是为什么回复中会说“对于一个简单的计数器”和“这取决于你的数据分布”的原因。 - erikkallen
6
这实际上是Sun在java.lang.Integer中实现的hashCode()方法。http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/Integer.java#Integer.hashCode%28%29 - Juande Carrion
5
这是误导性的，因为使用的不是那个哈希值。在转换为使用二次幂表大小后，Java会重新计算来自.hashCode()的每个哈希值，参见这里。 - Esailija
8
在许多实际应用中，由于恒等函数的分布特性（或其缺乏分布特性），它作为哈希函数相当无用，除非需要具有局部性属性。请注意，本句中的“locality”指的是数据区块在物理存储空间上的相对位置关系。 - awdz9nld
显示剩余2条评论
25

快速且良好的哈希函数可以由具有较低质量的快速置换组成，例如

  • 与奇数整数相乘
  • 二进制旋转
  • xorshift

为了产生具有优越品质的哈希函数，就像PCG用于随机数生成一样。

实际上，这也是rrxmrrxmsx_0和murmur哈希使用的配方，无论是有意还是无意地。

我个人发现

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. ：

identity function

输入的第n位决定输出的第n位，与其他位没有关联（蓝色），因此形成了完美的红线（相关性为100%）。

xorshift(n,32)并不比前者更好，只能得到一条半的线。但仍满足1.，因为可以通过再次应用来进行反演。

xorshift

使用无符号整数进行乘法运算（"Knuth's multiplicative method"）更好，级联效果更强，并以0.5的概率翻转更多输出位，这正是您想要的，在绿色方面。它满足以下条件：对于每个奇数，都存在一个乘法逆元素。

knuth

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

knuth•xorshift

再次使用乘法和xorshift将产生以下结果：

proposed hash

或者你可以使用伽罗瓦域乘法，例如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];                                              
   }
1
gfmul: 该代码似乎是伪代码，因为据我所知，您不能在__m128i中使用括号。但仍然非常有趣。第一行似乎是说“取一个未初始化的__m128i（I）并将其与（参数）i异或。 我应该理解为用0初始化I并将其与i异或吗？ 如果是这样，那么将I加载到i并对I执行not操作是否相同？ - Jan
@Jan 我想要做的是 __m128i I = i; //set the lower 64 bits，但我不能这样做，所以我使用了 ^=。0^1 = 1，因此没有不涉及。关于使用 {} 进行初始化，我的编译器从未抱怨过，这可能不是最好的解决方案，但我想要的是将其全部初始化为 0，以便我可以执行 ^= 或 |=。我认为我基于 这篇博客文章 编写了该代码，该博客文章还提供了反演，非常有用 :D - Wolfgang Brehm
1
哈希函数为什么需要可逆性？ - Violet Giraffe
2
如果哈希不是双射的，那么输出分布就不能是均匀的。如果哈希是双射的，那么它会尽可能地使用输出空间。这就是为什么建议哈希是双射的，使其可逆，但只忽略计算可行性。 - Wolfgang Brehm
1
@VioletGiraffe 如果哈希是双射的，原则上它是可逆的。这并不意味着在计算上很容易反转它。只有非常特定的应用需要哈希易于反转。加密应用需要哈希难以反转。您可以拥有一个双射哈希，它很难被反转（如果您想要一个，请告诉我如何联系您，此评论太短）。而且您可以拥有一个非双射哈希，它很容易被反转，但存在歧义。 - Wolfgang Brehm
1
我明白了，谢谢。我现在认为我理解了为什么哈希函数双射是可取的（无论它是否在实践中可逆）。 - Violet Giraffe
7

  • 32-bits multiplicative method (very fast) see @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 and 64-bits (good distribution) at : MurmurHash

  • Integer Hash Function
7

这个页面列出了一些简单的哈希函数，通常表现良好，但任何简单的哈希都有病态情况，它不能很好地工作。

5

自从我发现Thomas Mueller在这个答案中提到的splitmix64，我一直在使用它。然而，最近我偶然发现了Pelle Evensen的rrxmrrxmsx_0，它比原始的MurmurHash3 finalizer及其后继者（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 还提供了一个关于 MurmurHash3 最后一步使用的 64 位混合器和最近变体的深入分析, 可以在这里查看。

3
此函数不是双射函数。对于所有$v=ror（v，25）$的值，即所有0和1的值，在两个位置上会产生相同的输出。对于所有$v=ror64（v，24）^ ror64（v,49）$的值，这些值至少多2且与$v=ror（v，28）$相同，从而产生另外 $2^4$ 个冲突，总共约有22个不必要的碰撞。使用两次SplitMix可能同样好，同样快，但仍可逆且无冲突。 - Wolfgang Brehm
3

在Eternally Confuzzled网站上有一些哈希算法的概述。我推荐Bob Jenkins的单次哈希，它可以快速达到雪崩效应，因此可用于高效的哈希表查找。

4
这是一篇不错的文章，但它专注于哈希字符串密钥，而不是整数。 - Adrian Mouat
1
只是为了明确，虽然文章中的方法适用于整数（或可以进行调整），但我认为对于整数来说有更有效的算法。 - Adrian Mouat
3
对于随机哈希值，一些工程师表示黄金比例质数（2654435761）是一个糟糕的选择。但是，通过我的测试结果，我发现这不是真的。相反，2654435761可以很好地分布哈希值。
#define MCR_HashTableSize 2^10

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

哈希表的大小必须是2的幂次方。
我编写了一个测试程序来评估许多整数哈希函数，结果显示GRPrimeNumber是一个相当不错的选择。
我尝试过：
1. total_data_entry_number / total_bucket_number = 2, 3, 4；其中total_bucket_number = 哈希表大小； 2. 将哈希值域映射到桶索引域；也就是通过逻辑与操作(hash_table_size - 1)将哈希值转换为桶索引，如Hash_UInt_GRPrimeNumber()所示； 3. 计算每个桶的冲突数； 4. 记录未映射的桶，即空桶； 5. 找出所有桶中的最大冲突数；也就是最长的链长度；
通过我的测试结果，我发现黄金比例质数总是具有更少的空桶或零空桶和最短的冲突链长度。
一些整数哈希函数被认为很好，但测试结果显示，当total_data_entry/total_bucket_number=3时，最长的链长度大于10（最大冲突数>10），而且有很多未映射的桶（空桶），这非常糟糕，与使用黄金比例质数哈希法的零空桶和最长链长度3的结果相比。
顺便说一下，通过我的测试结果，我发现一种移位异或哈希函数的版本非常好（由mikera共享）。
unsigned int Hash_UInt_M3(unsigned int key)
{
  key ^= (key << 13);
  key ^= (key >> 17);    
  key ^= (key << 5); 
  return key;
}
2
但是为什么不将产品向右移动，这样您就可以保留最混合的位？这就是它应该工作的方式。 - harold
1
@哈罗德，黄金比例素数是经过精心选择的，虽然我认为这不会有任何区别，但我将测试以查看是否使用“最混合的位”更好。我的观点是，“选择不好”并不正确，因为测试结果表明，仅获取位的较低部分就足够好，并且比许多哈希函数更好。 - Chen-ChungChia
（2654435761，4295203489）是质数的黄金比例。 - Chen-ChungChia
（1640565991，2654435761）也是质数的黄金比例。 - Chen-ChungChia
@harold，将产品向右移动会变得更糟，即使只是向右移动1个位置（除以2），它仍然变得更糟（虽然仍然有零空桶，但最长链长度更大）；向右移动更多的位置，结果会变得更糟。为什么？我认为原因是：将产品向右移动会使更多的哈希值不互质，这只是我的猜测，真正的原因涉及数论。 - Chen-ChungChia
@Chen-ChungChia 我认为这是因为低位保留了双射性，如果所有值都小于MCR_HashTableSize，它将不会产生任何冲突。 - Wolfgang Brehm
1

我认为在不事先了解数据和使用情况的情况下，无法说一个哈希函数是“好”的。对于未知的数据大小，有比哈希表更好的数据结构（假设你正在为哈希表做哈希）。个人而言，当我知道需要在有限的内存中存储“有限”的元素时，我会使用哈希表。在开始考虑哈希函数之前，我会尝试对我的数据进行快速的统计分析，看看数据如何分布等。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接