最早,Bob Jenkins提出了多個基于字元串通用Hash算法(搜Jenkins Hash就知道了),而Thomas Wang在Jenkins的基礎上,針對固定整數輸入做了相應的Hash算法。其64位版本的 Hash算法如下:
uint64_t hash(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;
}
其關鍵特性是:
1.雪崩性(更改輸入參數的任何一位,就将引起輸出有一半以上的位發生變化)
2.可逆性
其逆Hash函數為:
uint64_t inverse_hash(uint64_t key) {
uint64_t tmp;
// Invert key = key + (key << 31)
tmp = key-(key<<31);
key = key-(tmp<<31);
// Invert key = key ^ (key >> 28)
tmp = key^key>>28;
key = key^tmp>>28;
// Invert key *= 21
key *= 14933078535860113213u;
// Invert key = key ^ (key >> 14)
tmp = key^key>>14;
tmp = key^tmp>>14;
tmp = key^tmp>>14;
key = key^tmp>>14;
// Invert key *= 265
key *= 15244667743933553977u;
// Invert key = key ^ (key >> 24)
tmp = key^key>>24;
key = key^tmp>>24;
// Invert key = (~key) + (key << 21)
tmp = ~key;
tmp = ~(key-(tmp<<21));
tmp = ~(key-(tmp<<21));
key = ~(key-(tmp<<21));
return key;
}
由上述的算法實作可知,原始的hash算法過程是非常快的,而其逆Hash算法則比較慢一些。
特征:0.
參考:
1.jenkins 32位Hash算法:http://burtleburtle.net/bob/hash/integer.html
2.Geoffrey Irving's blog: http://naml.us/blog/tag/thomas-wang