压缩、散列与加密算法

#数据结构 · #压缩 · #加密 · #哈希 · #SHA · #RSA · #AES · #Huffman编码

Hash 表用到的 Hash 函数只是冰山一角。散列算法还有更大的家族：非加密散列（HashMap 用的）、加密散列（MD5/SHA）、数据压缩、对称/非对称加密。本文覆盖这些在实际工程中频繁出现但容易被忽视的算法主题。

1. 非加密散列函数（Hash Functions）

非加密散列的核心目标：快、均匀分布、低碰撞率。

1.1 各语言/系统的默认 Hash

实现	算法	设计目标	特点
Go map	AES-based memhash	极快（硬件加速）	每次启动随机种子，防 HashDoS
Java HashMap	`h ^ (h >>> 16)`	极简	无随机化，可被 HashDoS 攻击
Python dict	SipHash-1-3	安全+速度	防 HashDoS，中等速度
Redis dict	SipHash	安全+速度	防 HashDoS
Rust HashMap	SipHash-1-3	安全+速度	默认安全
C++ unordered_map	MurmurHash / FNV	快	无安全保证（可被攻击）
SwissTable (Abseil)	H1 + H2 双hash	SIMD 批量探测	现代最快

1.2 短字符串 Hash：SipHash vs xxHash vs CityHash

mermaid

flowchart LR
    subgraph Speed["速度 (低→高)"]
        S["SipHash<br/>~2 GB/s<br/>加密级安全"] --> M["MurmurHash3<br/>~6 GB/s"]
        M --> X["xxHash64<br/>~13 GB/s"]
        X --> C["CityHash<br/>~16 GB/s"]
        C --> F["FarmHash<br/>~18 GB/s<br/>最快"]
    end

    subgraph Safety["安全性 (低→高)"]
        FS["FarmHash<br/>无安全保障"]
        XS["xxHash<br/>无安全保障"]
        MS["MurmurHash<br/>可碰撞攻击"]
        SS["SipHash<br/>防HashDoS"]
    end

    style S fill:#4CAF50,color:#fff
    style F fill:#FF9800,color:#fff
    style SS fill:#4CAF50,color:#fff
    style FS fill:#F44336,color:#fff

选型指南：

需要 HashDoS 防护 → SipHash（Rust/Python/Redis 的选择）
内部数据、无外部输入 → xxHash/FarmHash（快 5-10 倍）
硬件有 AES-NI → Go 的 AES memhash（最快）

2. 加密散列函数（Cryptographic Hash）

与非加密散列最重要区别：不可逆（原像抗性）、抗碰撞（找不到两个不同输入产生相同输出）、雪崩效应（改动 1 bit 输出翻天覆地）。

2.1 主流算法对比

算法	输出长度	速度	安全性	状态
MD5	128 bit	极快	❌ 已破解	废弃（可构造碰撞）
SHA-1	160 bit	快	❌ 已破解	废弃（SHAttered 攻击）
SHA-2 (256)	256 bit	中等	✅ 安全	当前主流
SHA-3 (256)	256 bit	慢	✅ 安全	未来替代
BLAKE3	任意	极快 (比 SHA-256 快 10×)	✅ 安全	新一代推荐

mermaid

flowchart LR
    MD5["MD5<br/>128bit"] -->|"2004, 碰撞"| SHA1["SHA-1<br/>160bit"]
    SHA1 -->|"2017, SHAttered"| SHA2["SHA-2 家族<br/>256/512bit"]
    SHA2 -->|"当前主流"| SHA3["SHA-3<br/>256/512bit (备用)"]
    SHA2 -->|"新选择"| B3["BLAKE3<br/>极快+安全"]

    style MD5 fill:#F44336,color:#fff
    style SHA1 fill:#FF9800,color:#fff
    style SHA2 fill:#4CAF50,color:#fff
    style B3 fill:#2196F3,color:#fff

2.2 应用场景

场景	推荐	说明
文件校验	SHA-256	`shasum -a 256 file`
Git commit	SHA-1 → SHA-256（迁移中）	Git 正在迁移到 SHA-256
密码存储	bcrypt / scrypt / Argon2	故意慢+加盐，防暴力破解
TLS 证书	SHA-256	证书签名
区块链	SHA-256 (Bitcoin) / Keccak-256 (Ethereum)	工作量证明
高性能场景	BLAKE3	比 SHA-256 快 10 倍
数据去重	xxHash / BLAKE3	非加密场景优先速度

