哈希算法(也称散列算法)是一种将任意长度的输入数据转换成固定长度输出的数学算法。
Hash 算法的应用场景
Hash 算法常常用在以下的场景中：
数据完整性验证
    .可以为文件生成唯一的哈希值，用于检测文件是否被篡改
    .常见场景如软件下载时的 MD5 校验、区块链中的数据验证
密码存储安全
    .不直接存储用户密码原文,而是存储密码的哈希值
    .即使数据库被攻破,黑客也无法直接获取原始密码
    .常用的密码哈希算法有 bcrypt、PBKDF2 等
数据结构优化
    .哈希表(Hash Table)使用哈希函数进行快速查找
    .能够将查找时间复杂度从 O(n)优化到 O(1)
    .在字典、缓存等场景广泛应用
数字签名
    .在数字签名中,先对消息进行哈希计算
    .再对哈希值进行加密,可以确保消息的完整性和来源
去重和快速比较
    .可以快速判断两个文件或数据是否相同
    .用于文件去重、判断重复内容等场景
负载均衡
    .使用哈希算法可以将请求均匀分配到不同服务器
    .实现简单且负载相对均衡
需要注意的重要特性：
    .哈希算法是单向的,无法从哈希值反推原始数据
    .即使输入数据只改变一位,输出的哈希值也会显著不同
    .优秀的哈希算法应当尽量避免哈希冲突(不同输入得到相同输出)
备注：本文中哈希、hash 用词混用，勿怪。

常见的 Hash 算法

算法	输出长度	速度	安全性	主要用途	优点	缺点	使用建议
MD5	128位(16字节)	非常快	低	文件校验，快速比较	计算速度快，实现简单	已被破解，存在碰撞	仅用于非安全场景的校验
SHA1	160位(20字节)	快	中低	Git版本控制，文件校验	较MD5更安全，速度适中	已被证实可碰撞	建议迁移到SHA2
SHA256	256位(32字节)	中等	高	数字签名，区块链	安全性高，使用广泛	计算较慢	推荐用于安全场景
SHA512	512位(64字节)	中等	很高	高安全性要求场景	安全性极高	计算资源消耗大	用于关键安全场景
BCrypt	184位(23字节)	慢	很高	密码存储	自动加盐，防彩虹表	计算慢，资源消耗大	推荐用于密码哈希
PBKDF2	可变	可配置	高	密钥派生，密码存储	可配置迭代次数	计算资源消耗大	适合密码和密钥存储
HMAC	取决于哈希算法	中等	高	消息认证，API安全	提供认证和完整性	需要密钥管理	推荐用于API认证
Argon2	可变	可配置	极高	密码哈希	内存难度可调，最新设计	实现复杂	推荐用于新项目密码存储

这些算法的安全性是不一样的，像我们常见的 MD5 算法，山东大学王小云教授在坐月子期间成功破解 MD5、HAVAL-128、 MD4 和 RIPEMD 算法，王小云教授发现，可以很快的找到 MD5 的“碰撞”，就是两个文件可以产生相同的“指纹”，后来还破解了 SHA-1。

Go 标准库以及扩展库提供了常用的 Hash 算法，如下表所列：

算法	包路径	输出长度	性能	使用场景	代码示例	特点
MD5	crypto/md5	16字节	很快	非加密校验	md5.Sum(data)	简单快速，不安全
SHA1	crypto/sha1	20字节	快	数据校验	sha1.Sum(data)	较MD5安全，但不推荐
SHA256	crypto/sha256	32字节	中等	加密场景	sha256.Sum256(data)	安全性高，使用广泛
SHA512	crypto/sha512	64字节	中等	高安全场景	sha512.Sum512(data)	最高安全性
Adler32	hash/adler32	4字节	极快	非加密校验	adler32.Checksum(data)	适合数据完整性快速校验
CRC32	hash/crc32	4字节	极快	数据校验	crc32.ChecksumIEEE(data)	适合数据完整性校验
FNV32	hash/fnv	4字节	极快	哈希表	fnv.New32().Sum(data)	适合短字符串哈希
FNV64	hash/fnv	8字节	极快	哈希表	fnv.New64().Sum(data)	FNV32的64位版本，其实还有128位版本，不单独列出了
BLAKE2b	golang.org/x/crypto/blake2b	可变(最大64字节)	快	加密场景	blake2b.New256(nil)	现代加密哈希函数，还有BLAKE2s变种
BCrypt	golang.org/x/crypto/bcrypt	24字节	慢	密码存储	bcrypt.GenerateFromPassword()	专门用于密码哈希

自 Go 1.19 版本以后, hash 包中又增加了 maphash 一种新的哈希算法。

这个 maphash 本来属于秘而不宣的一种 hash 算法，用在内部的 map 的 key 的 hash 计算中，性能优良，一些库为了提升性能，偷偷的引用这个实现，所以 Go 团队干脆把它公开了，放在了 hash 包中。我在项目hash-bench中评估了各种 Hash 算法的性能，maphash 无愧于性能之王。

