hash.go-几种 hash 函数实现

接口定义

type Hash interface {
   // 嵌入了 io.Writer 接口
   // 向执行中的 hash 加入更多数据
   // hash 函数的 Write 方法永远不会返回 error
   io.Writer

   // 把当前 hash 追加到 b 的后面
   // 不会改变当前 hash 状态
   Sum(b []byte) []byte

   // 重置 hash 到初始化状态
   Reset()

   // 返回 hash 结果返回的字节数
   Size() int

   // BlockSize 返回 hash 的基础块大小
   // 为了提高效率
   // Write 方法传入的字节数最好是 blick size 的倍数
   BlockSize() int
}

// 结果为 32bit hash 函数接口
type Hash32 interface {
   Hash
   Sum32() uint32
}

// 结果为 64bit hash 函数接口
type Hash64 interface {
   Hash
   Sum64() uint64
}

Go 的 hash 包里有几种 hash 算法实现，分别是 adler32，crc32/64，fnv 。

fnv

fnv 是一种简单可靠的 hash 算法。它的结果长度有多种， fnv.go 中也提供了多种长度的算法实现。 fnv 核心算法很简单：先初始化 hash ，然后循环 乘以素数 prime32 ，再与每位 byte 进行异或运算。

const offset32        = 2166136261
const prime32         = 16777619
type sum32   uint32
func (s *sum32) Reset()   { *s = offset32 }
func (s *sum32) Size() int   { return 4 }
func (s *sum32) BlockSize() int   { return 1 }
func (s *sum32) Write(data []byte) (int, error) {
   hash := *s
   for _, c := range data {
      hash *= prime32
      hash ^= sum32(c)
   }
   *s = hash
   return len(data), nil
}
func (s *sum32) Sum32() uint32  { return uint32(*s) }

adler - 可靠、快速的 hash 算法

Adler-32通过求解两个16位的数值 A、B 实现，并将结果连结成一个32位整数.

A 就是字符串中每个字节的和，而 B 是 A 在相加时每一步的阶段值之和。在Adler-32开始运行时， A 初始化为 1 ， B 初始化为 0 ，最后的校验和要模上 65521 (小于2的16次方的最小素数)。

type digest uint32
func (d *digest) Reset() { *d = 1 }

func (d *digest) Write(p []byte) (nn int, err error) {
   *d = update(*d, p)
   return len(p), nil
}

const (
   // 比 65536 小的最大素数
   mod = 65521
   // nmax is the largest n such that
   // 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1.
   // It is mentioned in RFC 1950 (search for "5552").
   nmax = 5552
)

// Add p to the running checksum d.
func update(d digest, p []byte) digest {
   s1, s2 := uint32(d&0xffff), uint32(d>>16)
   for len(p) > 0 {
      var q []byte
      
      // 每次处理数据量为 nmax
      // 处理完之后再 % mod
      // 防止溢出，且尽可能少的执行 mod 运算
      if len(p) > nmax {
         p, q = p[:nmax], p[nmax:]
      }
      
      // 底下这两个循环我不明白为啥不合成一个？？？
      // 有明白的可以告知一声
      
      for len(p) >= 4 {
         s1 += uint32(p[0])
         s2 += s1
         s1 += uint32(p[1])
         s2 += s1
         s1 += uint32(p[2])
         s2 += s1
         s1 += uint32(p[3])
         s2 += s1
         p = p[4:]
      }
      for _, x := range p {
         s1 += uint32(x)
         s2 += s1
      }
      s1 %= mod
      s2 %= mod
      p = q
   }
   
   // 把 s2 s1 再合成一个 uint32
   return digest(s2<<16 | s1)
}

crc32

CRC 为校验和的一种，是两个字节数据流采用二进制除法（没有进位，使用XOR来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为 n + 1 的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上 n 个 0。

对于 crc32 来说，IEEE 标准下的除数是 0xedb88320。除法运算效率比较低，所以生产环境一般使用的是查表法。（这块儿都是数学推导，没找到资料，也没看懂。）

以上是 hash 包中提供的几种 hash 算法。除此之外， crypto 包里提供了一些其他的算法也实现了 hash 接口，比如 md5，sha1，sha256 等。

md5 （消息摘要算法，经常有同学把 md5 错当成加密算法）是一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值。 md5 已被证实无法防止碰撞，已经不算是很安全的算法了，因此不适用于安全性认证，如 SSL公开密钥认证 或是 数字签名 等用途。对于需要高度安全性的数据，一般建议改用其他算法，比如 sha256 。

素数

hash 算法中常用中间值对一个 素数 取模作为 hash 值，这是为什么呢？

一个好的散列函数要尽可能减少冲突。如果对合数取模，那么所有该函数的因子的倍数冲突的概率会增大，而质数的因子只有1和它本身，所以对于特定倍数的数字来说，会有更好的散列效果。比如：

假设 mod 是 6，对于 2 的倍数 2、4、6、8、10、12 的 hash 值是 2、4、0、2、4、0，对于 3 的倍数 3、6、9、12 的 hash 值是 3、0、3、0。

假设 mod 是 7，对于 2、4、6、8、10、12 的 hash 值是 2、4、6、1、3、5，对于 3 的倍数 3、6、9、12 的 hash 值是 3、6、2、5。

可以看出，如果 mod 是质数的话会得到更好的散列效果。