2.3 密码专用 Hash：为什么不直接用 SHA-256？

mermaid

flowchart TD
    PW["用户密码 'password123'"] --> SHA["SHA-256"]
    SHA --> FAST["结果: ef92b778...\n问题: 1秒可算 10^9 次"]
    FAST --> ATTACK["攻击者用 GPU 暴力破解<br/>每秒数十亿次, 秒破弱密码"]

    PW2["用户密码 + 随机盐"] --> BCRYPT["bcrypt(cost=12)"]
    BCRYPT --> SLOW["结果: $2a$12$...\n配置 cost → 每次哈希 ~0.3s"]
    SLOW --> DEFENSE["攻击者暴力破解<br/>每秒仅 3 次, 弱密码也安全"]

    style FAST fill:#F44336,color:#fff
    style SLOW fill:#4CAF50,color:#fff

bcrypt：内置盐 + 可配置 cost 因子（故意慢）
scrypt：额外需要大量内存（防 GPU/ASIC 暴力破解）
Argon2：2015 年密码哈希竞赛冠军，抗 GPU/ASIC/侧信道

3. 对称加密

算法	密钥长度	块大小	速度	状态
AES-128-GCM	128 bit	128 bit	快（硬件 AES-NI）	✅ 主流，认证加密
AES-256-GCM	256 bit	128 bit	快	✅ 更高安全级别
ChaCha20-Poly1305	256 bit	流密码	快（无 AES-NI 时更快）	✅ 移动端首选
DES	56 bit	64 bit	慢	❌ 已破解
3DES	168 bit	64 bit	极慢	⚠️ 逐步淘汰

GCM (Galois/Counter Mode) = 加密 + 完整性校验（AEAD），TLS 1.3 仅支持 AEAD 模式。

4. 非对称加密

算法	用途	密钥长度	速度
RSA	加密/签名	2048-4096 bit	慢
ECDSA (secp256r1)	签名（TLS/区块链）	256 bit	中等
Ed25519	签名	256 bit	快，现代推荐
X25519	密钥交换（ECDH）	256 bit	快，TLS 1.3
Kyber	后量子 KEM	~1.5 KB 公钥	发展初期

// Ed25519 签名 — 现代非对称签名的推荐选择
import "crypto/ed25519"

publicKey, privateKey, _ := ed25519.GenerateKey(rand.Reader)
message := []byte("hello")
signature := ed25519.Sign(privateKey, message)
valid := ed25519.Verify(publicKey, message, signature)
// valid == true

5. 压缩算法

mermaid

flowchart LR
    subgraph Speed["速度优先 (实时)"]
        LZ4["LZ4<br/>~500 MB/s 压缩<br/>~2000 MB/s 解压"]
        SNAPPY["Snappy<br/>(Google)<br/>~250 MB/s"]
        ZSTD_F["Zstd level 1<br/>~500 MB/s"]
    end

    subgraph Size["压缩率优先 (归档)"]
        GZIP["gzip level 9<br/>~20 MB/s, 压缩率好"]
        BZIP2["bzip2<br/>~5 MB/s, 压缩率更好"]
        XZ["xz / LZMA<br/>~3 MB/s, 压缩率最好"]
    end

    subgraph Best["最佳平衡"]
        ZSTD_B["Zstd level 3-6<br/>~200 MB/s<br/>压缩率接近 gzip<br/>速度接近 LZ4"]
    end

    style LZ4 fill:#4CAF50,color:#fff
    style ZSTD_B fill:#2196F3,color:#fff
    style XZ fill:#9C27B0,color:#fff

5.1 工程选型指南

场景	推荐	理由
实时日志压缩	LZ4	几乎不增加延迟
RocksDB 底层压缩	Zstd (bottom) / LZ4 (其他层)	各层用不同策略
HTTP 传输	gzip / Brotli	浏览器原生支持
Kafka 消息	Zstd	压缩率高，生产环境首选
数据库备份	Zstd	压缩率+速度平衡
长期归档	xz (LZMA)	压缩率最高
Redis RDB	LZF (默认) / Zstd (可选)	极快+中等压缩

5.2 真实压缩率参考 (enwik8 文本, 100MB)

