本文分类:
数据结构与算法

FNV Hash 算法具有快速、冲突率小、Hash 结构高度分散的特点,适用于 Hash 一些非常相近的字符串,比如 URL,hostname,文件名,text,IP地址等,FNV算法说明可参考 FNV Hash

FNV Hash 算法全名为 Fowler-Noll-Vo 算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出,FNV算法有三个版本:FNV-0(已废弃)、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

hash是算法的结果,是一个无符号 n 位整数,n 应该是 2 的 n 次方,FNV_prime 和 offset_basis 的值依赖于 n,当 n 为 32 和 64 时取值如下,通常 32 位就够用了,其他值请参考 FNV Hash

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

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

Java实现如下。

/**
 * fnv - Fowler/Noll/Vo- hash code
 * <p>
 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
 */
public class FNV {
    private static final int FNV1_32_INIT = 0x811c9dc5;

    private static final int FNV1_PRIME_32 = 16777619;

    private static final long FNV1_64_INIT = 0xcbf29ce484222325L;

    private static final long FNV1_PRIME_64 = 1099511628211L;

    public static int fvn1a32(byte[] data) {
        int hash = FNV1_32_INIT;

        for (int i = 0; i < data.length; i++) {
            hash ^= (data[i] & 0xff);
            hash *= FNV1_PRIME_32;
        }

        return hash;
    }

    public static long fvn1a64(byte[] data) {
        long hash = FNV1_64_INIT;
        for (int i = 0; i < data.length; i++) {
            hash ^= (data[i] & 0xff);
            hash *= FNV1_PRIME_64;
        }

        return hash;
    }
}
本文来自 [时光记 - 王智超的个人空间](www.hiwzc.com),转载请注明出处。