什么是哈希函数？一个好的哈希函数有哪些标准？

简化版

哈希函数负责把任意的「键」映射成一个固定范围内的整数（哈希值），用来当数组下标。一个好的哈希函数要满足：确定性（同键必同值）、均匀性（把键尽量均匀散开、少冲突）、高效（计算快）、雪崩效应（键有微小变化，哈希值大幅变化）。均匀性是核心，它直接决定哈希表会不会退化。

详细版

哈希函数的目标：任意键 → [0, capacity) 内的整数，且尽量让不同键落到不同位置。好的哈希函数标准：

标准	含义	为什么重要
确定性	同一个键每次算出的值必须相同	否则存进去就再也找不到了
均匀分布	各种输入尽量均匀铺满整个下标范围	决定冲突多少，是性能命根子
高效	计算本身要快（O(1) 级）	每次增删查都要算一次
雪崩效应	输入改一点，输出变很多	避免相似的键（如 “aa”、“ab”）扎堆
低冲突	尽量减少不同键映射到同一值	冲突多 → 退化成线性查找

实际工程里一般不追求「完美哈希」，而是「足够均匀 + 足够快」的折中，剩下的冲突交给拉链法/开放寻址法处理。

完整版教学

一、哈希函数在做什么

它是一个「压缩映射」：把巨大的、甚至无限的键空间（所有字符串、所有对象）压到有限的下标区间 [0, capacity)。压缩必然有信息损失，所以不同的键映射到同一个值是不可避免的——这就是冲突的根源。哈希函数能做的，是让这种碰撞尽量少、尽量均匀。

二、为什么均匀性是第一位的

假设哈希函数很烂，把 80% 的键都算到了同一个桶：那这个桶变成一条长链表，查找退化成 O(n)，哈希表名存实亡。反之若分布均匀，每个桶只有一两个元素，查找才是真正的 O(1)。均匀分布是哈希表 O(1) 性能的前提，也是评价哈希函数好坏最重要的指标。

三、雪崩效应：避免相似键扎堆

现实中的键往往长得很像：“user_1”、“user_2”，或 “ab”、“ac”。如果哈希函数对相似输入产生相似输出，这些键就会挤在相邻/相同的桶里。好的哈希函数有雪崩效应：哪怕只改一个字符/一位，哈希值也会面目全非，从而把相似键打散。这也是为什么很多哈希算法里有位移、异或、乘大质数这类「搅拌」操作。

Java HashMap 的扰动函数 h ^ (h >>> 16) 就是把高 16 位混入低 16 位，让高位也参与取模，减少只有低位相同就冲突的情况——本质是增强均匀性。

四、字符串常见的哈希做法

经典的多项式哈希（如 Java String.hashCode()）：

hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

用 31 这个奇质数当基数：它能让每个字符都影响结果、分布较均匀，且 31*i 可被 JVM 优化成 (i<<5)-i，计算快。选质数是为了减少与容量产生规律性冲突。

五、哈希函数 ≠ 加密哈希

面试要分清两类：

• 哈希表用的哈希函数：追求快 + 均匀，不要求安全，可逆没关系（如 hashCode）。
• 加密哈希（MD5、SHA-256）：追求抗碰撞、不可逆、防篡改，计算慢得多，用于签名/校验/密码存储，不适合当哈希表下标（太慢）。

用错场景是常见误区：拿 SHA-256 当 HashMap 的哈希函数纯属浪费。

六、常见误区与追问

哈希类型	目标	典型用途
普通哈希函数	快速、分布均匀	哈希表下标
加密哈希	抗碰撞、不可逆	签名、摘要、安全校验
一致性哈希	映射稳定、迁移少	分布式缓存/存储

记忆钩子：哈希表里的哈希函数第一目标是“快且均匀”，不是“安全不可逆”。不要把 hashCode 和 SHA-256 混成一类答案。

数字例子：容量为 16 时，如果某批 key 的 hash 低 4 位都相同，那么 hash & 15 后会全部进同一个桶；如果扰动函数能让高位信息混入低位，这批 key 才更可能散到不同桶。好哈希函数要让相似输入也产生明显不同的输出，这就是常说的雪崩效应。

• 误区：哈希函数只要结果唯一就行。 对哈希表来说更关键的是分布均匀和计算快；完全唯一通常不现实。
• 误区：哈希值相等就说明原始 key 相等。 哈希可能碰撞，最终还要用 equals 或原始比较确认。
• 误区：加密哈希越安全越适合 HashMap。 加密哈希计算更重，哈希表通常不需要不可逆安全性。
• 追问：为什么字符串哈希常乘一个质数？ 乘法能把字符顺序和历史结果混合，质数有助于降低某些周期性分布问题。
• 追问：雪崩效应是什么？ 输入很小变化导致输出多位变化，减少相似 key 聚集到相邻或相同桶。
• 追问：哈希函数差会带来什么后果？ 冲突增加，桶链变长或探测次数增加，平均 O(1) 会被破坏。

七、加强记忆

哈希函数把键映射成下标，好坏看四点：确定（同键同值）、均匀（少冲突，最关键）、快、雪崩（微小输入变化引起输出剧变，打散相似键）。它和加密哈希是两回事——前者求快求均匀，后者求安全求抗碰撞。均匀性决定哈希表会不会退化成 O(n)。