算法	压缩后	压缩率	压缩速度	解压速度
原始	100 MB	-	-	-
LZ4	57 MB	1.75×	500 MB/s	2000 MB/s
Snappy	52 MB	1.92×	250 MB/s	500 MB/s
Zstd -1	42 MB	2.38×	450 MB/s	1100 MB/s
Zstd -6	36 MB	2.78×	150 MB/s	900 MB/s
gzip -6	37 MB	2.70×	30 MB/s	250 MB/s
bzip2 -9	30 MB	3.33×	8 MB/s	35 MB/s
xz -9	26 MB	3.85×	3 MB/s	60 MB/s

Zstd 几乎在所有维度优于 gzip——压缩率更高、速度快 5-10 倍。

5.3 LZ77 / LZ78 — 现代压缩算法的基石

几乎所有现代压缩算法（gzip、LZ4、Zstd、PNG）都来源于 LZ77 和 LZ78 这两个 1977/1978 年的思想。

LZ77：滑动窗口 + 重复引用

核心思想：用"距离+长度"的指针替代重复出现的字符串。

算法过程（滑动窗口 = 已处理数据）:
  原文: "ABC ABCD ABC ABCD"

  处理到第二个 "ABC ABCD":
    已处理窗口: "ABC ABCD "
    当前: ↑ 看到 "ABC ABCD" (12 字节)

    查找窗口中的最长匹配:
      窗口中有 "ABC ABCD" 出现在位置距离=8, 长度=12
      → 编码为 (distance=8, length=12, next='D')
      → 用 3 个数值替代 12+1 个字符

LZ77 窗口示意：

|---- 已处理 (字典/窗口) ----|-- 当前 --|---- 未处理 ----|
|ABC ABCD                    |ABC ABCD  |...              |
                              ↑
                    搜到距离=8, 长度=12 匹配
                    → 输出 (8, 12, 下一个字符)

LZ77 的变体：

算法	窗口大小	特点
Deflate (gzip)	32 KB	LZ77 + Huffman 编码，HTTP 默认
LZ4	64 KB	极简查找，不追求最大匹配，追求速度
Zstd	最大 2 GB	大窗口 + 熵编码，平衡速度与压缩率
LZMA (xz)	最大 4 GB	超大窗口 + 范围编码，极致压缩率

LZ78 → LZW：字典构建

LZ77 的问题: 窗口是"最近 N 字节"，远处的重复发现不了。

LZ78 的改进: 显式构建字典，字典项可以无限增长。

LZW (Lempel-Ziv-Welch, 1984, GIF 使用):
  1. 初始字典: 0-255 = 各单字节字符
  2. 扫描输入，找字典中最长的匹配前缀
  3. 输出匹配的字典索引
  4. 将"匹配前缀 + 下一个字符"作为新条目加入字典
  5. 重复

示例: 输入 "ABABABA"
  字典: 0=A, 1=B
  步骤1: "A" → 输出 0, 字典[2]="AB"
  步骤2: "B" → 输出 1, 字典[3]="BA"
  步骤3: "AB" → 输出 2, 字典[4]="ABA"
  步骤4: "A" (继续)...
  输出序列: 0, 1, 2, 1, ...

优势: 字典持续扩大，长重复可以编码为一个索引
缺点: 字典无界增长 → LZW 实际实现中会重置字典

5.4 Huffman 编码完整实现

Huffman 编码给高频字符分配短码、低频字符分配长码，实现整体编码长度最短。

// Huffman 树节点
type HuffNode struct {
    char  rune
    freq  int
    left  *HuffNode
    right *HuffNode
}

// 构建 Huffman 树 — O(n log n)
// 1. 统计频率 → 2. 所有节点放入最小堆 → 3. 每次取两个最小合并
func buildHuffmanTree(freq map[rune]int) *HuffNode {
    // 使用最小堆
    h := &minHeap{}
    heap.Init(h)
    for ch, f := range freq {
        heap.Push(h, &HuffNode{char: ch, freq: f})
    }

    for h.Len() > 1 {
        left := heap.Pop(h).(*HuffNode)
        right := heap.Pop(h).(*HuffNode)
        parent := &HuffNode{
            freq:  left.freq + right.freq,
            left:  left,
            right: right,
        }
        heap.Push(h, parent)
    }

    if h.Len() == 0 {
        return nil
    }
    return heap.Pop(h).(*HuffNode)
}

