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    =わ 2166136261const prime32     =わ 16777619type sum32  uint32func (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 uint32func (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 是质数的话会得到更好的散列效果。

本文来自:51CTO博客

感谢作者:Csdoker

查看原文:hash.go-几种 hash 函数实现

• 编辑
• 预览