整数哈希介绍
作者 斯人 | 发布于 2013 年 11 月 13 日
算法

为什么要整数哈希
 

很多时候,可以直接用整数作为键,比如QQ号码,手机号码,但这些号码的分布性不是均匀的(比如高位的变化更少,低位变化更多)。
分布均匀指的是每位为0或1的概率都是一样的。

理论基础

整数哈希的目标

1. 函数要是可逆的(1对1的映射)
2. 雪崩效应(输入中1bit的变化 影响 输出中1/4 到 1/2的bits变化)

可逆操作

key + const_value 加法是可逆
key – const_value 减法是可逆
key ^ const_value 异或是可逆的
~key 取反也是可逆的
key * const_value 乘以一个奇数也是可逆的

复杂操作的可逆性分析

a = (a+0xfd7046c5) + (a<<3);  // <<和+ 是可逆
a = (a+0xfd7046c5) + (a>>3);  // >>和+ 不保证是可逆的
a = (a^0xb55a4f09) ^ (a<<16); // ^ 和<< 是可逆
a = (a^0xb55a4f09) ^ (a>>16); // ^ 和>> 是可逆

 

雪崩操作

+ bit is 1 导致左边临近的所有1和最后一个0被反转( 0111 + 1 = 1000)
– bit is 1 导致左边临近的所有0和最后一个1被反转( 1000 – 1 = 0111)
所以加法和减法可以从低向高扩散变化

~ 可以把过多的0变1,把过多的1变成零,最后结合原始值,就可以保持0和1的平衡,以便 +或-可以有效扩散变化。

<< 让低位转到高位。
>> 让高位转到低位。

^ 会把某些位反转, 异或可以把两个变量的变化组合一起来,这经常跟移位一起来实现1个bit的变化扩散到2个bit上。

乘法的本质是 多个<< 和 +,也可以引起雪崩。 除法也可以影响雪崩(特别是素数)。
不用乘法和除法的原因的是,整数的乘法和除法太耗CPU了,整数除法是最慢的操作,比浮点数数除法还慢,在一些RISC机器上可能是上百倍的差距。

 

具体哈希算法介绍

乘法

《计算机编程艺术》中讲过: 乘以一个黄金分割数:2654435761(2^32) 可以得到 HASH.
hash = key*2654435761;
乘法的问题在于,低位可以影响高位,但高位不能影响低位。 分布是不均匀的。

 

但不是说乘法hash就没有用,在大量脚本语言中,对象的hash是通过对象的地址值来算hash的(因为对象本身会变化),
对象分配的特点决定了,地址的高位是不变化或变化极少。

uint32 address_hash(char* addr)
{
register uint32 key;
key = (uint32) addr;
return (key >> 3) * 2654435761; //这个3是对齐边界为8
}

这时候MASK, 应该选择高位更好(0xFFFF0000)

 

除法

   hash = key%prime

    除法的问题在于, 除数需要是素数,而且整数除法比较耗时。

如果除数不是素数,就要求hash值是均匀分布。

其实除法hash多是用在哈希表中求桶的位置,如果不能保证键的哈希函数是均匀的,那么建议使用素数来取模。

如果可以保证键值的哈希函数的质量,那么使用 MASK( &MASK)操作取代取模,效率会更高。

 

其它位运算

Tomas Wang

 

uint32_t hash32shift(uint32_t key)
{
key = ~key + (key << 15); // key = (key << 15) – key – 1;
key = key ^ (key >> 12);
key = key + (key << 2);
key = key ^ (key >> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >> 16);
return key;
}

Bob Jenkins’ 32 bit integer hash function

 

uint32_t hash( uint32_t a)
{
a = (a+0x7ed55d16) + (a<<12);
a = (a^0xc761c23c) ^ (a>>19);
a = (a+0x165667b1) + (a<<5);
a = (a+0xd3a2646c) ^ (a<<9);
a = (a+0xfd7046c5) + (a<<3); // <<和 +的组合是可逆的
   a = (a^0xb55a4f09) ^ (a>>16);
return a;
}

这六个数是随机数, 通过设置合理的6个数,你可以找到对应的perfect hash.

 

64 bit Mix Functions

 

uint64_t hash64shift(uint64_t key)
{
key = (~key) + (key << 21); // key = (key << 21) – key – 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
key = key + (key << 31);
return key;
}

64 bit to 32 bit Mix Functions

 

uint32_t hash64_32shift(uint64_t key)
{
key = (~key) + (key << 18); // key = (key << 18) – key – 1;
key = key ^ (key >> 31);
key = key * 21; // key = (key + (key << 2)) + (key << 4);
key = key ^ (key >> 11);
key = key + (key << 6);
key = key ^ (key >> 22);
return (int) key;
}

Bob Jenkins’ 96 bit Mix Function

 

uint32_t mix(uint32_t a, uint32_t b, uint32_t c)
{
a=a-b;  a=a-c;  a=a^(c >> 13);
b=b-c;  b=b-a;  b=b^(a << 8);
c=c-a;  c=c-b;  c=c^(b >> 13);
a=a-b;  a=a-c;  a=a^(c >> 12);
b=b-c;  b=b-a;  b=b^(a << 16);
c=c-a;  c=c-b;  c=c^(b >> 5);
a=a-b;  a=a-c;  a=a^(c >> 3);
b=b-c;  b=b-a;  b=b^(a << 10);
c=c-a;  c=c-b;  c=c^(b >> 15);
return c;
}

参考

http://www.concentric.net/~ttwang/tech/inthash.htm

原文出处:http://www.imsiren.com/archives/886