// DFS 生成编码表
func generateCodes(root *HuffNode) map[rune]string {
    codes := make(map[rune]string)
    var dfs func(node *HuffNode, code string)
    dfs = func(node *HuffNode, code string) {
        if node.left == nil && node.right == nil {    // 叶子节点
            codes[node.char] = code
            return
        }
        if node.left != nil {
            dfs(node.left, code+"0")
        }
        if node.right != nil {
            dfs(node.right, code+"1")
        }
    }
    if root != nil {
        dfs(root, "")
    }
    return codes
}

// 编码示例
// 输入: "AABBBCCCC"
// 频率: A=2, B=3, C=4
// 编码: A=00, B=01, C=1    (或类似)
// 原始: 9 × 8bit = 72bit
// Huffman: 2×2 + 3×2 + 4×1 = 14bit  (压缩 ~80%)

Huffman 的正确性 — 为什么是最优前缀码？

定理: Huffman 编码生成的是最优前缀码（编码总长度最短）。

证明（归纳法）:
  基础: n=2 个字符时显然最优（一个 0，一个 1）

  归纳:
    设 x, y 是频率最小的两个字符
    → 在任何最优前缀码中，x 和 y 的码字等长，且仅在最后一位不同
    → 将 x 和 y 合并为一个"虚拟字符"z，频率 f(z) = f(x) + f(y)
    → 对剩下的 n-1 个字符（含 z）递归构造最优树
    → 将 z 展开为 x(0) 和 y(1)，得到 n 个字符的最优树 ■

这个证明同时解释了为什么最小堆算法能找到最优解。

5.5 HMAC — 带密钥的哈希认证

HMAC 不是加密算法，而是消息认证码——验证消息的完整性和来源。TLS、JWT、API 签名都依赖它。

// HMAC-SHA256
import "crypto/hmac"
import "crypto/sha256"

func sign(message, key []byte) []byte {
    mac := hmac.New(sha256.New, key)
    mac.Write(message)
    return mac.Sum(nil)
}

func verify(message, key, expectedMAC []byte) bool {
    mac := hmac.New(sha256.New, key)
    mac.Write(message)
    return hmac.Equal(mac.Sum(nil), expectedMAC)
}
// 注意: hmac.Equal 是常量时间比较，防时序攻击

HMAC 的内部结构：

HMAC(key, message) = H((key ⊕ opad) ∥ H((key ⊕ ipad) ∥ message))

其中:
  ipad = 0x36 重复块大小次（如 64 字节）
  opad = 0x5C 重复块大小次
  ∥    = 拼接
  H    = 底层哈希函数（如 SHA-256）

为什么需要两层哈希？
  1. 内层哈希: H((key ⊕ ipad) ∥ message) → 将 message 与 key 混合
  2. 外层哈希: H((key ⊕ opad) ∥ inner_result) → 防止长度扩展攻击

如果只用 H(key ∥ message):
  SHA-256 有长度扩展攻击 → 攻击者可在 message 后追加数据
  且计算出的新哈希仍然"看起来正确"
  HMAC 的双层结构彻底堵住了这个漏洞

5.6 TLS 1.3 握手 — 加密套件协商全流程

TLS 1.3 将握手缩减到 1-RTT（首次）/ 0-RTT（恢复），加密套件选择也比 1.2 简洁得多。

mermaid

sequenceDiagram
    participant C as Client
    participant S as Server

    Note over C,S: TLS 1.3 完整握手 (1-RTT)
    C->>S: ClientHello<br/>- 支持的密码套件 (仅 5 种 AEAD)<br/>- key_share (X25519 公钥)<br/>- 支持的签名算法

    S->>C: ServerHello<br/>- 选定的密码套件<br/>- key_share (服务端 X25519 公钥)<br/>+ EncryptedExtensions<br/>+ Certificate (证书链)<br/>+ CertificateVerify (签名)<br/>+ Finished (握手 MAC)

    Note over C,S: 双方各自计算: shared_secret = X25519(client_priv, server_pub)
    Note over C,S: 派生: handshake_key → 加密剩余握手
    Note over C,S: 派生: application_key → 加密应用数据

    C->>S: Finished (握手 MAC)<br/>+ [Application Data]
    S->>C: [Application Data]

TLS 1.3 的 5 个标准密码套件：

TLS_AES_128_GCM_SHA256        ← 硬件有 AES-NI 时最快
TLS_AES_256_GCM_SHA384        ← 高安全要求
TLS_CHACHA20_POLY1305_SHA256  ← 移动端 / 无 AES-NI
TLS_AES_128_CCM_SHA256        ← IoT 低功耗
TLS_AES_128_CCM_8_SHA256      ← IoT 最低开销

