曲径通幽论坛

标题: FNV 哈希算法 [打印本页]

作者: beyes 时间: 2011-7-12 14:19
标题: 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形式：

[Plain Text] 纯文本查看 复制代码

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形式：

[Plain Text] 纯文本查看 复制代码

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 +１）。

实例(来自 linux 内核工具 conf 中的 confdata.c)：

[C++] 纯文本查看 复制代码

static unsigned strhash(const char *s)

{

    /* fnv32 hash */

    unsigned hash = 2166136261U;

    for (; *s; s++)

        hash = (hash ^ *s) * 0x01000193;

    return hash;

}

主页：http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-source

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)