备注：如果你对 hash 算法很在意，或者你的项目中发现 hash 算法是瓶颈，我建议你在你自己的环境中测试，并且针对你的场景进行仔细的 benchmark 对比。正如这些算法的分类一样，有些算法是偏重于安全的，有些算法偏重于速度，有些算法很容易产生碰撞，有些却尽量避免。大家根据具体的场景选择不同的 hash 算法，不能武断的断言某种 hash 算法比另外一种 hash 算法好。

性能测试
因为算法非常多，代码就非常长，我就不列出所有的代码了，这里值列出主要的代码：

var n int64
var testBytes []byte

func BenchmarkHash(b *testing.B) {
 sizes := []int64{32, 64, 128, 256, 512, 1024}
 for _, n = range sizes {
  testBytes = make([]byte, n)
  readN, err := rand.Read(testBytes)
  if readN != int(n) {
   panic(fmt.Sprintf("expect %d but got %d", n, readN))
  }
  if err != nil {
   panic(err)
  }

  b.Run(fmt.Sprintf("Sha1-%d", n), benchmarkSha1)
  b.Run(fmt.Sprintf("Sha256-%d", n), BenchmarkSha256)
  b.Run(fmt.Sprintf("Sha256SIMD-%d", n), BenchmarkSha256SIMD)
  b.Run(fmt.Sprintf("Sha512-%d", n), BenchmarkSha512)
  b.Run(fmt.Sprintf("MD5-%d", n), BenchmarkMD5)
  b.Run(fmt.Sprintf("Fnv-%d", n), BenchmarkFnv)
  b.Run(fmt.Sprintf("Adler32-%d", n), BenchmarkAdler32)
  b.Run(fmt.Sprintf("Crc32-%d", n), BenchmarkCrc32)
  b.Run(fmt.Sprintf("CityHash-%d", n), BenchmarkCityhash)
  b.Run(fmt.Sprintf("FarmHash-%d", n), BenchmarkFarmhash)
  b.Run(fmt.Sprintf("Farmhash_dgryski-%d", n), BenchmarkFarmhash_dgryski)
  b.Run(fmt.Sprintf("Murmur3-%d", n), BenchmarkMurmur3)
  b.Run(fmt.Sprintf("Highwayhash-%d", n), BenchmarkHighwayhash)
  b.Run(fmt.Sprintf("XXHash64-%d", n), BenchmarkXXHash64)
  b.Run(fmt.Sprintf("XXHash64_ASM-%d", n), BenchmarkXXHash64_ASM)
  b.Run(fmt.Sprintf("MapHash64-%d", n), BenchmarkMapHash64)
  b.Run(fmt.Sprintf("StdMapHash64-%d", n), BenchmarkStdMapHash64)
  b.Run(fmt.Sprintf("ChibiHash64-%d", n), BenchmarkChibiHash)
  b.Run(fmt.Sprintf("Blake2b-%d", n), BenchmarkBlake2b)
  fmt.Println()
 }

}

func benchmarkSha1(b *testing.B) {
 x := sha1.New()

 b.SetBytes(n)
 b.ResetTimer()

 for i := 0; i < b.N; i++ {
  x.Reset()
  x.Write(testBytes)
  _ = x.Sum(nil)
 }
}

... // 其它hash算法

这里写了一个通用的 hash benchmark 函数，用来测试不同 hash 算法在不同大小数据(32, 64, 128, 256, 512, 1024字节)下的性能。同时将 benchmark 结果输出到一个 csv 文件，便于生成图表。我找了一台 Linux/AMD64 的服务器，进行了测试，方便测试 CPU 的高级性能。

    Intel(R) Xeon(R) Gold 6271C CPU @ 2.60GHz, 96 核
    Linux 5.10.0-1.0.0.40
    796GB 内存

以 hash 1024 个字节为例(其它字节性能差不多)，以下是各种 hash 算法的性能对比(包括吞吐)：

