哈希函数

哈希函数 (Hash Function)

哈希函数 (Hash Function) 是将任意长度的输入数据映射为固定长度输出值（称为哈希值、摘要或散列值）的确定性函数。其数学表示为 $h: \{0,1\}^* \to \{0,1\}^n$，其中 $n$ 为输出比特长度。理想的哈希函数应具备计算高效性、抗原像性、抗第二原像性和抗碰撞性四项核心性质，是密码学、数据结构和分布式系统等领域的基石工具。

核心性质

现代密码学哈希函数需满足以下三项安全性质：抗原像性 (Preimage Resistance) 意味着给定哈希值 $y$，找到任意输入 $x$ 使得 $h(x) = y$ 在计算上不可行；抗第二原像性 (Second Preimage Resistance) 指给定输入 $x_1$，找到另一输入 $x_2 \neq x_1$ 使得 $h(x_1) = h(x_2)$ 在计算上不可行；抗碰撞性 (Collision Resistance) 要求找到任意两个不同输入 $x_1 \neq x_2$ 使得 $h(x_1) = h(x_2)$ 在计算上不可行。抗碰撞性是最强的要求，它蕴含抗第二原像性，但反之不成立。

常见算法

SHA-256 (Secure Hash Algorithm 2) 是当代最广泛使用的哈希函数之一，输出256比特摘要，是比特币工作量证明机制的核心组件。SHA-256 属于Merkle-Damgård结构，通过对消息进行填充、分块处理并使用压缩函数迭代计算生成摘要。SHA-3 (Keccak) 采用海绵结构 (Sponge Construction)，具有更强的安全冗余和灵活的输出长度。BLAKE2 和 SHAKE 等较新算法在软硬件实现效率上表现优异。

数据结构中的应用

在数据结构领域，哈希函数是实现哈希表 (Hash Table) 和布隆过滤器 (Bloom Filter) 等高效数据结构的核心。哈希表通过哈希函数将键映射到桶 (Bucket) 索引，实现平均 $O(1)$ 的查找、插入和删除操作。布隆过滤器利用多个哈希函数和位数组实现空间高效的概率性成员查询，允许一定误报率但绝无漏报。通用哈希函数 (Universal Hashing) 族通过从函数族中随机选取一个哈希函数，在概率意义上保证抗碰撞性，广泛用于算法设计和去随机化。

密码学应用

哈希函数是数字签名 (Digital Signature) 和消息认证码 (MAC) 的基础组件：先将消息压缩为摘要再对摘要签名，可大幅提升签名效率。默克尔树 (Merkle Tree) 通过递归哈希将大量数据组织为可高效验证的树形结构，每个叶子节点存储数据块的哈希值，内部节点存储子节点哈希值的哈希，根哈希即默克尔根。默克尔树使轻节点仅需存储根哈希就能验证任意交易的存在性，是区块链系统轻量化的关键技术。在密码学协议中，哈希函数还用于构造承诺方案 (Commitment Scheme)：先通过哈希承诺一个值，稍后通过公开原像验证，实现绑定性 (Binding) 和隐藏性 (Hiding)。

安全性与攻击

对哈希函数的主要攻击分为两类：碰撞攻击 (Collision Attack) 试图找到任意两个不同的输入产生相同的哈希值；原像攻击 (Preimage Attack) 试图根据哈希值恢复输入。生日攻击 (Birthday Attack) 基于生日悖论，可在约 $2^{n/2}$ 次尝试中找到碰撞，因此安全哈希函数的输出长度不应低于256比特（对应128比特安全级）。2017年，Google 研究团队通过约 $2^{63}$ 次 SHA-1 碰撞计算成功实现了SHAttered攻击，宣告 SHA-1 在实际意义上的失效，推动了业界向 SHA-2 和 SHA-3 的全面迁移。

理论拓展

随机谕言机模型 (Random Oracle Model) 将哈希函数理想化为随机函数，是许多密码学方案可证明安全的理论框架。尽管随机谕言机模型存在局限性（真实哈希函数无法完全模拟随机函数），它仍是设计可证明安全密码协议的标准工具。可提取性和同态哈希等方向拓展了哈希函数的理论边界：前者允许从成功验证者处提取原像，后者支持对密文进行哈希运算后仍可验证其结构关系。

总而言之，哈希函数作为从信息压缩到安全认证的通用原语，是现代计算系统不可或缺失的数学抽象。从文件完整性校验到密码货币的共识机制，哈希函数的应用贯穿了计算科学的各个层面。