FNV哈希算法(转)
由来:FNV哈希算法全名为Fowler-Noll-Vo算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出。
特点和用途:FNV能快速hash大量数据并保持较小的冲突率,它的高度分散使它适用于hash一些非常相近的字符串,比如URL,hostname,文件名,text,IP地址等。
算法版本:FNV算法有两个版本FNV-1和FNV-1a
算法描述:
相关变量:
hash值:一个n位的unsigned int型hash值
offset_basis:初始的哈希值
FNV_prime:FNV用于散列的质数
octet_of_data:8位数据(即一个字节)
FNV-1描述:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash * FNV_prime
hash = hash xor octet_of_data
return hash
FNV-1a描述:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash xor octet_of_data
hash = hash * FNV_prime
return hash
FNV-1a和FNV-1的唯一区别就是xor和multiply的顺序不同,他们所采用的FNV_prime和offset_basis都相同,有人认为FNV-1a在进行小数据(小于4个字节)哈希时有更好的性能。
FNV_prime的取值:
32 bit FNV_prime = 2^24 + 2^8 + 0x93 = 16777619
64 bit FNV_prime = 2^40 + 2^8 + 0xb3 = 1099511628211
128 bit FNV_prime = 2^88 + 2^8 + 0x3b = 309485009821345068724781371
256 bit FNV_prime = 2^168 + 2^8 + 0x63 =374144419156711147060143317175368453031918731002211
512 bit FNV_prime = 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575
126094039892345713852759
1024 bit FNV_prime = 2^680 + 2^8 + 0x8d =
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573
offset_basis的取值:
32 bit offset_basis = 2166136261
64 bit offset_basis = 14695981039346656037
128 bit offset_basis = 144066263297769815596495629667062367629
256 bit offset_basis = 100029257958052580907070968620625704837092796014241193945225284501741471925557
512 bit offset_basis = 96593031294966694980094354007163104660904187456726378961083743294344626579945829
32197716438449813051892206539805784495328239340083876191928701583869517785
1024 bit offset_basis = 14197795064947621068722070641403218320880622795441933960878474914617582723252296
73230371772215086409652120235554936562817466910857181476047101507614802975596980
40773201576924585630032153049571501574036444603635505054127112859663616102678680
82893823963790439336411086884584107735010676915
算法实现:
//sheepdog中64位FNV-1a算法的实现
/*
* 64 bit FNV-1a non-zero initial basis
*/
#define FNV1A_64_INIT ((uint64_t) 0xcbf29ce484222325ULL)
/*
* 64 bit Fowler/Noll/Vo FNV-1a hash code
*/
// 调用时,hval的参数值为FNV1A_64_INT,即算法描述中的offset_basis
static inline uint64_t fnv_64a_buf(void *buf, size_t len, uint64_t hval)
{
unsigned char *bp = (unsigned char *) buf;
unsigned char *be = bp + len;
while (bp < be) {
hval ^= (uint64_t) *bp++;
hval += (hval << ) + (hval << ) + (hval << ) +
(hval << ) + (hval << ) + (hval << );
}
return hval;
}
参考文献:点击打开链接(包含详细讲解和代码) 转自:https://blog.csdn.net/TCCaiWQ/article/details/7319739
最新文章
- [2014.01.27]wfPrintOcx 票据打印控件 v5.3
- 求第N个素数
- URAL 1077 Travelling Tours(统计无向图中环的数目)
- css笔记07:通配符选择器
- EasyUI Layout Full - Not Correct in IE8
- C# - 系统类 - DateTime类
- Windows下安装Emacs+Sbcl+Slime
- .net framework3.0 以上版本开发的软件乱码问题
- SQL SERVER统计服务器所有的数据库(数据库文件)、表(表行数)、字段(各字段)等详细信息
- RCP:如何把Preferences中的项从一个类别移动到另一个类别 2013-08-23 18:59 by Binhua Liu,
- C#隐藏(new)方法和重写(override)方法
- Linux系列教程(十六)——Linux权限管理之ACL权限
- Android二维码扫描、生成
- JavaScript一看就懂(2)闭包
- [tkinter]为列表框添加滚动条
- 微信小程序day01-JSON配置
- Write your own operating system Day(1)
- 4.django学习模板
- windows系统下将nginx作为系统服务启动
- MongoDB的Invalid credentials for database
热门文章
- mysql 查询当天数据
- 连接mysql报";ERROR 1130: Host xxx.xxx.xxx.xxx is not allowed to connect to this MySQL server";
- Linux系统禁止root账号远程登录
- docker指定固定IP创建容器
- 4.LVS的三种工作模式_DR模式
- CentOS7 编译安装MySQL5.6.38(一)
- 从SQLAlchemy的“缓存”问题说起
- 纯数据结构Java实现(8/11)(Trie)
- dfs 全排列 使用交换——含重复元素和非重复元素
- js 正则表达式 贪婪与惰性