BenchmarkHash/Sha1-1024-96                      797005       1471 ns/op  695.96 MB/s
BenchmarkHash/Sha256-1024-96                    377248       3172 ns/op  322.82 MB/s
BenchmarkHash/Sha256SIMD-1024-96                378414       3176 ns/op  322.46 MB/s
BenchmarkHash/Sha512-1024-96                    507495       2353 ns/op  435.16 MB/s
BenchmarkHash/MD5-1024-96                       725233       1648 ns/op  621.33 MB/s
BenchmarkHash/Fnv-1024-96                       911083       1312 ns/op  780.48 MB/s
BenchmarkHash/Adler32-1024-96                  2734160        434.1 ns/op 2359.04 MB/s
BenchmarkHash/Crc32-1024-96                   15229868         78.35 ns/op 13069.26 MB/s
BenchmarkHash/CityHash-1024-96                 1774196        676.4 ns/op 1513.94 MB/s
BenchmarkHash/FarmHash-1024-96                 2465469        487.2 ns/op 2101.90 MB/s
BenchmarkHash/Farmhash_dgryski-1024-96        10912843        109.9 ns/op 9316.16 MB/s
BenchmarkHash/Murmur3-1024-96                  6018717        199.2 ns/op 5141.23 MB/s
BenchmarkHash/Highwayhash-1024-96              9591049        125.0 ns/op 8188.84 MB/s
BenchmarkHash/XXHash64-1024-96                11106692        108.0 ns/op 9477.11 MB/s
BenchmarkHash/XXHash64_ASM-1024-96            12232465         98.09 ns/op 10439.81 MB/s
BenchmarkHash/MapHash64-1024-96               25519408         47.02 ns/op 21777.23 MB/s
BenchmarkHash/StdMapHash64-1024-96             9233738        130.2 ns/op 7864.52 MB/s
BenchmarkHash/ChibiHash64-1024-96              2550945        470.3 ns/op 2177.50 MB/s
BenchmarkHash/Blake2b-1024-96                   952615       1258 ns/op  814.09 MB/s

这里面MapHash明显是最优秀的一种哈希算法:47.02 ns/op, 每秒可以处理21777.23 MB的数据。MapHash算法就是 Go 运行时中为 Map 的哈希所实现的 hash 算法。即使标准库暴露了这个算法，但是还是没有直接通过 hack 的方式使用它性能更高。

maphash(runtime·memhash) 算法
在 Go 运行时中 MapHash 算法叫做memhash, 我想它暴露出来叫做 MapHash 算法主要是因为它最初就是为了 map 使用的吧。我在 benchmark 代码通过下面的 hack 方式使用了 maphash 算法，如果你在项目中使用它，你也可以这样使用：

//go:noescape
//go:linkname memhash runtime.memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr
// 堆代码 duidaima.com
type stringStruct struct {
 str unsafe.Pointer
 len int
}

func MemHash(data []byte) uint64 {
 ss := (*stringStruct)(unsafe.Pointer(&data))
 return uint64(memhash(ss.str, 0, uintptr(ss.len)))
}

这里我们不考虑安全和碰撞，总是把种子设置为 0。你也看到了，这个算法实际是在runtime.memhash中实现的。找到它：

// memhash should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
//   - github.com/aacfactory/fns
//   - github.com/dgraph-io/ristretto
//   - github.com/minio/simdjson-go
//   - github.com/nbd-wtf/go-nostr
//   - github.com/outcaste-io/ristretto
//   - github.com/puzpuzpuz/xsync/v2
//   - github.com/puzpuzpuz/xsync/v3
//   - github.com/authzed/spicedb
//   - github.com/pingcap/badger
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr

func memhash32(p unsafe.Pointer, h uintptr) uintptr

func memhash64(p unsafe.Pointer, h uintptr) uintptr

文件不太好找，在src/runtime/alg.go文件中。注意有趣的注释，被点名的使用了这个函数的库。Go 团队正在推进拒绝 hack 使用这些内部函数的go:linkname方式，但是当前 Go 生态圈的库有很多都这么使用，不好搞。很明显，这个实现是通过 C 或者 ASM 实现的。找到它。具体都在src/runtime/asm_xxx.s文件中，比如src/runtime/asm_amd64.s文件中有memhash的实现：

TEXT runtime·memhash<ABIInternal>(SB),NOSPLIT,$0-32
    // AX = ptr to data
    // BX = seed
    // CX = size
    CMPB    runtime·useAeshash(SB), $0
    JEQ    noaes
    JMP    aeshashbody<>(SB)
noaes:
    JMP    runtime·memhashFallback<ABIInternal>(SB)

可以看到，如果 CPU 支持 Aes 指令，它会使用 Aes 指令来实现 hash 算法，否则会使用runtime·memhashFallback纯内存算法的函数实现。也正是使用了 Aes 指令，所以 maphash 的性能非常高，无愧于性能之王。

AES 指令集（AES-NI，Advanced Encryption Standard New Instructions）是由英特尔和 AMD 引入的一组指令，用于硬件加速 AES 加密和解密操作。AES 是对称加密标准，广泛应用于数据保护领域，如 HTTPS、VPN、磁盘加密等。Go 在 AMD64 架构中使用下面的汇编实现了 memhash:

// AX: data
// BX: hash seed
// CX: length
// At return: AX = return value
TEXT aeshashbody<>(SB),NOSPLIT,$0-0
..

具体我们就不解读了，不可读，主要判断要 hash 的数据的长度，走到不同的分支中，使用种子和数据进行异或操作(PXOR)、使用AESENC指令执行多轮 AES 加密。你可以通过cat /proc/cpuinfo | grep -m 1 -i aes查看你的 CPU 是否支持 aes 指令：

苹果电脑中可以使用sysctl -a | grep aes查看 CPU 是否支持 AES:

通过本次解密，你又了解了一种 Go 秘而不宣的数据结构和函数。