深入解析哈希算法 | Baeldung中文网

1. 哈希简介

哈希（Hashing）广泛应用于算法、数据结构和密码学领域，是现代软件开发中不可或缺的技术之一。

在本文中，我们将深入探讨哈希的基本原理、常见哈希算法及其应用场景，并分析哈希在密码学中的安全性问题，以及其在哈希表中的实现方式。

2. 哈希原理

2.1. 哈希函数

哈希函数是一种将变长输入数据映射为固定长度输出值的函数。输出值通常称为：

哈希码（hash code）
摘要（digest）
哈希值（hash value）

哈希函数的关键特性包括：

✅ 单向性：无法通过哈希值反推出原始输入数据
✅ 确定性：相同输入始终产生相同输出
✅ 均匀分布：输出值在可能范围内分布均匀
✅ 固定长度输出：无论输入大小如何，输出长度不变
✅ 抗碰撞性：应尽量减少不同输入产生相同输出的可能

举个例子，Java 中 String 类的 hashCode() 方法实现如下：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Joshua Bloch 在《Effective Java》一书中解释，选择 31 是因为它是一个奇素数。使用偶数可能导致信息丢失（类似位移操作），而使用因子较多的数会增加碰撞概率。

我们可以运行以下代码验证其行为：

public static void main(String[] args) {
    String anotherTest = "java";
    String test = "test";
    String oneMoreTest = "dev";
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(anotherTest.hashCode()); // output: 3254818
    System.out.println(oneMoreTest.hashCode()); // output: 99349
}

输出结果验证了：

单向性 ✅（无法从 3556498 推出 "test"）
确定性 ✅（多次调用返回相同值）
固定长度 ✅（Java 中 int 固定为 4 字节）

2.2. 密码学哈希函数

密码学哈希函数是专门用于安全场景的哈希函数，常见用途包括：

密码验证
数据完整性校验
区块链（如比特币）

与普通哈希函数相比，密码学哈希函数需要满足额外的安全要求：

✅ 抗碰撞性（Collision Resistance）：无法找到两个不同的输入产生相同输出
✅ 原像抗性（Preimage Resistance）：无法通过哈希值反推出原始输入
✅ 第二原像抗性（Second Preimage Resistance）：给定一个输入，无法找到另一个输入使其哈希相同
✅ 快速计算：计算哈希的过程必须高效
✅ 雪崩效应（Avalanche Effect）：输入的微小变化应导致输出的巨大差异
✅ 伪随机性（Pseudorandomness）

⚠️ 密码学哈希函数的安全性是构建现代安全体系的基石。一旦某个哈希算法被证明不满足这些条件（如 MD5），就应立即弃用。

2.3. 常见哈希算法

以下是几个常见的哈希算法及其特点：

名称	输出长度	说明
MD5	128 bits	已不推荐用于加密用途，仅用于校验
SHA-256	256 bits	广泛用于 TLS、SSL、区块链等
BLAKE3	256 bits	新一代高速哈希算法，支持并行处理

其中：

SHA-2 是美国国家安全局（NSA）设计，NIST 发布的标准，包含 SHA-224、SHA-256、SHA-384、SHA-512 等子算法
BLAKE3 于 2020 年发布，支持任意长度输出，适用于数据完整性验证、签名输入等场景

⚠️ BLAKE3 不适合用于密码哈希（如存储用户密码），应使用专门的算法如 bcrypt、scrypt

3. 哈希攻击类型

3.1. 暴力破解（Brute Force）

暴力破解是一种通过尝试所有可能输入，试图找到与目标哈希匹配的原始数据的方法。

虽然理论上所有哈希函数都可能被暴力破解，但实际中：

✅ 哈希长度越长，破解成本越高
✅ 256 位哈希（如 SHA-256）几乎无法在合理时间内破解

3.2. 生日攻击（Birthday Attack）

生日攻击利用的是“生日悖论”——在一个 23 人的房间里，有 50% 的概率至少有两人同一天生日。

在哈希中，这意味着：

找到任意两个输入具有相同哈希值（碰撞）的复杂度远低于找到特定输入的哈希值
对于 128 位哈希，暴力破解需要 2¹²⁸ 次尝试，而生日攻击只需 2⁶⁴ 次

✅ 举例：若破解特定哈希需 60 万年，生日攻击只需 1 小时即可找到碰撞

这在安全领域非常危险。例如，攻击者可以通过构造一个与用户密码哈希相同的“假密码”来绕过身份验证。

3.3. 拒绝服务攻击（Denial of Service）

攻击者可以通过构造大量哈希冲突的数据，导致哈希表性能下降（从 O(1) 退化为 O(n)），从而拖垮服务器。

常见于：

防火墙
SSH 登录
Web 服务器

✅ 踩坑提醒：在处理用户输入时，务必限制请求频率，避免因哈希冲突导致性能崩溃

4. 哈希表（Hash Table）

4.1. 哈希表原理

哈希表是一种基于哈希函数实现的高效数据结构，用于存储键值对（Key-Value Pair）。

其核心特性：

✅ 常数时间复杂度（O(1)）的插入、查找和删除操作
✅ 内部使用数组 + 桶（bucket）机制
✅ Java 中的 HashMap 是其典型实现

工作流程如下：

插入时，对 key 执行哈希函数，得到索引
将 value 存入对应索引位置的桶中
查找时，对 key 再次哈希，定位桶位置，返回 value

⚠️ 使用不可变对象作为 key 非常重要。若 key 被修改，哈希值将变化，导致无法正确查找数据

4.2. 哈希冲突处理

哈希冲突是指两个不同 key 产生了相同的哈希值。

处理冲突的常见方法有：

方法一：拉链法（Separate Chaining）

每个桶中使用链表（或树）存储冲突的键值对
查找复杂度：O(1) + O(n)（链表长度）

优点：实现简单，扩展性强
缺点：链表查找效率较低（可改用红黑树优化）

方法二：开放寻址法（Open Addressing）

当冲突发生时，通过探针函数（probe function）寻找下一个空桶
常见探针策略：
- 线性探测（Linear Probing）：p(i) = i
- 二次探测（Quadratic Probing）：p(i) = i^2
- 双重哈希（Double Hashing）：p(i) = i * h'(K)

优点：无需额外数据结构
缺点：容易产生聚集，影响性能

5. 总结

本文我们深入探讨了哈希的基本原理、密码学哈希函数、常见哈希算法、攻击方式以及哈希表的实现机制。

关键点总结如下：

✅ 哈希函数是数据结构和密码学的基础
✅ 密码学哈希函数必须满足抗碰撞、抗原像等安全特性
✅ MD5 已不安全，推荐使用 SHA-2 或 BLAKE3
✅ 哈希冲突是不可避免的，需通过拉链法或开放寻址法处理
✅ 哈希表性能依赖于哈希函数质量与冲突处理机制

✅ 踩坑提醒：在开发中务必注意 key 的不可变性、哈希冲突处理机制以及密码哈希算法的选择，否则可能带来严重安全风险或性能问题。

Persistence

REST

Security