很多概念都叫“哈希”：哈希表里的 hash，SHA-256 这样的密码学哈希，局部敏感哈希 LSH，一致性哈希，滚动哈希，Bloom Filter 里的多重哈希，甚至还有专门存密码用的 bcrypt、Argon2。它们名字相似，实际目标差得很远。
一个共同抽象可以写成：给定输入 \(x\)，要设计哈希函数 \(h\) 把它映射到某个输出空间 \(Y\)，即 \(h: X \to Y\)。这句话太宽泛，宽泛到几乎不能指导工程实践。真正的问题不是“哈希是什么”，而是：
这个哈希函数希望保留什么信息，又希望抹掉什么信息？
有些哈希希望相似输入得到完全不同的输出，有些哈希希望相似输入尽量落在一起；有些哈希追求速度，有些哈希故意变慢；有些哈希害怕碰撞，有些哈希则靠“可控碰撞”工作。
碰撞不是异常，而是前提
只要输入空间远大于输出空间，碰撞就无法避免。输入空间通常极大，输出空间只有 \(m\) 个可能值，放入 \(n\) 个对象时，就会出现多个输入映射到同一个输出的可能性。粗略地看，如果哈希输出均匀分布，至少一次碰撞的概率接近：
这就是生日悖论在哈希场景里的影子。它提醒我们一件事：讨论哈希时不要只说“会不会碰撞”，而要问“碰撞之后系统怎么处理，以及这种碰撞是否可接受”。
哈希表可以接受碰撞，只要冲突处理得好；SHA-256 不能让攻击者可行地构造碰撞；LSH 则希望相似对象以较高概率碰撞。碰撞在不同系统里扮演完全不同的角色。
哈希表：为了把 key 快速放到某个位置
在哈希表里，哈希函数通常用于把 key 映射到数组下标。典型过程是：
index = hash(key) % capacity
这里的目标不是安全，也不是相似搜索，而是让 key 尽量均匀地分布到桶里。假设表里有 \(n\) 个元素，桶数量是 \(m\)，负载因子是 \(\alpha = n/m\)。当 \(\alpha\) 太高时，冲突会变多，查询和插入成本会上升；所以哈希表通常会扩容，并重新分布已有元素。
工程上，哈希表的复杂性不只在哈希函数本身，还在冲突处理策略。常见方案有链地址法和开放寻址法。链地址法在每个桶后面挂链表或其他结构；开放寻址法则在数组内部继续探测下一个可用位置。前者对删除更自然，后者缓存局部性更好，但对负载因子更敏感。
哈希表里的 hash 通常追求几个性质：计算快、分布均匀、对常见输入模式不容易退化。它不需要“不可逆”。很多语言运行时的哈希函数会加入随机种子，主要是为了避免攻击者构造大量碰撞 key 导致性能退化，而不是为了替代密码学哈希。
哈希表的哈希值不是数据的“指纹”。它只是定位手段。即使两个 key 的哈希值一样，哈希表仍然要比较原始 key，才能确认它们是不是同一个键。
密码学哈希：为了让篡改变得可见
SHA-256、SHA-3、BLAKE3 这类函数关注的是另一个问题：给定一段数据，生成一个固定长度的摘要，使得攻击者很难伪造另一个具有同样摘要的数据。
密码学哈希一般希望满足几个性质。给定 \(x\)，计算 \(h(x)\) 很容易；但给定 \(h(x)\)，反推出 \(x\) 很难，这叫原像抗性。给定 \(x\)，找到另一个 \(y \ne x\) 且 \(h(y)=h(x)\) 很难，这叫第二原像抗性。找到任意一对不同输入 \(x,y\) 使得 \(h(x)=h(y)\) 很难，这叫碰撞抗性。
密码学哈希通常还有雪崩效应：输入变动一位，输出看起来应该完全改变。对 SHA-256 来说，"hello" 和 "hellp" 的摘要不应该只差一点点，而应该像两个无关随机值。
这和 LSH 的目标正好相反。密码学哈希试图消除输入之间的相似性，让输出空间看起来随机；LSH 则试图保留相似性，让相似对象更可能靠近或相撞。
使用密码学哈希时，还有一个边界要注意：哈希摘要本身不能证明“是谁生成的”。如果你需要认证消息来自某个持有密钥的人，通常要使用 HMAC 或数字签名，而不是单纯的 SHA256(message)。
校验和：检测意外错误，不是防攻击
CRC32、Adler-32、Internet checksum 常被放在“哈希”附近讨论。它们能把数据压缩成较短校验值，用于发现传输或存储中的意外错误。
问题在于，校验和通常不是为对抗攻击者设计的。CRC 可以很好地检测某些误码模式，但攻击者如果知道算法，往往可以构造出不同数据但相同 CRC 的内容。
所以文件下载页面上如果只给 CRC32，它更多是在帮助你发现网络损坏或存储错误；如果要防止恶意篡改，需要密码学哈希，甚至还需要签名。SHA-256 能告诉你“内容是否与某个摘要匹配”，签名进一步告诉你“这个摘要是否由可信私钥确认过”。
LSH：相似输入应该更容易碰撞
局部敏感哈希 Locality-Sensitive Hashing 的设计方向和密码学哈希不同。它关心的是相似搜索。
在高维空间里，直接找最近邻往往很贵。假设有几千万个向量，每次查询都和所有向量计算余弦相似度，成本很快不可接受。LSH 的思路是设计一族哈希函数，使得相似对象更容易落入同一个桶。
可以抽象成：
这不是严格保证，而是概率性质。LSH 不承诺一定找到最近的对象，它通常牺牲一部分精确性换取查询速度。实际系统里常用多张哈希表、多组随机投影或多阶段召回来提高命中率。
例如，在基于随机超平面的 SimHash 里，一个向量落在超平面的哪一侧决定某一位是 0 还是 1。两个方向相近的向量，更可能在多个随机超平面上落到同一侧，于是得到相近的签名。文本去重、网页相似检测、推荐召回都可以利用这种性质。
MinHash 则常用于集合相似度，尤其是 Jaccard 相似度。两个集合 \(A\) 和 \(B\) 的 Jaccard 相似度是 \(J(A,B)=|A \cap B|/|A \cup B|\)。MinHash 的漂亮之处在于，在随机排列下，两个集合最小哈希值相等的概率正好等于它们的 Jaccard 相似度。
LSH 的边界也很明确：它适合做候选集召回，不适合直接当作最终判断。工程系统里常见做法是先用 LSH 找到一批候选，再用真实距离或更昂贵的模型重新排序。
一致性哈希：节点变化时少搬数据
分布式系统里经常要把 key 分配到不同节点。最直接的方法是：
node = hash(key) % N
当节点数 \(N\) 固定时，这很简单。但如果从 10 台机器扩容到 11 台，大量 key 的结果都会变化，缓存会大面积失效，数据也需要大规模迁移。
一致性哈希解决的是这个问题。它把哈希空间看成一个环，节点和 key 都映射到环上。一个 key 通常归属于顺时针方向遇到的第一个节点。增加一个节点时，只影响它在环上接管的那一段范围；删除一个节点时，也主要影响它负责的那段数据。
这里哈希函数本身并不神秘，关键是映射结构改变了。它优化的是节点集合变化时的数据稳定性，而不是单次查找速度，也不是安全性。
实际实现中还会引入虚拟节点。因为真实节点数量少时，直接映射到环上可能分布不均。每台机器映射成多个虚拟节点，可以让负载更平滑。代价是路由表更大，维护逻辑也更复杂。
滚动哈希：窗口移动时不要从头算
滚动哈希常见于字符串匹配、内容切片、增量同步等场景。它关注的问题是：当一个窗口从 s[i:i+k] 移动到 s[i+1:i+k+1] 时，能不能快速更新哈希值，而不是重新扫描整个窗口。
Rabin-Karp 算法就是典型例子。把字符串看作某个进制下的数字，窗口哈希类似：
窗口右移时，可以减去离开的字符，乘以基数 \(b\)，再加上新字符。这样每次更新可以接近 \(O(1)\)。
滚动哈希通常会有误判，因为不同窗口可能有相同哈希值。所以在字符串匹配中，哈希相等后仍然需要比较原文，除非你能接受极小概率错误。很多实现会使用双模数或 64 位自然溢出来降低碰撞概率，但这仍然不是密码学保证。
它的价值不在“摘要安全”，而在“局部更新便宜”。
完美哈希：当 key 集合固定时，可以追求零碰撞
普通哈希表要处理动态插入和删除，因此必须接受碰撞并设计冲突处理。但如果 key 集合提前固定，就可以构造完美哈希，使得集合内每个 key 都映射到不同位置。
编译器关键字表、静态字典、只读索引都可能用到这种方法。最小完美哈希进一步要求空间接近 key 的数量，也就是 \(m=n\)。这时查找可以很快，内存也紧凑。
代价是构造过程更复杂，而且对动态更新不友好。只要 key 集合变了，原来的完美性质可能就不成立。它适合“构建一次，查询很多次”的场景，而不是高频写入场景。
Bloom Filter：用多个哈希换空间
Bloom Filter 不是哈希函数，而是一种概率型集合结构。它用一个 bit 数组和多个哈希函数表示集合成员关系。
插入元素 \(x\) 时，计算 \(k\) 个位置：
h1(x), h2(x), ..., hk(x)
然后把这些 bit 置为 1。查询时，如果这些位置全是 1，就认为 \(x\) 可能存在；如果至少一个位置是 0，就可以确定 \(x\) 不存在。
这里的关键性质是：Bloom Filter 会有假阳性，但不会有假阴性。它可能把不存在的元素误判为存在，但不会把已经插入的元素判断为不存在，前提是没有删除操作或删除机制正确实现。
它适合在空间紧张、可以接受误判的地方做快速过滤。例如爬虫判断 URL 是否可能访问过，数据库查询前判断某个 key 是否可能存在，缓存穿透防护等。
误判率和 bit 数组大小 \(m\)、元素数量 \(n\)、哈希函数数量 \(k\) 有关。常见近似形式是：
增大 \(m\) 可以降低误判率，增大 \(k\) 一开始也有帮助，但 \(k\) 太大后会增加计算成本，并让 bit 数组更快被填满。它是一个典型的空间、时间和准确率之间的交换。
密码哈希：慢是一种功能
“密码要哈希存储”这句话容易造成误解。直接用 SHA-256 存密码通常不是好主意，因为 SHA-256 太快了。对文件完整性来说，快是优点；对密码存储来说，快反而帮助攻击者做离线暴力破解。
密码哈希函数，比如 bcrypt、scrypt、Argon2，目标是让每次猜测都足够昂贵。它们通常支持成本参数，可以随着硬件变强逐步调高。scrypt 和 Argon2 还会引入内存成本，让 GPU 或 ASIC 的大规模并行破解更不划算。
密码存储还需要 salt。salt 不是秘密，它的作用是让相同密码在不同用户那里得到不同结果，也防止攻击者直接使用预计算表。更高安全要求下还可能使用 pepper，也就是服务端额外保存的秘密值，但这涉及密钥管理，不能替代合适的密码哈希算法。
这里的取舍很直接：登录验证不能慢到用户无法接受，但必须慢到攻击者无法廉价尝试海量密码。
| 类型 | 主要目标 | 碰撞态度 | 相似输入的输出 | 常见场景 | 典型边界 |
|---|---|---|---|---|---|
| 哈希表哈希 | 快速定位 key | 可接受，需要处理 | 不要求相关 | HashMap、Set、字典 | 最坏情况可能退化，需要扩容和冲突处理 |
| 密码学哈希 | 防篡改、摘要、完整性 | 攻击者难以构造 | 应该完全不同 | SHA-256、SHA-3、BLAKE3 | 单独哈希不能证明身份，需要 HMAC 或签名 |
| 校验和 | 检测意外错误 | 可接受，但不抗攻击 | 不关心 | CRC32、网络包、压缩文件 | 不适合安全校验 |
| LSH | 快速找相似对象 | 主动利用碰撞 | 相似则更可能相同或接近 | 向量检索、文本去重、推荐召回 | 通常是近似结果，需要 rerank |
| 一致性哈希 | 节点变化时少迁移 | 用于分配，不是核心问题 | 不关心 | 分布式缓存、分片、负载均衡 | 需要虚拟节点改善均衡性 |
| 滚动哈希 | 滑动窗口快速更新 | 可能误判，需要复核 | 不关心 | 字符串匹配、内容切片、同步算法 | 不是安全哈希，碰撞后常要原文比较 |
| 完美哈希 | 固定集合零碰撞 | 在已知集合内避免碰撞 | 不关心 | 静态字典、编译器关键字表 | 不适合频繁更新 |
| Bloom Filter | 用小空间判断可能存在 | 假阳性来自碰撞 | 不关心 | 去重、缓存穿透、数据库过滤 | 有误判率，普通版本不支持安全删除 |
| 密码哈希 | 抵抗离线暴力破解 | 输出碰撞不是主要矛盾 | 不关心 | bcrypt、scrypt、Argon2 | 故意慢，需要 salt 和成本参数 |
选型时先问目标，而不是先问算法名
如果你在实现一个 Map，应该关心哈希分布、冲突处理、扩容策略和负载因子，而不是拿 SHA-256 来算桶下标。SHA-256 当然也能输出整数，但它通常太重，而且没有解决哈希表真正复杂的部分。
如果你在校验文件是否被篡改，CRC32 就不够。它适合发现意外损坏，不适合对抗能主动构造输入的人。更合理的是使用 SHA-256 这类密码学摘要；如果还要确认发布者身份，就需要签名。
如果你在找相似图片或相似文档，SHA-256 也不合适。两个只差一个像素的图片，密码学哈希会给出完全不同的摘要。你需要的是感知哈希、SimHash、MinHash、向量索引或其他相似性保留方法。
如果你在存密码，不要因为 SHA-256 是“安全哈希”就直接使用它。密码存储的核心威胁是数据库泄露后的离线猜测，所以算法需要慢、可调成本，最好还有内存硬度。这里“快”不是优点。
哈希这个词容易让人产生一种错觉，好像它指向某个统一工具。但在工程里，哈希更像是一类映射技术的共同外壳。真正决定设计的是目标函数：你要速度、安全性、相似性、稳定分配、低内存，还是可增量更新。目标不同，好的哈希就会长成完全不同的样子。