【密码学】一文读懂FNV Hash

FNV

算法概述

FNV哈希全名为Fowler-Noll-Vo算法，是以三位发明人Glenn Fowler，Landon Curt Noll，Phong Vo的名字来命名的，最早在1991年提出。它可以快速hash大量的数据并保持较小的冲突概率，适合hash一些相近的字符串比如IP地址、URL、文件名等等。目前FNV算法有三个版本，分别是: FNV-0(已废弃)、FNV-1以及FNV-1a。这三个算法的结构非常相似，因此呢，在这里就一块说了。

算法结构

总体来说，FNV-0、FNV-1以及FNV-1a都有两个参数，第一个是offset，第二个是一个素数，对于FNV-0来说OFFSET是0，然后PRIME和FNV-1一致，流程也和FNV-1一致，然后FNV-1和FNV-1a的区别是先算异或还是先算乘法，其他的也都是相同的，具体如下图，应该是比较清晰了。

FNV-HASH结构

整个FNV-HASH的结构到这里其实就讲完了，然后发现本文的字数有点少，再来瞎聊几句，凑一下字数吧。

在我用Go写FNV-HASH的实现的时候，发现Go居然内置了这个算法，灰常是神奇，具体Go的代码在下面的链接当中

• https://github.com/golang/go/blob/master/src/hash/fnv/fnv.go

然后他有了，咱这就借鉴一下官方实现就好了，因此呢，下面Go的代码我就不给出来了，官方的实现实际上比我上面讲的要多，但是对于32位哈希来说是一样的，下面我来写个已经废弃的FNV-0吧，主体代码格式借鉴官方库来了。

代码实现

• Go

package fnv
import (
  "hash"
)
const offset32 = 0
const prime32 = 16777619
type sum32 uint32
func New32() hash.Hash32 {
  var s sum32 = offset32
  return &s
}
func (s *sum32) Write(data []byte) (n int, err error) {
  h := *s
  for _, c := range data {
    h *= prime32
    h ^= sum32(c)
  }
  *s = h
  return len(data), nil
}
func (s *sum32) Sum(in []byte) []byte {
  v := uint32(*s)
  return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
}
func (s *sum32) Reset() {
  *s = offset32
}
func (s *sum32) Size() int {
  return 4
}
func (s *sum32) BlockSize() int {
  return 1
}
func (s *sum32) Sum32() uint32 {
  return uint32(*s)
}

• Rust

rust这就佛系实现了，简单来写

fn fnv0(data: &[u8]) -> u32 {
    let mut h = 0u32;
    for &item in data {
        h = h.wrapping_mul(16777619);
        h ^= item as u32;
    }
    h
}