Jenkins hash
2024-09-12 03:48:22
最早,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
最新文章
- 我心中的核心组件(可插拔的AOP)~第五回 消息组件
- foj 2044 1 M possible 二进制压缩
- redis的实现过程
- struts2文件异步上传
- 【转】warning C4819,该文件保存为 Unicode 格式以防止数据丢失,处理方法
- 让你彻底弄清offset
- java web 整合开发王者归来学习总结
- gogs windows
- java 内存调试 mat
- Android热更新技术——Tinker、nuwa、AndFix、Dexposed
- python-函数入门(二)
- python网页爬虫开发之二
- PowerDesigner使用(设置继承,实现)
- Ubuntu18.04中配置wxWidget3.0.4开发环境
- C#连接Oracle数据库的方法(Oracle.DataAccess.Client也叫ODP.net)
- python实战——网络爬虫之request
- js数组的比较
- 华为S5300系列交换机V100R005SPH008热补丁
- Cobbler实现自动化安装(上)--原理篇
- HDU3336 KMP+DP
热门文章
- Nginx的负载均衡 - 加权轮询 (Weighted Round Robin) 上篇
- Android View框架总结(八)ViewGroup事件分发机制
- android 填满手机磁盘空间方法
- Ruby开发入门
- Cocos2D中Node的userObject实例变量使用时一个要注意的地方
- Android之Gallery和Spinner-Android学习之旅(二十九)
- Android的ExpandableListView-android学习之旅(二十八)
- UNIX网络编程——TCP输出,UDP输出
- FFmpeg获取DirectShow设备数据(摄像头,录屏)
- (六十七)Xcode导入XMPPFramework框架