Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1071487
  • 博文数量: 646
  • 博客积分: 288
  • 博客等级: 二等列兵
  • 技术积分: 5375
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-08 14:33
个人简介

为了技术,我不会停下学习的脚步,我相信我还能走二十年。

文章分类

全部博文(646)

文章存档

2014年(8)

2013年(134)

2012年(504)

分类: C/C++

2012-10-03 18:53:47

FNV哈希算法

  FNV哈希函数,有三种FNV-0(已废弃),FNV-1, FNV-1a。

  FNV-1和FNV-1a算法对于最终生成的哈希值(hash)有一定限制

  1,hash是无符号整型

  2,hash的位数(bits),应该是2的n次方(32,64,128,256,512,1024),一般32位的就够用了。

  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-1a代替FNV-1发现算法离散性或CPU利用效率更好(我感觉应该没什么太大差距,只是微小的)。

for each octet_of_data to be hashed 意思是对于你要算哈希值的数,它的每一个字节。

hash = hash * FNV_prime,是包含取模运算的,具体看你采用多少位的哈希函数。例如,你用32为哈希,hash = hash * FNV_prime % (2的32次方);

hash = hash xor octet_of_data,意思是把当前取来的字节和当前的hash值的第八位做抑或运算。

32 bit FNV_prime = 224 + 28 + 0x93 = 16777619

64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211

128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371

256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211

512 bit FNV_prime = 2344 + 28 + 0x57 = 
35835915874844867368919076489095108449946327955754392558399825615420669938882575
126094039892345713852759

1024 bit FNV_prime = 2680 + 28 + 0x8d = 
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573

  以上这几个数都是质数(哈希的理论基石,质数分辨定理,我理解也不深),不用管为什么,用的时候照搬就是了。

  

 如果我想得到的哈希位数不是上面几种呢?

  比如我想得到24位的哈希值,方法:取上面比24大的最小的位数,当然是32了,先算对应32位哈希值,再转换成24位的。

  转换方法:32 - 24 = 8, 好了把得到的32砍成两段,高8位最和低24位。第8位与低24位中的低8位做抑或,得到的24位值是最终结果。(hash>>24) ^ (hash & 0xFFFFFF);
 如果我想得到的哈希值不能用位数来表示呢?

  比如想得到范围在0~9999的哈希值,方法:取上面比9999大的最小的位数,当然是32,先算对应32位哈希值,再mod(9999 +1)。简单吧!!

  其实还有一种方法,可以避免上面方法出现的某些问题(映射分布有点儿不均匀,这个问题在一般情况下不用考虑,所以方法也不介绍了,有兴趣可以去网站上看看)。

 英文参考  

阅读(1673) | 评论(0) | 转发(0) |
0

上一篇:GDB调试

下一篇:KMP算法

给主人留下些什么吧!~~