TLS 1.2 曾有上百种组合（RSA/DHE/ECDHE + AES/CAMELLIA + CBC/GCM + SHA1/SHA256...）
TLS 1.3 砍到只剩 5 种 → 减少了配置错误和降级攻击面

密钥派生流程（HKDF）：

// TLS 1.3 密钥派生示意（简化版）
// 实际使用 HKDF-Extract + HKDF-Expand 链式派生

// 1. 从 ECDHE 得到 shared_secret
sharedSecret := ecdhe(clientPriv, serverPub)

// 2. 早期密钥 (0-RTT 数据用)
earlySecret := HKDFExtract(salt=0, ikm=psk)  // 无 PSK 则为全 0

// 3. 握手密钥 (加密剩余握手消息)
handshakeSecret := HKDFExtract(salt=earlySecret, ikm=sharedSecret)
handshakeKey := HKDFExpand(handshakeSecret, "handshake key")

// 4. 主密钥 → 应用数据密钥
masterSecret := HKDFExtract(salt=handshakeSecret, ikm=0)
applicationKey := HKDFExpand(masterSecret, "application key")

// 前向安全性: 每步派生都不可逆！
// 即使 applicationKey 泄露，也无法逆推出 handshakeSecret 或 sharedSecret

6. 算法全景总结

你的数据需要什么？

├── 需要 Hash 映射 → 选 Hash 函数
│   ├── 公开 API / 防攻击 → SipHash
│   ├── 内部 / 速度第一 → xxHash / FarmHash
│   └── 分布式节点分配 → 见 [[一致性Hash与Raft]]
│
├── 需要完整性校验 → 选加密散列
│   ├── 文件校验 / Git → SHA-256
│   ├── 密码存储 → bcrypt / Argon2（故意慢！）
│   └── 高性能 → BLAKE3
│
├── 需要加密传输 → 选加密方案
│   ├── TLS / 网络 → AES-256-GCM + X25519
│   ├── 移动端 → ChaCha20-Poly1305
│   └── 签名认证 → Ed25519
│
└── 需要节省空间 / 带宽 → 选压缩
    ├── 实时 / 低延迟 → LZ4
    ├── 平衡 → Zstd (level 3-6)
    └── 归档 → xz (LZMA)

参考

xxHash — 极快非加密散列

压缩、散列与加密算法 ​

1. 非加密散列函数（Hash Functions） ​

1.1 各语言/系统的默认 Hash ​

1.2 短字符串 Hash：SipHash vs xxHash vs CityHash ​

2. 加密散列函数（Cryptographic Hash） ​

2.1 主流算法对比 ​

2.2 应用场景 ​

2.3 密码专用 Hash：为什么不直接用 SHA-256？ ​

3. 对称加密 ​

4. 非对称加密 ​

5. 压缩算法 ​

5.1 工程选型指南 ​

5.2 真实压缩率参考 (enwik8 文本, 100MB) ​

5.3 LZ77 / LZ78 — 现代压缩算法的基石 ​

LZ77：滑动窗口 + 重复引用 ​

LZ78 → LZW：字典构建 ​

5.4 Huffman 编码完整实现 ​

5.5 HMAC — 带密钥的哈希认证 ​

5.6 TLS 1.3 握手 — 加密套件协商全流程 ​

6. 算法全景总结 ​

参考 ​

💬 文章评论

压缩、散列与加密算法

1. 非加密散列函数（Hash Functions）

1.1 各语言/系统的默认 Hash

1.2 短字符串 Hash：SipHash vs xxHash vs CityHash

2. 加密散列函数（Cryptographic Hash）

2.1 主流算法对比

2.2 应用场景

2.3 密码专用 Hash：为什么不直接用 SHA-256？

3. 对称加密

4. 非对称加密

5. 压缩算法

5.1 工程选型指南

5.2 真实压缩率参考 (enwik8 文本, 100MB)

5.3 LZ77 / LZ78 — 现代压缩算法的基石

LZ77：滑动窗口 + 重复引用

LZ78 → LZW：字典构建

5.4 Huffman 编码完整实现

5.5 HMAC — 带密钥的哈希认证

5.6 TLS 1.3 握手 — 加密套件协商全流程

6. 算法全景总结

参考