什么整数散列函数可以接受整数散列键？

什么整数散列函数可以接受整数散列键？

160539 次浏览
小开

取决于您的数据是如何分布的。对于一个简单的计数器，最简单的函数

f(i) = i

将是好的(我怀疑是最佳的，但我不能证明它)。

小开

这个页面 列出了一些简单的散列函数，这些函数通常都很好，但是任何简单的散列都会出现病态情况，不能很好地工作。

小开

答案取决于很多因素，比如:

  • 你打算在哪里使用它？
  • 你拿这些大麻做什么？
  • 你需要一个密码安全散列函数吗？

我建议您研究一下 Merkle-Damgard系列散列函数，如 SHA-1等

小开

在 永远的困惑上有一个关于一些散列算法的很好的概述。我建议使用 Bob Jenkins 的一次一个散列(one-at-a-time hash) ，这种散列很快就会崩溃，因此可以用于高效的散列表查找。

小开
最佳答案

Knuth 的乘法方法:

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

一般来说，您应该选择一个乘数，它的顺序是您的散列大小(例子中的 2^32) ，并且与它没有公共因子。这样散列函数可以统一地覆盖所有的散列空间。

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

小开

  • 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-bits and 64-bits (good distribution) at : MurmurHash

  • Integer Hash Function
小开

我发现下面的算法提供了很好的统计分布。每个输入位以大约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时一样好(不完全一样)。一个小小的优势是同一个常量被使用了两次(在我上次测试的时候，它确实使得速度稍微快了一些，但不确定是否仍然如此)。

如果将 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位数字，我建议使用以下方法，即使它可能不是最快的。这篇文章基于 分裂混合64，它似乎基于博客文章 更好的比特混合(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;
}

更新: 您可能还想查看 散列函数探测器项目，其中列出了其他(可能更好的)常量。

小开

I don't think we can say that a hash function is "good" without knowing your data in advance ! and without knowing what you're going to do with it.

There are better data structures than hash tables for unknown data sizes (I'm assuming you're doing the hashing for a hash table here ). I would personally use a hash table when I Know I have a "finite" number of elements that are needing stored in a limited amount of memory. I would try and do a quick statistical analysis on my data, see how it is distributed etc before I start thinking about my hash function.

小开

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

#define MCR_HashTableSize 2^10


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

散列表的大小必须是2的幂次方。

I have written a test program to evaluate many hash functions for integers, the results show that GRPrimeNumber is a pretty good choice.

我试过了:

  1. Total _ data _ entry _ number/total _ bucket _ number = 2,3,4; 其中 total _ bucket _ number = hash 表大小;
  2. 映射哈希值域到桶索引域; 也就是说，使用(Hash _ table _ size-1)通过 Logical And Operation 将哈希值转换为桶索引，如 Hash _ UInt _ GRPrimeNumber ()所示;
  3. 计算每个桶的碰撞次数;
  4. 记录未映射的桶，即一个空桶;
  5. 求出所有桶的最大碰撞次数，即最长链长;

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

一些整数散列函数被认为是良好的，但测试结果表明，当 total _ data _ entry/total _ bucket _ Number = 3时，最长链长大于10(最大碰撞数 > 10) ，并且许多桶没有映射(空桶) ，这与黄金比率素数散列得到的零空桶和最长链长3的结果相比非常糟糕。

顺便说一下，根据我的测试结果，我发现 shift-xor 散列函数的一个版本非常好(它是由 mikera 共享的)。

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

我一直在使用 splitmix64(指在托马斯穆勒的 answer) ，因为我发现了这个线程。然而，我最近偶然发现了 Pelle Evensen 的 Rrxmrxmsx _ 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 还提供了用于 MurmurHash3最后一步的64位混频器的 深入分析以及最近的变体。

小开

快速和良好的哈希函数可以由具有较少质量的快速排列组成，如

  • 非均匀整数乘法
  • binary rotations
  • Xorshift

产生一个具有优良品质的散列函数，如用 PCG演示的随机数生成。

事实上，这也是 rrxmrrxmsx _ 0和 mutur 散列(有意或无意地)正在使用的配方。

我个人发现

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

Input bit n determines output bit n with a correlation of 100% (red) and no others, they are therefore blue, giving a perfect red line across.

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

xorshift

使用无符号整数("Knuth's multiplicative method")的乘法要好得多，级联更强，并以0.5的概率翻转更多的输出位，这正是您想要的，绿色。满足1。每个不均匀整数都有一个倒数。

knuth

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

knuth•xorshift

A second application of multiplication and xorshift will yield the following:

proposed hash

或者您可以使用像 GHash这样的 Galois 字段乘法，它们在现代 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];
}

提交答案