作者：chen-true@qq.com
仅供学习交流，如有错误恳请指出！
===========================================
哈希函数（Hash function），又称哈希算法、散列函数、杂凑函数、摘要算法等，是一种将任意长度的输入数据M，通过一个确定性的映射H，转换为固定长度输出h的函数，记为h = H ( M )，其中h称为哈希值（散列值、杂凑值、摘要值等）。
从本质上看，哈希就是一种把“大空间”映射到“较小空间”的“指纹化”过程：不同输入经过算法压缩后得到固定长度的输出。由于这种映射在信息论意义上是不可逆的，一般无法从哈希值h恢复出原始输入M。
哈希算法并不是某一个具体的公式，而是一类遵循“散列映射”思想的算法统称：只要满足哈希函数的一般特征，就可称为哈希算法。密码学中常见的哈希算法包括MD5、SHA-1、SHA-256等。
2）哈希函数的特性
一个设计良好的（尤其是密码学意义上的）哈希函数，通常应满足以下特性：
1、确定性：对于相同的输入M，哈希函数H在任何时候计算得到的输出h都应完全相同。
2、单向性/抗原像性：给定一个哈希值h，在计算上应当极其困难去找到任意一个输入M，使得H ( M ) = h。
换句话说，哈希函数在实际使用中被视为单向函数：可以很容易从输入算出哈希值，但几乎不可能从哈希值逆推回有意义的原始输入。
理论上，可以通过暴力穷举的方式，对大量可能的输入逐一计算哈希值，并与目标哈希值进行比对，最终可能找到某个满足H ( M ) = h的输入。但由于输入空间极其巨大，这种方法的计算代价通常高到难以实现，实际攻击中几乎不可行。
3、抗第二原像性：已知一个具体输入M，想找到另一个不同的输入N，使得H ( M ) = H ( N )，在计算上也应非常困难；
4、抗碰撞性：不事先指定输入，只是“随便”寻找一对不同的输入（M，N），使得H ( M ) = H ( N )，也应该在计算上非常困难。
由于输入空间（几乎）无限，而输出空间有限，从数学上看，碰撞必然存在。这被称为“碰撞不可避免性”。但对于一个设计良好的哈希函数来说，“碰撞不可避免”并不意味着“碰撞容易找到”，我们的目标是让找到有效碰撞在计算上几乎不可能。
5、固定输出长度：无论输入数据长度多少，哈希函数的输出长度应保持固定。
例如：MD5的输出长度固定为128比特，SHA-1的输出长度固定为160比特。通常认为，在相同设计水平下，哈希函数输出长度越长，其抗碰撞能力越强，安全性也越高。
6、伪随机性：哈希值在数值上应当呈现“类似随机”的分布特性，看起来像是均匀且无规律地分布在输出空间中。
当然，由于对相同输入进行两次哈希计算结果必然相同，哈希值并不是真正的随机数，而是伪随机——在固定算法下可重现，但在统计特性上尽量接近随机分布。
7、高效性：哈希函数的计算过程应当足够高效，适合在实际系统中被大量调用，计算开销相对较低。
但是，在某些特定场景（如密码存储）中，人们会刻意选用计算成本更高的哈希/派生算法（如bcrypt、scrypt、Argon2等），以增加暴力穷举攻击的难度。
8、雪崩效应：对输入数据进行极小的修改（例如只改变一个比特），输出哈希值应当发生大范围、不可预测的变化，看不出与原输出在模式上的相似性。
良好的雪崩效应是哈希函数“伪随机性”和抗分析能力的重要体现。
3）哈希函数的应用
由于哈希函数兼具固定长度输出、单向性、伪随机性和抗碰撞性等特征，在工程和密码学中有着非常广泛的应用，常见场景包括但不限于以下几类。
1、哈希表与数据索引
在数据结构中，哈希函数最典型的用途是构造哈希表（Hash Table）：
·将键值（如字符串、整数等）通过哈希函数映射为一个整数索引
·再根据该索引，将数据存放到数组或桶（bucket）中；
·查找时只需重新计算键的哈希值，直接定位到对应位置。
良好的哈希函数可以使键在桶中均匀分布，从而在平均情况下实现接近 O(1)时间复杂度的插入、查询和删除操作。
在数据库索引、编程语言的字典/映射类型（如map、dict、HashMap）中都大量使用了哈希函数。
2、数据完整性校验
哈希函数常用于对文件或消息进行完整性校验：
·发送方在发送数据前计算出其哈希值，随数据一并发送或单独公布（例如发布文件下载链接时给出SHA-256校验值）；
·接收方在收到数据后重新计算哈希值，与原哈希值对比；
·若二者一致，说明在传输过程中数据高度可信未被篡改或损坏。
在这种场景下，哈希函数充当“数字指纹”的角色，任何对数据的微小改动（甚至是一个比特的翻转）都将导致完全不同的哈希值。
3、密码存储与密钥派生
在密码学应用中，哈希函数经常用于保护密码和生成密钥：
① 密码存储
系统通常不会直接存储用户的明文密码，而是存储h = H（密码+盐）。
登录时对用户输入的密码进行同样的哈希计算并比对结果。这样即使数据库泄露，攻击者拿到的也只是哈希值而非明文密码。
思考：为什么不直接存储h = H ( 密码 )，而非要加“盐（salt）”变成h = H（密码+盐）呢？
用哈希函数存储密码时为什么要加“盐”？
② 口令到密钥的派生（KDF）
直接将人类口令当作加密密钥不安全，通常通过哈希函数或专门的密钥派生函数（如PBKDF2、scrypt、Argon2等）把口令“拉长、搅拌、放大成本”，生成强度更高的密钥，用于对称加密或其他密码操作。
在这些场景中，人们往往会选择基于哈希的“慢算法”，用更多计算消耗来对抗暴力穷举。
4、数字签名与消息认证
哈希函数还是数字签名与消息认证的基础组件：
① 数字签名
·对长消息M直接做公钥签名效率很低，一般是先计算消息哈希值h = H ( M )；
·再对h进行签名，而不是对整个M签名。
这样既能保证签名结果与消息内容一一对应，又能显著提高效率。
② 消息认证码（MAC）和HMAC
·为保证消息在传输过程中未被篡改且确实来自持有密钥的一方，可以使用基于哈希的消息认证码HMAC（Hash-based Message Authentication Code）；
·与单纯的“哈希值校验”不同，HMAC依赖一个密钥K，只有持有密钥的一方才能生成合法的认证值。
4）哈希算法不等于加密算法
·哈希函数是一类单向映射算法，用于将任意长度输入压缩为固定长度的摘要值，具有不可逆性和抗碰撞性，常用于密码存储、完整性校验和数字签名等场景；
·加密算法则是一类可逆的变换，依赖密钥对数据进行加密和解密，目标是保护数据的机密性，常用于安全传输和敏感信息存储。
二者在设计目标、可逆性、是否依赖密钥以及应用场景上都有本质区别，不能混为一谈。
5）常见哈希算法
图 常见哈希算法
