FNV与FNV-1a Hash算法说明【转】
转自:http://blog.csdn.net/jiayanhui2877/article/details/12090575
The core of the FNV hash
The core of the FNV-1 hash algorithm is as follows:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash * FNV_prime
hash = hash xor octet_of_data
return hash
The offset_basis andFNV_prime can be found in theparameters of the FNV-1/FNV-1a hash section below.
FNV-1a alternate algorithm
There is a minor variation of the FNV hash algorithm known asFNV-1a:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash xor octet_of_data
hash = hash * FNV_prime
return hash
The only difference between the FNV-1a hash and the FNV-1 hashis the order of the xor and multiply.The FNV-1a hashuses the same FNV_prime and offset_basisas the FNV-1 hash of the same n-bit size.
Parameters of the FNV-1/FNV-1a hash
The FNV-1 hash parameters are as follows:
- hash is an n bit unsigned integer,where
n is the bit length of hash.- The multiplication is performed modulo 2nwhere
n is the bit length of hash.- The xor is performed on the low orderoctet (8 bits) of hash.
- The FNV_prime is dependent on n, the size of the hash:
32 bit FNV_prime =224 + 28 + 0x93 =
1677761964 bit FNV_prime = 240 + 28 + 0xb3 =
1099511628211128 bit FNV_prime = 288 + 28 + 0x3b =
309485009821345068724781371256 bit FNV_prime = 2168 + 28 + 0x63 =
374144419156711147060143317175368453031918731002211512 bit FNV_prime = 2344 + 28 + 0x57 =
35835915874844867368919076489095108449946327955754392558399825615420669938882575
1260940398923457138527591024 bit FNV_prime = 2680 + 28 + 0x8d =
50164565101131186554345988110352789550307653454047907443030175238311120551081474
51509157692220295382716162651878526895249385292291816524375083746691371804094271
873160484737966720260389217684476157468082573Part of the magic of FNV is the selection of the FNV_primefor a given sized unsigned integer.Some primes do hash better than other primes for a given integer size.
- The offset_basis for FNV-1 is dependent on
n, the size of the hash:32 bit offset_basis = 2166136261
64 bit offset_basis = 14695981039346656037
128 bit offset_basis = 144066263297769815596495629667062367629
256 bit offset_basis =
100029257958052580907070968620625704837092796014241193945225284501741471925557512 bit offset_basis =
96593031294966694980094354007163104660904187456726378961083743294344626579945829
321977164384498130518922065398057844953282393400838761919287015838695177851024 bit offset_basis =
14197795064947621068722070641403218320880622795441933960878474914617582723252296
73230371772215086409652120235554936562817466910857181476047101507614802975596980
40773201576924585630032153049571501574036444603635505054127112859663616102678680
82893823963790439336411086884584107735010676915NOTE: Older versions of this web page incorretly indicated that the 128 bitFNV_prime was 2168 + 28 + 0x59.This was not correct.While that satisfied all of the significant
FNV_prime properties,it was not the smallest 128 bit
FNV_prime.The 128 bit offset_basischanged from275519064689413815358837431229664493455to144066263297769815596495629667062367629was changed as a result of the 128 bit
FNV_prime correction.(Sorry about that!)
最新文章
- python学习笔记之基础二(第二天)
- ThinkPhp单字母函数
- 使用NVelocity生成内容的几种方式
- ASP.NET MVC 模块与组件(二)——定制图片验证码
- Linq To DataSet
- TS 流的解码过程(系摘抄)
- NGUI 实现 透明底图遮罩 &;&; 人物像素变黑
- 可爱的 Python : Python中函数式编程,第二部分
- Linq to SQL 简单的增删改操作
- Andrew Ng机器学习第一章——单变量线性回归
- Lambda in Java VS in C#
- 基于kettle的简单HTTP接口监控
- Java编程实现多线程TCP服务器完整实例
- Weblogic java生成wlfullclient.jar
- git 管理和存储二进制大文件
- Codeforces Round #551 (Div. 2) A-E
- Python+Excel+Unittest+HTMLTestRunner实现数据驱动接口自动化测试(一)
- Java不定参数Object… obj 和 Object[] 的区别
- supervisor control in centos 6/7 python2.6.2.7 3.4
- Spring Boot(5) 集成Hibernate 日志配置