hash算法fnv
-
FNV哈希算法 取自于1991年Glenn Fowler和 Phong Vo向IEEE POSIX P1003.2委员会发送评论者意见的想法 。在随后的投票中： Landon Curt Noll 对他们的算法进行了改进。一些人尝试了此哈希，发现它工作得很好。在发给 Landon的电子邮件中，他们将其命名为“ Fowler / Noll / Vo ”或
FNV
哈希 -
FNV哈希被设计为快速，同时保持较低的冲突率。该 FNV速度允许一个快速散列大量的数据，同时保持合理的碰撞率。FNV散列的高度分散性使其非常适合散列几乎相同的字符串，例如URL，主机名，文件名，文本，IP地址等
fnv版本
- FNV
- FNV-1
- FNV-1a
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-1算法的区别就是异或运算与乘法运算顺序调整了，即是说FNV-1算法是先进行乘法运算再进行异或运算
参数说明
-
offset_basis
参数依赖于hash位数的大小
-
32 bit offset_basis = 2166136261
-
64 bit offset_basis = 14695981039346656037
-
128 bit offset_basis = 144066263297769815596495629667062367629
-
256 bit offset_basis =
100029257958052580907070968620625704837092796014241193945225284501741471925557 -
512 bit offset_basis =
9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785 -
1024 bit offset_basis =
14197795064947621068722070641403218320880622795441933960878474914617582723252296732303717722150864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915 -
offset_basis 计算脚本
hash_bits = insert_the_hash_size_in_bits_here;
FNV_prime = insert_the_FNV_prime_here;
offset_basis = 0;
offset_str = “chongo /\…/\”;
hash_mod = 2
hash_bits
;
str_len = strlen(offset_str);
for (i=1; i <= str_len; ++i) {
offset_basis = (offset_basis * FNV_prime) % hash_mod;
offset_basis = xor(offset_basis, ord(substr(offset_str,i,1)));
}
//输出
print hash_bits, “bit offset_basis =”, offset_basis;
-
FNV_prime
参数依赖于hash位数的大小
-
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 =
35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 -
1024 bit FNV_prime = 2
680
+ 2
8
+ 0x8d =
5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
-
octet_of_data
8位元数据或者单个字节数据
伪代码实现
/**
* 这里的值跟2166136261等价，因为int大小越界调整为16进制表示
*/
private final static int offset_basis_32 = 0x811c9dc5;
private final static int FNV_prime_32 = 16777619;
/**
*
* @param str
* @return
*/
public static int hash(String str) {
char[] chrs = str.toCharArray();
int hash = offset_basis_32;
for(int i=0;i<chrs.length;i++) {
hash ^= chrs[i];
hash *= FNV_prime_32;//乘法运算更快一点
//hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24); //将上面的乘法运算改为移位和运算
}
return Math.abs(hash);
}
/**
* 获取限定长度的hash
* 注意长度大小
* @param str 初始字符串
* @param len hash位数
* @return
*/
public static int hashOfLen(String str,int len) {
int hash = hash(str);
hash = (hash >> len) ^ ( hash & ( (1<<len)-1 ) );
return hash;
}
/**
* 获取限定最大的值的hash
* @param str 初始字符串
* @param max hash最大值
* @return
*/
public static int hashOfMax(String str,int max) {
int hash = hash(str) % (max+1);
return hash;
}
特别注意的地方。
- 按照长度缩小。基准值应选择大于当前值最接近的位数，例如你需要16位的长度，选择32位，需要54位长度 选择64位
-
同理按照大小缩小也一样。如果选择最大值为99999，则选择32位 因为2
32
> 99999,如果选择最大值为3000000000，则选择64位 因为2
64
> 3000000000