FNV哈希算法有如下两种,FNV-1a相比FNV-1,散列分布更好。二者不同点为:for循环两行代码的顺序相反
哈希函数一般适用移位和乘除法来实现。哈希函数一般都比较精简,算法复杂度比较低。哈希函数的移位和乘除法可能会导致数据丢失,这也是哈希不可逆的原因
参见《生成offset_basis.py》
octet_of_data:8位数据(即一个字节):即需要被哈希的字符串
FNV_prime:FNV用于散列的质数(质数在哈希算法中发挥着重要作用,在一般使用的哈希除留余数法中: H(key) = key MOD p,p也要求是一个质数(质数也称为素数))
hash = offset_basis
for each octet_of_data to be hashed
hash = hash xor octet_of_data
hash = hash * FNV_prime
return hash
参见《生成32位哈希.py》
将字符串哈希为[0,999]的数字
#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;
hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;
参见《生成任意范围哈希.py》,代码附件链接
参考:
http://www.isthe.com/chongo/tech/comp/fnv/index.html#lazy-mod