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

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

Lear asked 2019-09-11T11:47:55Z
9个解决方案
118 votes

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

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时一样好(不完全)。 一个小优点是两次使用相同的常数(它确实使我上次测试时的速度略快,不确定是否仍然如此)。

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

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

Thomas Mueller answered 2019-09-11T11:49:35Z
36 votes

Knuth的乘法方法:

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

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

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

Rafał Dowgird answered 2019-09-11T11:48:24Z
26 votes

取决于数据的分布方式。 对于一个简单的计数器,最简单的功能

f(i) = i

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

erikkallen answered 2019-09-11T11:50:06Z
7 votes

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

Tyler McHenry answered 2019-09-11T11:50:32Z
5 votes
  • 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位(良好分布)

  • 整数散列函数
bill answered 2019-09-11T11:51:18Z
3 votes

对Eternal Confuzzled的一些哈希算法有一个很好的概述。 我推荐Bob Jenkins的一次性哈希值,它可以快速达到雪崩,因此可用于高效的哈希表查找。

Christoph answered 2019-09-11T11:51:44Z
2 votes

答案取决于很多事情:

  • 您打算在哪里使用它?
  • 你想用哈希做什么?
  • 你需要一个密码安全的哈希函数吗?

我建议您看一下Merkle-Damgard系列哈希函数,如SHA-1等

dirkgently answered 2019-09-11T11:52:37Z
1 votes

我不认为我们可以在不事先知道您的数据的情况下说哈希函数是“好”的! 并且不知道你将如何处理它。

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

Ouanixi answered 2019-09-11T11:53:11Z
0 votes

对于随机哈希值,一些工程师说黄金比率素数(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. 将哈希值域映射到桶索引域; 也就是说,通过Logical And Operation with(hash_table_size - 1)将哈希值转换为bucket索引,如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;
}
Chen-ChungChia answered 2019-09-11T11:54:52Z
translate from https://stackoverflow.com:/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key