尧图网站开发 
一、从一个经典面试题说起在很多 Java 面试中面试官会忽然抛出一个看似简单却很难答深的问题「String 的 hashCode 方法里为什么选择 31 作为乘子」不少候选人能背出源码却说不清楚 31 背后的数学原理、工程权衡和历史渊源。有人回答「因为 31 是素数」有人回答「因为 31 * h 可以优化成 (h 5) - h」但很少有人能把这两个答案串成一个完整的逻辑链条为什么哈希乘子要选素数为什么素数里偏偏是 31而不是 33 或 37为什么这个选择在几十年后的今天仍然合理这篇文章不是简单罗列结论而是从一个字符串求哈希的原始需求出发逐步推导出「素数乘子」的必然性再解释「2 的 5 次方减 1」带来的性能红利最后用可运行的实验验证不同乘子的冲突率差异。读完之后你会发现31 这个数字是数学性质与计算机硬件特性达成的一次精妙妥协。一句话预告31 是一个素数保证了乘子与字符取值空间的互质关系从而让哈希值分布更均匀同时 31 32 - 1可以让乘法被编译器替换成一次左移和一次减法在现代 CPU 上这条优化路径又便宜又快。二者缺一31 都不会成为最终答案。二、先搞清楚 hashCode 到底在做什么在讨论「为什么是 31」之前必须先明确哈希码的用途。Java 中的 hashCode() 方法返回一个 int 值它的核心消费者是散列表例如 HashMap、HashSet、Hashtable。散列表的基本思路是把任意对象映射到一个固定范围的「桶」中查找时先算出桶下标再在桶内做少量比较。这个映射过程通常分为两步第一步调用对象的 hashCode() 得到一个 int 类型的原始哈希值。第二步通过类似(n - 1) hash的运算把 int 值映射到数组长度 n 的某个桶下标。所以 hashCode 的质量直接影响散列表的性能。如果大量对象都返回相同的 hashCode它们会挤进同一个桶原本期望 O(1) 的查找退化成 O(n) 的链表遍历甚至树遍历。反过来如果 hashCode 能把不同对象均匀地撒到整个 int 空间中每个桶里的元素数量就接近平均查找效率最优。Java 对 hashCode 有一个基础契约同一个对象在程序运行期间未被修改的情况下多次调用 hashCode() 必须返回相同的整数。两个对象根据 equals() 比较相等那么它们的 hashCode() 必须相等。两个对象根据 equals() 比较不相等不要求 hashCode() 一定不同但理想情况下应尽量不同以减少哈希冲突。换句话说「equals 相等则 hashCode 相等」是必须保证的硬约束而「equals 不相等时 hashCode 也不相等」只是一个尽力而为的性能目标。String 作为日常使用频率最高的键类型之一它的 hashCode 实现理所当然地被做成教科书级别的样例也正因为如此31 才频繁出现在面试题中。三、String.hashCode 源码逐行解读先看 JDK 8 中经典的 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; }这段代码的逻辑并不复杂但每一行都有讲究缓存字段 hashString 对象内部有一个private int hash;字段默认值为 0。第一次调用 hashCode() 时如果 hash 仍为 0 且字符串非空就执行完整计算并把结果缓存起来后续调用直接返回缓存值不再重复计算。这利用了 String 的不可变性是「空间换时间」的典型做法。hash 0 的判断细节注意条件是h 0 value.length 0。它用 0 作为「尚未计算」的哨兵值。一个潜在副作用是如果某个字符串的真实哈希值恰好等于 0那么每次调用都会重新计算一遍因为没有区分「没算过」和「算出来就是 0」。不过这种情况概率极低即使发生也只会带来一点重复计算不会产生错误。核心循环h 31 * h val[i];从第一个字符开始每一步把当前累加值乘以 31再加上当前字符的 Unicode 码点。char 与 Unicode在 JDK 9 之前的 String 内部用 char 数组存储 UTF-16 码元每个 char 的取值范围是 0 到 65535。JDK 9 之后改用 byte 数组配合 coder 区分 Latin-1 与 UTF-16但哈希算法保持等价结果不变。现在把这个循环展开假设字符串是abc对应字符码点分别是 97、98、99那么计算过程是初始 h 0第一步h 31 * 0 97 97第二步h 31 * 97 98 3105第三步h 31 * 3105 99 96354最终哈希值是一个很大的整数。如果把它写成多项式形式它等价于97 * 31² 98 * 31 99。这就是理解后续所有内容的钥匙——String 的 hashCode 本质上是一个以 31 为基数的多项式哈希。理解了这一点为什么乘子不能随意选择就显而易见了。四、为什么不能简单相加多项式哈希很多人会问为什么要把前一个结果乘以 31 再加字符为什么不干脆把所有字符的码点直接相加假设我们定义一种「求和哈希」int naiveHash(String s) { int h 0; for (char c : s.toCharArray()) { h h c; } return h; }这个实现虽然简单却有一个致命缺陷它完全丢失了字符的位置信息。ab和ba的求和结果都是 97 98 195stop、tops、post、opts这些字母相同但顺序不同的词也会全部碰撞。在自然语言中同字母异序词远比想象中常见这会让散列表的冲突率居高不下。多项式哈希的核心思想是给每个位置赋予不同的「权重」。把字符串看作一个 digit 序列最高位字符对应最大的幂最低位字符对应 31 的 0 次方。这样字符串s s₀ s₁ ... sₙ₋₁的哈希值就是hash s₀ * 31^(n-1) s₁ * 31^(n-2) ... sₙ₋₁ * 31^0只要基数大于字符的取值范围不同字符、不同位置的组合映射出的数值就几乎不会相同。位置信息被编码进了幂指数里所以ab会得到 97 * 31 98而ba会得到 98 * 31 97二者完全不同。这也是为什么这种算法在算法竞赛中被称为「Rolling Hash」——它不仅能区分顺序还能在 O(1) 时间内从子串 [L, R] 的哈希值推出相邻子串的哈希值用于字符串匹配、最长公共子串等问题。Java 的 String.hashCode 正是同一个思想在标准库中的落地。五、乘子不能太小也不能乱选选择多项式哈希时乘子也就是基数的大小非常关键。如果乘子太小会导致高位权重衰减不足短字符串和长字符串的哈希值分布范围差距过大。例如把乘子设为 1就退化成了求和哈希把乘子设为 2权重增长仍然太慢a、aa、aaa的哈希值分别是 97、97 * 2 97 291、97 2 * 291 679分布得太密集而且无法利用 int 的完整 32 位空间。反之如果乘子太大短字符串就能迅速触达 int 上界并发生溢出。Java 的 int 加减乘默认按 32 位有符号数运算溢出时直接截断相当于对结果自动取模 2³²。这一步「溢出即取模」其实是设计的一部分而不是缺陷因为它天然把散列表桶下标的取模操作和哈希值生成合并了。把乘子选在 30 到 40 这个量级就显得十分合理它既能让三五个字符的字符串快速把哈希值拉高到百万、千万级别充分发挥 32 位空间又不会因为权重爆炸而过早失去粒度。但仅靠「大小合适」还不够乘子本身的数学性质——是否为素数、与 2 的幂的关系——才是决定分布均匀性的关键。六、素数乘子的真正意义「乘子选素数」是哈希设计中的一条经验法则但它背后的原因需要拆开看。多项式哈希中每个字符的贡献是char * 31^k而字符的取值范围是 0 到 65535。如果这个乘子与字符的取值范围存在公因数就会出现周期性问题让某些位置对哈希结果产生系统性的偏置。举一个最直观的反例如果把乘子选成 32也就是 2 的 5 次方那么这个多项式中所有 k ≥ 5 的项32^k都包含因数 32它们在二进制下的低 5 位永远是 0。这意味着字符串的第 6 个字符及之后的所有字符对哈希值低 5 位的贡献恒为 0低 5 位完全由最后 5 个字符决定。当散列表长度为 32 的倍数时桶下标只取决于哈希值低几位于是长字符串的前缀信息被完全丢弃大量共享后缀的字符串会撞进同一桶。素数没有除 1 和自身以外的因数因此不可能与字符的常见取值范围、数组长度等产生这类共振。一个素数乘子能让每个字符的贡献更好地混合进结果的每一位这是它分布均匀的根本原因。当然「素数」只是必要条件而非充分条件——还需要结合溢出取模的模数 2³² 来看31 是奇数与 2³² 互质这意味着以 31 为基的多项式在模 2³² 下形成一个完整的循环结构不会陷入短周期。另一个经典做法是用大素数做模数例如竞赛中的 1e9 7 或 1e9 9。Java 的标准库则选择「用 31 做乘子、用 2³² 做隐式模数」用硬件溢出代替显式取模。这两条路线殊途同归核心都在于让乘子和模数互质。七、31 的独特数学身份在众多素数中31 有一个非同寻常的身份它恰好等于 2⁵ − 1也就是 32 减 1。这类形如 2^p − 1 的数在数学上被称为「梅森数」Mersenne number当它本身也是素数时就称为「梅森素数」。这个身份带来一个立即可用的工程优化31 * h (32 - 1) * h 32 * h - h (h 5) - h在二进制层面乘以 32 等价于左移 5 位因为左移 1 位是乘以 2左移 5 位就是乘以 32。于是「乘以 31」可以被改写为「左移 5 位再减去自身」。相比整数乘法指令现代 CPU 上的移位和加减指令通常更便宜延迟更短、吞吐更高。更关键的是编译器在做优化时能自动识别这种模式即使源码里写的是31 * h生成的机器码也可能已经是移位加减法。那么为什么是 2⁵ − 1而不是 2³ − 1 7或者 2⁷ − 1 127 呢这里就回到了「大小合适」的问题7 太小短字符串的哈希值增长太慢碰撞明显偏多127 是 2⁷ − 1虽然也是梅森素数但作为字符串哈希乘子偏大短字符串就会快速逼近 int 上限且实际测试中其分布并不优于 3131 恰好处在一个「乘以几次就覆盖整个 32 位空间」的甜点区间。31 同时满足三个条件是素数、等于 2 的幂减 1、大小适中。这三条共同锁定了它作为 String 哈希乘子的资格但还差最后一环——真实的实验数据以及一位关键人物的背书。八、JVM 如何把乘法变成移位和减法「乘以 31 可以优化成移位和减法」这句话值得展开成一次从 Java 源码到机器指令的旅程。在 Java 层面31 * h是一次imul有符号整数乘法运算。即时编译器JIT的 C2 编译器在做强度削减strength reduction时会识别出「乘以一个可以表示成 2^k ± c 的常数」的情形并将其转换为移位与加减组合。对于 31 这类 2⁵ − 1 形式的乘数转换非常直接; 伪汇编示意 mov eax, h ; 把 h 加载到 eax shl eax, 5 ; 左移 5 位等价于 h * 32 sub eax, h ; 减去 h等价于 h * 31不过需要诚实说明在 x86 架构上整数乘法指令imul的代价并没有想象中那么高现代 CPU 的乘法单元延迟通常只有 3 个周期左右而移位是 1 个周期加法/减法是 1 个周期。左移加减法合计约 2 个周期确实比乘法略快。对于哈希计算这种会在 HashMap 的每一次 put、get、resize 中被反复调用的热点路径一点微观延迟的累积也很可观。31 的选择让这条热点路径在几十年前的 CPU 上获得了实实在在的收益而在今天的 CPU 上依然不亏。所以「31 的性能优势」并不是一个过时传说而是从算法层面就为编译器优化预留了空间。这种「把数学性质变成机器指令红利」的设计意识正是优秀标准库代码的体现。九、Joshua Bloch 的官方解释关于 31 的选择最权威的出处来自 Java 集合框架与部分核心库的设计者 Joshua Bloch。他在经典著作《Effective Java》中讨论「覆盖 equals 时总要覆盖 hashCode」这一条目时专门解释了 String.hashCode 中乘子的由来。大意如下之所以选择 31是因为它是一个奇素数。相比偶数用奇数与溢出即隐式的 2³² 取模结合能更好地保留信息。同时31 有一个很好的性质乘法可以被替换成移位和减法在某些架构上能得到更优的性能。虽然现代编译器和硬件会做这类优化但 31 * i 可以用 (i 5) - i 表达这是一个不错的选择。这段解释包含了三个要点一是奇素数二是与溢出机制配合的信息保留三是移位减法优化。值得注意的是Bloch 并没有宣称 31 是所有乘子中的「全局最优」而是将它描述为一个在分布与性能之间取得良好平衡的工程选择。这个措辞很重要——它告诉我们哈希乘子的选择从来不是纯粹的数学最优解问题而是在约束条件下寻找足够好的解。一个常被引用的轶事是Bloch 曾表示如果重新设计他也可能选择其他乘子因为 31 在分布上并非碾压所有对手但它足够好且已被广泛接受。标准库一旦发布字符串哈希值就变成了事实上的公共协议轻易不能修改否则会破坏已经序列化存储的哈希值、依赖特定 hashCode 的第三方代码以及大量既有数据。这种「一经选定极难更改」的特性也反过来要求当初的选择必须足够稳健。十、经典字符串哈希算法中的 31 与 3331 并不是孤例。在通用字符串哈希算法的谱系中31、33、131 等「小奇数」反复出现形成了一条清晰的设计传统。了解这些兄弟算法有助于理解 31 的位置。几个知名度较高的字符串哈希算法如下算法核心乘子特点BKDRHash31、131、1313、13131 等Brian Kernighan 与 Dennis Ritchie 的《C 程序设计语言》中出现乘子取 31 或 131DJB233Daniel J. Bernstein 设计初始值 5381乘子 33SDBMHash65599多用于数据库分布良好APHash0x9E3779B9 等Arash Partow 设计的变体RSHash63689 等Robert Sedgwicks 提出的简单哈希JS Hash1315423911Justin Sobel 设计乘子很大可以看到BKDRHash 直接用 31 做乘子DJB2 用 33。33 与 31 一样是奇素数大小也接近两者在实际冲突测试中的表现通常处于同一档次差异很小。既然 33 的分布也不差为什么 Java 不选 33 而选 31关键差异就在上一节提到的性质33 32 1虽然也能写成 (h 5) h但它是「左移加自身」需要一次加法31 是「左移减自身」。从数学上看两者对称但从进位、溢出和混合效果看减法形式在某些测试中略优且 31 是梅森素数、33 不是。两者差别细微最终胜出的 31 同时兼顾了「梅森素数 移位减法」两个标签。这些经典算法的共同点是乘子取「接近 2 的幂的奇素数」既保证与 2³² 模数互质带来的分布均匀性又保留了移位优化的可能。31 正是这条谱系中的典型代表。十一、动手实验换掉 31 会发生什么理论讲得再多不如用代码说话。下面写一个完整的 Java 实验程序随机生成一批长度不同的字符串分别用 31、32、33、37、39、41、127 等乘子计算哈希值然后统计放入一个固定长度桶数组后的冲突情况。冲突定义为「不同字符串落入同一个桶」的事件数。import java.util.Random; public class HashMultiplierExperiment { static final String ALPHABET abcdefghijklmnopqrstuvwxyz0123456789; static final int SAMPLE_COUNT 200_000; static final int BUCKET_COUNT 1 16; // 65536 个桶 public static void main(String[] args) { int[] multipliers {31, 32, 33, 37, 39, 41, 127}; System.out.printf(%-8s %s%n, 乘子, 冲突次数); for (int m : multipliers) { int collisions measureCollisions(m); System.out.printf(%-8d %d%n, m, collisions); } } static int measureCollisions(int multiplier) { int[] buckets new int[BUCKET_COUNT]; int collisions 0; Random random new Random(42); for (int n 0; n SAMPLE_COUNT; n) { String s randomString(random); int h polynomialHash(s, multiplier); int bucket h (BUCKET_COUNT - 1); if (buckets[bucket] ! 0) { collisions; } buckets[bucket]; } return collisions; } static String randomString(Random random) { int len 3 random.nextInt(10); StringBuilder sb new StringBuilder(len); for (int i 0; i len; i) { sb.append(ALPHABET.charAt(random.nextInt(ALPHABET.length()))); } return sb.toString(); } static int polynomialHash(String s, int multiplier) { int h 0; for (int i 0; i s.length(); i) { h multiplier * h s.charAt(i); } return h; } }这个实验刻意把桶数量设为 65536也就是 2¹⁶让桶下标完全由哈希值的低 16 位决定。这样能非常直观地暴露「偶数乘子导致低位信息丢失」的问题。样例字符串长度从 3 到 12 不等模拟真实使用中短键为主的场景。随机种子固定为 42保证结果可复现。需要说明的是这个实验的「冲突次数」统计的是发生碰撞的桶数量不是碰撞对的总数。它足以反映不同乘子下哈希分布的相对优劣。运行一次典型输出会非常有说服力我们将在下一节详细解读。十二、实验结果与冲突率分析在 20 万条随机字符串、65536 个桶的设定下一个理想的均匀哈希函数大约会让每个桶平均容纳 3 个元素几乎所有桶都会被占用因此「冲突次数」接近桶总数 65536 才是正常表现。真正值得关注的是那些明显低于这个值的乘子——它们说明大量字符串挤在了少数桶里分布严重不均。实验的核心观察如下32 表现得最差因为 32 是 2 的 5 次方字符串第 6 个字符之后的贡献在低 5 位全部为零。当桶数取 2 的幂时桶下标只由低 16 位决定于是所有长度超过 5 的字符串的低位哈希严重同质化冲突数量会显著低于理想值大量桶被浪费。39 是一个很有教育意义的样本39 3 × 13它不是素数。虽然它是奇数不会像 32 那样直接丢失低位但由于与字符码点取值范围存在结构上的关联其分布也略逊于同量级的素数乘子。31、33、37、41 这些奇素数的表现非常接近它们的冲突数量都贴近理想值彼此之间的差异常常只有千分之几。这说明「奇素数」这个条件一旦满足具体选 31 还是 37 对分布的影响很小。127 作为 2⁷ − 1 的梅森素数分布同样优秀但它在字符串较短时就把哈希值推得过高且 127 不能像 31 那样在「前几步就有效混合低位」与「避免过早饱和」之间取得完美平衡。这张对比表把结论浓缩得非常清楚分布质量的决定性因素是「奇数且尽量为素数」而 31 在满足这个条件的同时还附带「2⁵ − 1 的移位优化」。换句话说31 在众多同样「分布良好」的候选者中靠性能优势脱颖而出而在众多「性能好优化」的候选者中靠素数的分布优势胜出。它是两个维度的交集。十三、从数论角度看乘法哈希如果要严谨一些31 的优良性质可以从数论上给出解释。考虑一个简化模型哈希函数是h(x) a * x mod m其中 a 是乘子x 是输入字符码点m 是模数。为了让所有可能的 x 都能被均匀映射我们希望 a 与 m 互质。更严格地说当 a 与 m 互质时映射x ↦ a * x mod m是模 m 剩余类环上的一个置换它把 0 到 m−1 的每个值都一一映射不会把两个不同 x 折叠到同一个值。Java 的 String.hashCode 不是简单的a * x而是迭代多项式h a * h c。把它展开每个字符 cᵢ 的系数是 a^(n−1−i)。如果 a 与模数 2³² 互质等价于 a 是奇数那么这些系数 a^k 在模 2³² 下形成一个遍历所有单位的循环不会过早重复。这使得不同位置的字符以不同周期混合进结果避免「位置 k 和位置 kp 总是同权」的灾难。相反如果 a 是偶数则 a 与 2³² 有公因数 2系数 a^k 会迅速共享越来越大的 2 的幂因子低位信息被系统性抹掉。这从数学上解释了上一节实验中 32 的糟糕表现。为什么不仅要求奇数还希望是素数在模 2³² 的环里「奇数」已经足以保证可逆性素数在纯模 2³² 意义上的额外作用并不像「模大素数」时那么关键但素数依然有价值它排除了 a 与字符码点空间或其他结构产生隐秘公因数的可能同时在历史实践中被大量统计验证为分布优良。工程上我们往往先靠数论排除明显错误选项再靠实验在合格选项里做最终筛选。十四、为什么是 31而不是 33 或 37经过前面的铺垫现在可以正面回答这个对比问题了。33 和 37 都是奇素数分布表现与 31 不相上下但它们各自缺少 31 具备的那个决定性优势。先说 33。33 32 1虽然可以写成 (h 5) h但它不是梅森素数且加法形式意味着每次迭代需要一次左移加一次加法。31 32 − 1 则是 (h 5) − h。两者成本几乎一样但在溢出回绕时减法与加法的低位进位行为略有不同31 的减法形式在部分测试里拥有更均匀的混合效果。更重要的是31 是梅森素数这个「2 的幂减 1 且为素数」的双重身份让它在数学与硬件两个维度同时得到背书。再说 37。37 是素数但它不能表示为 2 的幂减 1 或加 1 的简单形式乘 37 无法用单次移位优化需要真正的乘法指令或更复杂的一系列移位加法组合。分布上它并不比 31 更好性能上却略逊自然落选。41、47、61 等其他奇素数也是类似逻辑。31 之所以被选中本质上是一场多目标优化目标一哈希分布均匀要求乘子为奇素数目标二计算代价低要求乘子能写成 2^k ± 1目标三权重增长适中要求乘子数值落在短字符串也能充分利用 32 位空间的区间31 正好同时满足这三个目标。它不是「分布最好」的乘子也不是「计算最快」的乘子但它是这个多目标问题的帕累托最优解之一并且被一个在历史上拥有极高影响力的标准库固化了下来。这就是工程选择的真实面貌不求单项极致而求整体平衡。十五、hashCode 与 equals 的契约理解 31 之后有必要回到它服务的对象equals 与 hashCode 的契约。很多初学者会问「是不是 hashCode 相等两个对象就相等」答案是否定的。哈希值相等只是「可能相等」的必要条件最终必须由 equals 做精确判定。两个不同字符串的 hashCode 可能相同这是哈希冲突无法也无需完全避免但两个 equals 相等的字符串必须有相同的 hashCode。String 类对这两个方法做了严格一致的实现equals 逐字符比较内容hashCode 基于同样的字符序列计算。只要两个字符串内容相同它们必然经过相同的多项式计算过程得到相同的哈希值满足契约。这给自定义类的实现提供了模板当你重写 equals 时必须同步重写 hashCode否则把对象放进 HashMap 或 HashSet 后会出现诡异的「找不到元素」问题。正确做法通常是选取所有参与 equals 比较的字段用一个与 31 类似的奇素数做多项式混合。Bloch 在《Effective Java》中给出的建议公式正是int result 17; result 31 * result field1.hashCode(); result 31 * result field2.hashCode();这里的 17 和 31 不是随意写的17 作为初始值提供非零起点31 继续充当那个经过验证的奇素数乘子。这个模式与 String.hashCode 一脉相承可以看成是标准库经验向应用代码的扩散。十六、字符串不可变性与哈希缓存String.hashCode 能放心地缓存结果前提是 String 不可变。Java 的 String 对象一旦创建其内部 value 数组就不能被外部修改在 JDK 9 及之后是 byte 数组同样不可变因此哈希值可以安全地在第一次计算后保存之后每次调用直接返回。这种设计带来两个直接收益重复哈希零成本同一个字符串作为 HashMap 的键被查找多次时第二次开始的 hashCode 调用都是 O(1) 的字段读取而不是 O(n) 的字符遍历。并发安全即使多个线程同时首次调用 hashCode各自计算出的值也必然相同缓存写入只是幂等的重复赋值不会产生可见性问题。JDK 后续版本在细节上做了一些并发加固但逻辑不变。不可变性还让 String 成为散列表最理想的键类型equals 结果永不改变hashCode 结果永不改变整个散列表的完整性在键的生命周期内都能保证。如果用可变对象做键一旦键的内容在插入后被修改它的桶位置就失效了元素会「丢失」在错误的桶里。这也解释了为什么标准实践强烈建议用 String、Integer 等不可变类型做键。十七、常见误区与面试高频追问围绕 31 和 String.hashCode有几个频繁出现的误解和追问值得一一澄清。误区一31 是「最优」乘子。严格来说不存在对所有字符串集合都最优的乘子。31 是在「分布质量 计算成本」的权衡下足够好的选择并非数学意义上的全局最优。不同数据集的字符串分布不同或许某个特定数据集在乘子 37 下冲突更少但这不构成改变标准库的理由。误区二hashCode 会溢出导致错误。int 溢出在这里是特性而非缺陷。Java 的 int 运算按 32 位回绕恰好实现了模 2³² 的效果。只要 equals 与 hashCode 的实现保持一致溢出产生的负数或「回绕」都不会破坏正确性。误区三hashCode 返回负数不正常。int 是有符号的哈希值完全可能是负数。这没有影响因为后续映射桶下标时会用位运算或取模把符号位也纳入计算例如(n - 1) hash对负数同样生效。追问一能举个 String 哈希冲突的例子吗经典例子是Aa与BB。A是 65a是 97B是 66可以算出Aa的哈希值是 65 * 31 97 2112BB的哈希值是 66 * 31 66 2112二者相等。这说明冲突无法避免但概率和分布都在可接受范围内。追问二既然冲突难免Java 如何兜底HashMap 在同一个桶内用链表或红黑树存储冲突元素查找时先比 hashCode 快速筛选再用 equals 精确确认所以即使 hashCode 冲突正确性依然由 equals 保证。追问三为什么 JDK 不改成分布更好的乘子因为 String.hashCode 的结果已经是事实标准序列化数据、第三方库的缓存、分布式系统的一致性哈希等都可能依赖它。修改意味着大范围兼容性破坏而 31 带来的分布问题在实际业务中几乎不可感知不值得为此付出巨大迁移成本。十八、总结与延伸思考回到最初的问题「为什么 String hashCode 方法选择数字 31 作为乘子」答案可以浓缩成一句话31 是一个大小适中的奇素数能与 Java 的 int 溢出隐式模数 2³² 良好配合让多项式哈希的分布足够均匀同时它等于 2⁵ − 1使 31 * h 可以被编译器优化成 (h 5) - h在性能上占据优势。分布与性能的双重合格加上标准库一经发布便难以更改的路径依赖让 31 成为最终答案。如果只记得一句话请记住31 是素数与硬件友好的交集。这个选择背后其实隐藏着软件设计中反复出现的规律好的实现不是追求某个维度的极致而是在正确性约束下用数学性质换取工程收益。String.hashCode 的 31、HashMap 的 2 的幂容量、各种经典哈希算法的奇素数乘子都是同一种思维在不同场景下的投影。延伸下去还有很多值得深入的方向你可以研究开放寻址法与链地址法对哈希函数质量的不同要求可以阅读 William Pugh 的跳跃表、Google Guava 对哈希的封装也可以去算法竞赛世界了解双哈希、滚动哈希和大素数取模的技巧。理解了 31就拿到了进入这些领域的一张入场券。对于正在准备面试的读者建议把这条逻辑链完整走一遍从「为什么需要乘子」到「为什么是素数」再到「为什么是 31 而不是 33 或 37」最后到「改成别的数会发生什么」。当你能够不查资料地讲出这四步这个问题就不再是背诵题而是展示你技术深度的机会了。 
一、从一个经典面试题说起在很多 Java 面试中面试官会忽然抛出一个看似简单却很难答深的问题「String 的 hashCode 方法里为什么选择 31 作为乘子」不少候选人能背出源码却说不清楚 31 背后的数学原理、工程权衡和历史渊源。有人回答「因为 31 是素数」有人回答「因为 31 * h 可以优化成 (h 5) - h」但很少有人能把这两个答案串成一个完整的逻辑链条为什么哈希乘子要选素数为什么素数里偏偏是 31而不是 33 或 37为什么这个选择在几十年后的今天仍然合理这篇文章不是简单罗列结论而是从一个字符串求哈希的原始需求出发逐步推导出「素数乘子」的必然性再解释「2 的 5 次方减 1」带来的性能红利最后用可运行的实验验证不同乘子的冲突率差异。读完之后你会发现31 这个数字是数学性质与计算机硬件特性达成的一次精妙妥协。一句话预告31 是一个素数保证了乘子与字符取值空间的互质关系从而让哈希值分布更均匀同时 31 32 - 1可以让乘法被编译器替换成一次左移和一次减法在现代 CPU 上这条优化路径又便宜又快。二者缺一31 都不会成为最终答案。二、先搞清楚 hashCode 到底在做什么在讨论「为什么是 31」之前必须先明确哈希码的用途。Java 中的 hashCode() 方法返回一个 int 值它的核心消费者是散列表例如 HashMap、HashSet、Hashtable。散列表的基本思路是把任意对象映射到一个固定范围的「桶」中查找时先算出桶下标再在桶内做少量比较。这个映射过程通常分为两步第一步调用对象的 hashCode() 得到一个 int 类型的原始哈希值。第二步通过类似(n - 1) hash的运算把 int 值映射到数组长度 n 的某个桶下标。所以 hashCode 的质量直接影响散列表的性能。如果大量对象都返回相同的 hashCode它们会挤进同一个桶原本期望 O(1) 的查找退化成 O(n) 的链表遍历甚至树遍历。反过来如果 hashCode 能把不同对象均匀地撒到整个 int 空间中每个桶里的元素数量就接近平均查找效率最优。Java 对 hashCode 有一个基础契约同一个对象在程序运行期间未被修改的情况下多次调用 hashCode() 必须返回相同的整数。两个对象根据 equals() 比较相等那么它们的 hashCode() 必须相等。两个对象根据 equals() 比较不相等不要求 hashCode() 一定不同但理想情况下应尽量不同以减少哈希冲突。换句话说「equals 相等则 hashCode 相等」是必须保证的硬约束而「equals 不相等时 hashCode 也不相等」只是一个尽力而为的性能目标。String 作为日常使用频率最高的键类型之一它的 hashCode 实现理所当然地被做成教科书级别的样例也正因为如此31 才频繁出现在面试题中。三、String.hashCode 源码逐行解读先看 JDK 8 中经典的 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; }这段代码的逻辑并不复杂但每一行都有讲究缓存字段 hashString 对象内部有一个private int hash;字段默认值为 0。第一次调用 hashCode() 时如果 hash 仍为 0 且字符串非空就执行完整计算并把结果缓存起来后续调用直接返回缓存值不再重复计算。这利用了 String 的不可变性是「空间换时间」的典型做法。hash 0 的判断细节注意条件是h 0 value.length 0。它用 0 作为「尚未计算」的哨兵值。一个潜在副作用是如果某个字符串的真实哈希值恰好等于 0那么每次调用都会重新计算一遍因为没有区分「没算过」和「算出来就是 0」。不过这种情况概率极低即使发生也只会带来一点重复计算不会产生错误。核心循环h 31 * h val[i];从第一个字符开始每一步把当前累加值乘以 31再加上当前字符的 Unicode 码点。char 与 Unicode在 JDK 9 之前的 String 内部用 char 数组存储 UTF-16 码元每个 char 的取值范围是 0 到 65535。JDK 9 之后改用 byte 数组配合 coder 区分 Latin-1 与 UTF-16但哈希算法保持等价结果不变。现在把这个循环展开假设字符串是abc对应字符码点分别是 97、98、99那么计算过程是初始 h 0第一步h 31 * 0 97 97第二步h 31 * 97 98 3105第三步h 31 * 3105 99 96354最终哈希值是一个很大的整数。如果把它写成多项式形式它等价于97 * 31² 98 * 31 99。这就是理解后续所有内容的钥匙——String 的 hashCode 本质上是一个以 31 为基数的多项式哈希。理解了这一点为什么乘子不能随意选择就显而易见了。四、为什么不能简单相加多项式哈希很多人会问为什么要把前一个结果乘以 31 再加字符为什么不干脆把所有字符的码点直接相加假设我们定义一种「求和哈希」int naiveHash(String s) { int h 0; for (char c : s.toCharArray()) { h h c; } return h; }这个实现虽然简单却有一个致命缺陷它完全丢失了字符的位置信息。ab和ba的求和结果都是 97 98 195stop、tops、post、opts这些字母相同但顺序不同的词也会全部碰撞。在自然语言中同字母异序词远比想象中常见这会让散列表的冲突率居高不下。多项式哈希的核心思想是给每个位置赋予不同的「权重」。把字符串看作一个 digit 序列最高位字符对应最大的幂最低位字符对应 31 的 0 次方。这样字符串s s₀ s₁ ... sₙ₋₁的哈希值就是hash s₀ * 31^(n-1) s₁ * 31^(n-2) ... sₙ₋₁ * 31^0只要基数大于字符的取值范围不同字符、不同位置的组合映射出的数值就几乎不会相同。位置信息被编码进了幂指数里所以ab会得到 97 * 31 98而ba会得到 98 * 31 97二者完全不同。这也是为什么这种算法在算法竞赛中被称为「Rolling Hash」——它不仅能区分顺序还能在 O(1) 时间内从子串 [L, R] 的哈希值推出相邻子串的哈希值用于字符串匹配、最长公共子串等问题。Java 的 String.hashCode 正是同一个思想在标准库中的落地。五、乘子不能太小也不能乱选选择多项式哈希时乘子也就是基数的大小非常关键。如果乘子太小会导致高位权重衰减不足短字符串和长字符串的哈希值分布范围差距过大。例如把乘子设为 1就退化成了求和哈希把乘子设为 2权重增长仍然太慢a、aa、aaa的哈希值分别是 97、97 * 2 97 291、97 2 * 291 679分布得太密集而且无法利用 int 的完整 32 位空间。反之如果乘子太大短字符串就能迅速触达 int 上界并发生溢出。Java 的 int 加减乘默认按 32 位有符号数运算溢出时直接截断相当于对结果自动取模 2³²。这一步「溢出即取模」其实是设计的一部分而不是缺陷因为它天然把散列表桶下标的取模操作和哈希值生成合并了。把乘子选在 30 到 40 这个量级就显得十分合理它既能让三五个字符的字符串快速把哈希值拉高到百万、千万级别充分发挥 32 位空间又不会因为权重爆炸而过早失去粒度。但仅靠「大小合适」还不够乘子本身的数学性质——是否为素数、与 2 的幂的关系——才是决定分布均匀性的关键。六、素数乘子的真正意义「乘子选素数」是哈希设计中的一条经验法则但它背后的原因需要拆开看。多项式哈希中每个字符的贡献是char * 31^k而字符的取值范围是 0 到 65535。如果这个乘子与字符的取值范围存在公因数就会出现周期性问题让某些位置对哈希结果产生系统性的偏置。举一个最直观的反例如果把乘子选成 32也就是 2 的 5 次方那么这个多项式中所有 k ≥ 5 的项32^k都包含因数 32它们在二进制下的低 5 位永远是 0。这意味着字符串的第 6 个字符及之后的所有字符对哈希值低 5 位的贡献恒为 0低 5 位完全由最后 5 个字符决定。当散列表长度为 32 的倍数时桶下标只取决于哈希值低几位于是长字符串的前缀信息被完全丢弃大量共享后缀的字符串会撞进同一桶。素数没有除 1 和自身以外的因数因此不可能与字符的常见取值范围、数组长度等产生这类共振。一个素数乘子能让每个字符的贡献更好地混合进结果的每一位这是它分布均匀的根本原因。当然「素数」只是必要条件而非充分条件——还需要结合溢出取模的模数 2³² 来看31 是奇数与 2³² 互质这意味着以 31 为基的多项式在模 2³² 下形成一个完整的循环结构不会陷入短周期。另一个经典做法是用大素数做模数例如竞赛中的 1e9 7 或 1e9 9。Java 的标准库则选择「用 31 做乘子、用 2³² 做隐式模数」用硬件溢出代替显式取模。这两条路线殊途同归核心都在于让乘子和模数互质。七、31 的独特数学身份在众多素数中31 有一个非同寻常的身份它恰好等于 2⁵ − 1也就是 32 减 1。这类形如 2^p − 1 的数在数学上被称为「梅森数」Mersenne number当它本身也是素数时就称为「梅森素数」。这个身份带来一个立即可用的工程优化31 * h (32 - 1) * h 32 * h - h (h 5) - h在二进制层面乘以 32 等价于左移 5 位因为左移 1 位是乘以 2左移 5 位就是乘以 32。于是「乘以 31」可以被改写为「左移 5 位再减去自身」。相比整数乘法指令现代 CPU 上的移位和加减指令通常更便宜延迟更短、吞吐更高。更关键的是编译器在做优化时能自动识别这种模式即使源码里写的是31 * h生成的机器码也可能已经是移位加减法。那么为什么是 2⁵ − 1而不是 2³ − 1 7或者 2⁷ − 1 127 呢这里就回到了「大小合适」的问题7 太小短字符串的哈希值增长太慢碰撞明显偏多127 是 2⁷ − 1虽然也是梅森素数但作为字符串哈希乘子偏大短字符串就会快速逼近 int 上限且实际测试中其分布并不优于 3131 恰好处在一个「乘以几次就覆盖整个 32 位空间」的甜点区间。31 同时满足三个条件是素数、等于 2 的幂减 1、大小适中。这三条共同锁定了它作为 String 哈希乘子的资格但还差最后一环——真实的实验数据以及一位关键人物的背书。八、JVM 如何把乘法变成移位和减法「乘以 31 可以优化成移位和减法」这句话值得展开成一次从 Java 源码到机器指令的旅程。在 Java 层面31 * h是一次imul有符号整数乘法运算。即时编译器JIT的 C2 编译器在做强度削减strength reduction时会识别出「乘以一个可以表示成 2^k ± c 的常数」的情形并将其转换为移位与加减组合。对于 31 这类 2⁵ − 1 形式的乘数转换非常直接; 伪汇编示意 mov eax, h ; 把 h 加载到 eax shl eax, 5 ; 左移 5 位等价于 h * 32 sub eax, h ; 减去 h等价于 h * 31不过需要诚实说明在 x86 架构上整数乘法指令imul的代价并没有想象中那么高现代 CPU 的乘法单元延迟通常只有 3 个周期左右而移位是 1 个周期加法/减法是 1 个周期。左移加减法合计约 2 个周期确实比乘法略快。对于哈希计算这种会在 HashMap 的每一次 put、get、resize 中被反复调用的热点路径一点微观延迟的累积也很可观。31 的选择让这条热点路径在几十年前的 CPU 上获得了实实在在的收益而在今天的 CPU 上依然不亏。所以「31 的性能优势」并不是一个过时传说而是从算法层面就为编译器优化预留了空间。这种「把数学性质变成机器指令红利」的设计意识正是优秀标准库代码的体现。九、Joshua Bloch 的官方解释关于 31 的选择最权威的出处来自 Java 集合框架与部分核心库的设计者 Joshua Bloch。他在经典著作《Effective Java》中讨论「覆盖 equals 时总要覆盖 hashCode」这一条目时专门解释了 String.hashCode 中乘子的由来。大意如下之所以选择 31是因为它是一个奇素数。相比偶数用奇数与溢出即隐式的 2³² 取模结合能更好地保留信息。同时31 有一个很好的性质乘法可以被替换成移位和减法在某些架构上能得到更优的性能。虽然现代编译器和硬件会做这类优化但 31 * i 可以用 (i 5) - i 表达这是一个不错的选择。这段解释包含了三个要点一是奇素数二是与溢出机制配合的信息保留三是移位减法优化。值得注意的是Bloch 并没有宣称 31 是所有乘子中的「全局最优」而是将它描述为一个在分布与性能之间取得良好平衡的工程选择。这个措辞很重要——它告诉我们哈希乘子的选择从来不是纯粹的数学最优解问题而是在约束条件下寻找足够好的解。一个常被引用的轶事是Bloch 曾表示如果重新设计他也可能选择其他乘子因为 31 在分布上并非碾压所有对手但它足够好且已被广泛接受。标准库一旦发布字符串哈希值就变成了事实上的公共协议轻易不能修改否则会破坏已经序列化存储的哈希值、依赖特定 hashCode 的第三方代码以及大量既有数据。这种「一经选定极难更改」的特性也反过来要求当初的选择必须足够稳健。十、经典字符串哈希算法中的 31 与 3331 并不是孤例。在通用字符串哈希算法的谱系中31、33、131 等「小奇数」反复出现形成了一条清晰的设计传统。了解这些兄弟算法有助于理解 31 的位置。几个知名度较高的字符串哈希算法如下算法核心乘子特点BKDRHash31、131、1313、13131 等Brian Kernighan 与 Dennis Ritchie 的《C 程序设计语言》中出现乘子取 31 或 131DJB233Daniel J. Bernstein 设计初始值 5381乘子 33SDBMHash65599多用于数据库分布良好APHash0x9E3779B9 等Arash Partow 设计的变体RSHash63689 等Robert Sedgwicks 提出的简单哈希JS Hash1315423911Justin Sobel 设计乘子很大可以看到BKDRHash 直接用 31 做乘子DJB2 用 33。33 与 31 一样是奇素数大小也接近两者在实际冲突测试中的表现通常处于同一档次差异很小。既然 33 的分布也不差为什么 Java 不选 33 而选 31关键差异就在上一节提到的性质33 32 1虽然也能写成 (h 5) h但它是「左移加自身」需要一次加法31 是「左移减自身」。从数学上看两者对称但从进位、溢出和混合效果看减法形式在某些测试中略优且 31 是梅森素数、33 不是。两者差别细微最终胜出的 31 同时兼顾了「梅森素数 移位减法」两个标签。这些经典算法的共同点是乘子取「接近 2 的幂的奇素数」既保证与 2³² 模数互质带来的分布均匀性又保留了移位优化的可能。31 正是这条谱系中的典型代表。十一、动手实验换掉 31 会发生什么理论讲得再多不如用代码说话。下面写一个完整的 Java 实验程序随机生成一批长度不同的字符串分别用 31、32、33、37、39、41、127 等乘子计算哈希值然后统计放入一个固定长度桶数组后的冲突情况。冲突定义为「不同字符串落入同一个桶」的事件数。import java.util.Random; public class HashMultiplierExperiment { static final String ALPHABET abcdefghijklmnopqrstuvwxyz0123456789; static final int SAMPLE_COUNT 200_000; static final int BUCKET_COUNT 1 16; // 65536 个桶 public static void main(String[] args) { int[] multipliers {31, 32, 33, 37, 39, 41, 127}; System.out.printf(%-8s %s%n, 乘子, 冲突次数); for (int m : multipliers) { int collisions measureCollisions(m); System.out.printf(%-8d %d%n, m, collisions); } } static int measureCollisions(int multiplier) { int[] buckets new int[BUCKET_COUNT]; int collisions 0; Random random new Random(42); for (int n 0; n SAMPLE_COUNT; n) { String s randomString(random); int h polynomialHash(s, multiplier); int bucket h (BUCKET_COUNT - 1); if (buckets[bucket] ! 0) { collisions; } buckets[bucket]; } return collisions; } static String randomString(Random random) { int len 3 random.nextInt(10); StringBuilder sb new StringBuilder(len); for (int i 0; i len; i) { sb.append(ALPHABET.charAt(random.nextInt(ALPHABET.length()))); } return sb.toString(); } static int polynomialHash(String s, int multiplier) { int h 0; for (int i 0; i s.length(); i) { h multiplier * h s.charAt(i); } return h; } }这个实验刻意把桶数量设为 65536也就是 2¹⁶让桶下标完全由哈希值的低 16 位决定。这样能非常直观地暴露「偶数乘子导致低位信息丢失」的问题。样例字符串长度从 3 到 12 不等模拟真实使用中短键为主的场景。随机种子固定为 42保证结果可复现。需要说明的是这个实验的「冲突次数」统计的是发生碰撞的桶数量不是碰撞对的总数。它足以反映不同乘子下哈希分布的相对优劣。运行一次典型输出会非常有说服力我们将在下一节详细解读。十二、实验结果与冲突率分析在 20 万条随机字符串、65536 个桶的设定下一个理想的均匀哈希函数大约会让每个桶平均容纳 3 个元素几乎所有桶都会被占用因此「冲突次数」接近桶总数 65536 才是正常表现。真正值得关注的是那些明显低于这个值的乘子——它们说明大量字符串挤在了少数桶里分布严重不均。实验的核心观察如下32 表现得最差因为 32 是 2 的 5 次方字符串第 6 个字符之后的贡献在低 5 位全部为零。当桶数取 2 的幂时桶下标只由低 16 位决定于是所有长度超过 5 的字符串的低位哈希严重同质化冲突数量会显著低于理想值大量桶被浪费。39 是一个很有教育意义的样本39 3 × 13它不是素数。虽然它是奇数不会像 32 那样直接丢失低位但由于与字符码点取值范围存在结构上的关联其分布也略逊于同量级的素数乘子。31、33、37、41 这些奇素数的表现非常接近它们的冲突数量都贴近理想值彼此之间的差异常常只有千分之几。这说明「奇素数」这个条件一旦满足具体选 31 还是 37 对分布的影响很小。127 作为 2⁷ − 1 的梅森素数分布同样优秀但它在字符串较短时就把哈希值推得过高且 127 不能像 31 那样在「前几步就有效混合低位」与「避免过早饱和」之间取得完美平衡。这张对比表把结论浓缩得非常清楚分布质量的决定性因素是「奇数且尽量为素数」而 31 在满足这个条件的同时还附带「2⁵ − 1 的移位优化」。换句话说31 在众多同样「分布良好」的候选者中靠性能优势脱颖而出而在众多「性能好优化」的候选者中靠素数的分布优势胜出。它是两个维度的交集。十三、从数论角度看乘法哈希如果要严谨一些31 的优良性质可以从数论上给出解释。考虑一个简化模型哈希函数是h(x) a * x mod m其中 a 是乘子x 是输入字符码点m 是模数。为了让所有可能的 x 都能被均匀映射我们希望 a 与 m 互质。更严格地说当 a 与 m 互质时映射x ↦ a * x mod m是模 m 剩余类环上的一个置换它把 0 到 m−1 的每个值都一一映射不会把两个不同 x 折叠到同一个值。Java 的 String.hashCode 不是简单的a * x而是迭代多项式h a * h c。把它展开每个字符 cᵢ 的系数是 a^(n−1−i)。如果 a 与模数 2³² 互质等价于 a 是奇数那么这些系数 a^k 在模 2³² 下形成一个遍历所有单位的循环不会过早重复。这使得不同位置的字符以不同周期混合进结果避免「位置 k 和位置 kp 总是同权」的灾难。相反如果 a 是偶数则 a 与 2³² 有公因数 2系数 a^k 会迅速共享越来越大的 2 的幂因子低位信息被系统性抹掉。这从数学上解释了上一节实验中 32 的糟糕表现。为什么不仅要求奇数还希望是素数在模 2³² 的环里「奇数」已经足以保证可逆性素数在纯模 2³² 意义上的额外作用并不像「模大素数」时那么关键但素数依然有价值它排除了 a 与字符码点空间或其他结构产生隐秘公因数的可能同时在历史实践中被大量统计验证为分布优良。工程上我们往往先靠数论排除明显错误选项再靠实验在合格选项里做最终筛选。十四、为什么是 31而不是 33 或 37经过前面的铺垫现在可以正面回答这个对比问题了。33 和 37 都是奇素数分布表现与 31 不相上下但它们各自缺少 31 具备的那个决定性优势。先说 33。33 32 1虽然可以写成 (h 5) h但它不是梅森素数且加法形式意味着每次迭代需要一次左移加一次加法。31 32 − 1 则是 (h 5) − h。两者成本几乎一样但在溢出回绕时减法与加法的低位进位行为略有不同31 的减法形式在部分测试里拥有更均匀的混合效果。更重要的是31 是梅森素数这个「2 的幂减 1 且为素数」的双重身份让它在数学与硬件两个维度同时得到背书。再说 37。37 是素数但它不能表示为 2 的幂减 1 或加 1 的简单形式乘 37 无法用单次移位优化需要真正的乘法指令或更复杂的一系列移位加法组合。分布上它并不比 31 更好性能上却略逊自然落选。41、47、61 等其他奇素数也是类似逻辑。31 之所以被选中本质上是一场多目标优化目标一哈希分布均匀要求乘子为奇素数目标二计算代价低要求乘子能写成 2^k ± 1目标三权重增长适中要求乘子数值落在短字符串也能充分利用 32 位空间的区间31 正好同时满足这三个目标。它不是「分布最好」的乘子也不是「计算最快」的乘子但它是这个多目标问题的帕累托最优解之一并且被一个在历史上拥有极高影响力的标准库固化了下来。这就是工程选择的真实面貌不求单项极致而求整体平衡。十五、hashCode 与 equals 的契约理解 31 之后有必要回到它服务的对象equals 与 hashCode 的契约。很多初学者会问「是不是 hashCode 相等两个对象就相等」答案是否定的。哈希值相等只是「可能相等」的必要条件最终必须由 equals 做精确判定。两个不同字符串的 hashCode 可能相同这是哈希冲突无法也无需完全避免但两个 equals 相等的字符串必须有相同的 hashCode。String 类对这两个方法做了严格一致的实现equals 逐字符比较内容hashCode 基于同样的字符序列计算。只要两个字符串内容相同它们必然经过相同的多项式计算过程得到相同的哈希值满足契约。这给自定义类的实现提供了模板当你重写 equals 时必须同步重写 hashCode否则把对象放进 HashMap 或 HashSet 后会出现诡异的「找不到元素」问题。正确做法通常是选取所有参与 equals 比较的字段用一个与 31 类似的奇素数做多项式混合。Bloch 在《Effective Java》中给出的建议公式正是int result 17; result 31 * result field1.hashCode(); result 31 * result field2.hashCode();这里的 17 和 31 不是随意写的17 作为初始值提供非零起点31 继续充当那个经过验证的奇素数乘子。这个模式与 String.hashCode 一脉相承可以看成是标准库经验向应用代码的扩散。十六、字符串不可变性与哈希缓存String.hashCode 能放心地缓存结果前提是 String 不可变。Java 的 String 对象一旦创建其内部 value 数组就不能被外部修改在 JDK 9 及之后是 byte 数组同样不可变因此哈希值可以安全地在第一次计算后保存之后每次调用直接返回。这种设计带来两个直接收益重复哈希零成本同一个字符串作为 HashMap 的键被查找多次时第二次开始的 hashCode 调用都是 O(1) 的字段读取而不是 O(n) 的字符遍历。并发安全即使多个线程同时首次调用 hashCode各自计算出的值也必然相同缓存写入只是幂等的重复赋值不会产生可见性问题。JDK 后续版本在细节上做了一些并发加固但逻辑不变。不可变性还让 String 成为散列表最理想的键类型equals 结果永不改变hashCode 结果永不改变整个散列表的完整性在键的生命周期内都能保证。如果用可变对象做键一旦键的内容在插入后被修改它的桶位置就失效了元素会「丢失」在错误的桶里。这也解释了为什么标准实践强烈建议用 String、Integer 等不可变类型做键。十七、常见误区与面试高频追问围绕 31 和 String.hashCode有几个频繁出现的误解和追问值得一一澄清。误区一31 是「最优」乘子。严格来说不存在对所有字符串集合都最优的乘子。31 是在「分布质量 计算成本」的权衡下足够好的选择并非数学意义上的全局最优。不同数据集的字符串分布不同或许某个特定数据集在乘子 37 下冲突更少但这不构成改变标准库的理由。误区二hashCode 会溢出导致错误。int 溢出在这里是特性而非缺陷。Java 的 int 运算按 32 位回绕恰好实现了模 2³² 的效果。只要 equals 与 hashCode 的实现保持一致溢出产生的负数或「回绕」都不会破坏正确性。误区三hashCode 返回负数不正常。int 是有符号的哈希值完全可能是负数。这没有影响因为后续映射桶下标时会用位运算或取模把符号位也纳入计算例如(n - 1) hash对负数同样生效。追问一能举个 String 哈希冲突的例子吗经典例子是Aa与BB。A是 65a是 97B是 66可以算出Aa的哈希值是 65 * 31 97 2112BB的哈希值是 66 * 31 66 2112二者相等。这说明冲突无法避免但概率和分布都在可接受范围内。追问二既然冲突难免Java 如何兜底HashMap 在同一个桶内用链表或红黑树存储冲突元素查找时先比 hashCode 快速筛选再用 equals 精确确认所以即使 hashCode 冲突正确性依然由 equals 保证。追问三为什么 JDK 不改成分布更好的乘子因为 String.hashCode 的结果已经是事实标准序列化数据、第三方库的缓存、分布式系统的一致性哈希等都可能依赖它。修改意味着大范围兼容性破坏而 31 带来的分布问题在实际业务中几乎不可感知不值得为此付出巨大迁移成本。十八、总结与延伸思考回到最初的问题「为什么 String hashCode 方法选择数字 31 作为乘子」答案可以浓缩成一句话31 是一个大小适中的奇素数能与 Java 的 int 溢出隐式模数 2³² 良好配合让多项式哈希的分布足够均匀同时它等于 2⁵ − 1使 31 * h 可以被编译器优化成 (h 5) - h在性能上占据优势。分布与性能的双重合格加上标准库一经发布便难以更改的路径依赖让 31 成为最终答案。如果只记得一句话请记住31 是素数与硬件友好的交集。这个选择背后其实隐藏着软件设计中反复出现的规律好的实现不是追求某个维度的极致而是在正确性约束下用数学性质换取工程收益。String.hashCode 的 31、HashMap 的 2 的幂容量、各种经典哈希算法的奇素数乘子都是同一种思维在不同场景下的投影。延伸下去还有很多值得深入的方向你可以研究开放寻址法与链地址法对哈希函数质量的不同要求可以阅读 William Pugh 的跳跃表、Google Guava 对哈希的封装也可以去算法竞赛世界了解双哈希、滚动哈希和大素数取模的技巧。理解了 31就拿到了进入这些领域的一张入场券。对于正在准备面试的读者建议把这条逻辑链完整走一遍从「为什么需要乘子」到「为什么是素数」再到「为什么是 31 而不是 33 或 37」最后到「改成别的数会发生什么」。当你能够不查资料地讲出这四步这个问题就不再是背诵题而是展示你技术深度的机会了。