分表路由：为什么大神都用 & (n-1)，而不用 % ？一次给你讲透

有芝有味 發表於 2026-1-5 14:30:00

分表路由：为什么大神都用 & (n-1)，而不用 % ？一次给你讲透

<blockquote>
写在前面
"分库分表"大家都不陌生。当数据量激增时，我们习惯性地写下 <code>userId % tableCount</code> 来决定数据路由到哪张表。
这段代码逻辑正确、简单直观。但在对性能要求极高的底层中间件开发中，这真的是最优解吗？
如果我们翻开 JDK 1.8 的 HashMap 源码，会发现大神 Doug Lea 在计算数组下标时，刻意避开了 <code>%</code> 取模，而是使用了一行看起来更晦涩的 <code>& (n - 1)</code>。
今天，我们就把 HashMap 的这项底层“绝技”移植到业务系统的分表组件中，打造一个高性能、可扩展且具备防御性的路由工具。
</blockquote>
<hr>
<h2 id="一-从一次-code-review-说起">一、从一次 Code Review 说起</h2>
最近在审查新版分表中间件的代码时，看到了一段非常标准的分表路由逻辑：
<pre><code class="language-java">// ❌ 常见的写法
public String getTableName(int userId) {
// 假设分32张表
int tableIndex =userId % 32;
return "t_order_" + tableIndex;
}
</code></pre>
这段代码在功能上没有问题。但作为一个对底层细节有追求的工程师，我不禁想到了 HashMap 的实现。
打开 JDK 源码，在 <code>HashMap.put</code> 方法中，计算节点落槽位置的代码是这样的：
<pre><code class="language-java">// HashMap源码片段
if ((p = tab) == null) ...
</code></pre>
Doug Lea 并没有使用直观的 <code>hash % n</code>，而是使用了与运算 <code>&</code>。
为什么？ 
根本原因在于 CPU 的指令执行效率：
<ul>
<li>位运算（&, |, ^, ~）：直接对应 CPU 底层指令，通常只需 1 个时钟周期。</li>
<li>取模运算（%）：涉及除法操作，在底层硬件实现上极其复杂，通常消耗 10-30 个时钟周期。</li>
</ul>
虽然在普通的业务逻辑中，几十个时钟周期的差异可以忽略不计。但在高频触发的基础设施层（如网关路由、分表中间件、缓存寻址），这种微小的性能差异在高并发下会被显著放大。
<hr>
<h2 id="二-揭秘位运算的物理意义">二、揭秘位运算的物理意义</h2>
HashMap 能用 <code>&</code> 替代 <code>%</code>，有一个强制性的前提条件：
<blockquote>
数组长度（或分表数）必须是 2 的 n 次幂（2, 4, 8, 16, 32, 64...）
</blockquote>
<h3 id="1-数学原理">1. 数学原理</h3>
公式： 
当 <code>n = 2^k</code> 时，<code>X % n</code> 等价于 <code>X & (n - 1)</code>
这个公式背后的逻辑，从二进制视角来看会非常清晰。
假设分表数 <code>n = 8</code>（即 2³）。 
那么 <code>n - 1 = 7</code>。
<ul>
<li>8 的二进制：<code>... 0000 1000</code></li>
<li>7 的二进制：<code>... 0000 0111</code> （低三位全为1，高位全为0）</li>
</ul>
当我们计算 <code>userId & 7</code> 时，实际上是在进行位掩码（BitMask）操作。 
因为 7 的高位全是 0，<code>&</code> 运算会将 userId 的所有高位清零，只完整保留最后三位。
而一个数值的低 k 位，恰恰就是它对 2^k 取模的余数。
<table>
<thead>
<tr>
<th style="text-align: left">userId (十进制)</th>
<th style="text-align: left">userId (二进制)</th>
<th style="text-align: left">& 0111 (掩码)</th>
<th style="text-align: left">结果</th>
<th style="text-align: left">% 8 结果</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: left">10</td>
<td style="text-align: left"><code>... 0000 1010</code></td>
<td style="text-align: left"><code>0010</code></td>
<td style="text-align: left">2</td>
<td style="text-align: left">2</td>
</tr>
<tr>
<td style="text-align: left">15</td>
<td style="text-align: left"><code>... 0000 1111</code></td>
<td style="text-align: left"><code>0111</code></td>
<td style="text-align: left">7</td>
<td style="text-align: left">7</td>
</tr>
<tr>
<td style="text-align: left">16</td>
<td style="text-align: left"><code>... 0001 0000</code></td>
<td style="text-align: left"><code>0000</code></td>
<td style="text-align: left">0</td>
<td style="text-align: left">0</td>
</tr>
<tr>
<td style="text-align: left">17</td>
<td style="text-align: left"><code>... 0001 0001</code></td>
<td style="text-align: left"><code>0001</code></td>
<td style="text-align: left">1</td>
<td style="text-align: left">1</td>
</tr>
</tbody>
</table>
结论：只要分表数是 2 的幂，位运算本质上就是一次高效的低位截取。它能在硬件层面以最快的速度得到我们想要的结果。
<hr>
<h2 id="三-实战打造生产级路由工具">三、实战：打造生产级路由工具</h2>
原理虽然简单，但要落地到生产环境，必须考虑工程化问题：如何防止后续维护者错误配置分表数？如何保证代码的健壮性？
这里我们推荐使用 防御性编程 + 枚举约束 的方式。
<h3 id="1-定义分表策略枚举">1. 定义分表策略枚举</h3>
我们通过枚举（Enum）将分表规则固定下来，并在枚举构造器中进行严格校验。
<pre><code class="language-java">@Getter
@AllArgsConstructor
public enum TableStrategyEnum {
/** 订单表：分32张 */
ORDER("t_order_", 32),

/** 支付流水表：分64张 */
PAYMENT("t_pay_flow_", 64);

private final String prefix;
private final int count;

// 构造时进行 Fail-Fast 检查
// 如果配置的不是 2 的幂，应用启动时就会直接抛错，阻止由于配置失误导致的上线事故
TableStrategyEnum(String prefix, int count) {
 if (count <= 0 || (count & (count - 1)) != 0) {
 throw new Error("配置错误：Strategy [" + prefix + "] 分表数必须是 2 的幂！");
 }
 this.prefix = prefix;
 this.count = count;
}
}
</code></pre>
<h3 id="2-封装核心路由工具类">2. 封装核心路由工具类</h3>
<pre><code class="language-java">public class DivTableUtils {

/**
* 获取目标表名
* @param bizId 业务主键（如 userId, orderId）
* @param strategy 分表策略
*/
public static String getTableName(int bizId, TableStrategyEnum strategy) {
 // 1. 基础校验
 if (bizId <= 0) {
 throw new IllegalArgumentException("业务ID必须为正整数");
 }

 // 2. 核心位运算逻辑
 // 因为枚举构造里已经保证了 count 是 2 的幂，这里可以安全使用位运算
 int index = bizId & (strategy.getCount() - 1);

 // 3. 拼接返回
 return strategy.getPrefix() + index;
}
}
</code></pre>
使用示例：
<pre><code class="language-java">// 业务代码中调用，清晰且安全
String tableName = DivTableUtils.getTableName(user.getId(), TableStrategyEnum.ORDER);
// 输出：t_order_5
</code></pre>
<hr>
<h2 id="四-深度思考为什么要强制-2-的幂">四、深度思考：为什么要强制 2 的幂？</h2>
肯定有人会问：
<blockquote>
“我的业务规模刚好适合分 100 张表，为了用位运算强行改成 128 张，是不是这就叫过早优化？”
</blockquote>
这个问题直击要害。 
事实上，HashMap 以及我们推荐的分表策略，强制使用 2 的幂次方，性能提升只是表象，真正的核心价值在于——扩容的平滑性。
<h3 id="扩容时的-rehash-魔法">扩容时的 "Rehash" 魔法</h3>
通常分表扩容时，我们会将表数量翻倍（例如 16 -> 32）。 
如果我们使用传统的 <code>hash % n</code>，当 n 变化时，几乎所有数据的路由结果都会发生改变，这意味着我们需要迁移绝大部分数据。
但如果我们遵循 2 的幂次方扩容： 
从二进制角度看，<code>n</code> 从 16 (10000) 变为 32 (100000)，仅仅意味着位掩码多取了一位。
对于任何一个 ID，其路由结果只有两种可能：
<ol>
<li>保持不变：如果新增的那一位是 0。</li>
<li>平移固定量：如果新增的那一位是 1，新坐标 = <code>原坐标 + 原长度</code>。</li>
</ol>
这就是 HashMap 扩容时 rehash 极其高效的秘密。反映到数据库分表扩容上，这意味着我们有一半的数据完全不需要移动，这一点对于海量数据的迁移至关重要。
<hr>
<h2 id="五-结语在比特世界里寻找优雅">五、结语：在比特世界里寻找优雅</h2>
计算机科学里有一句名言："Simple is Better"。
但"简单"往往有两个层次： 
一个是无知的简单：随手写下 <code>id % n</code>，不管不顾。 
一个是透彻的简单：理解了二进制的规律，用 <code>id & (n-1)</code> 驾驭复杂。
<code>DivideTableUtils</code> 这个小工具，虽然只有寥寥几行代码，却折射出了优秀架构设计的三个维度：
<ol>
<li>对原理的极致利用（位运算加速）。</li>
<li>对错误的零容忍（Fail-Fast 校验）。</li>
<li>对未来的深远规划（Rehash 扩容）。</li>
</ol>
可以预见的是，当你的业务流量洪峰到来时，那些藏在比特世界里的每一次优化，都将成为系统最坚实的护盾。
<blockquote>
文章的最后，想和你多聊两句。
技术之路，常常是热闹与孤独并存。那些深夜的调试、灵光一闪的方案、还有踩坑爬起后的顿悟，如果能有人一起聊聊，该多好。
为此，我建了一个小花园——我的微信公众号「[努力的小郑]」。
这里没有高深莫测的理论堆砌，只有我对后端开发、系统设计和工程实践的持续思考与沉淀。它更像我的数字笔记本，记录着那些值得被记住的解决方案和思维火花。
如果你觉得今天的文章还有一点启发，或者单纯想找一个同行者偶尔聊聊技术、谈谈思考，那么，欢迎你来坐坐。 
<img src="https://img2024.cnblogs.com/blog/3703499/202601/3703499-20260105210259813-964799315.jpg">
愿你前行路上，总有代码可写，有梦可追，也有灯火可亲。
</blockquote> 
来源：https://www.cnblogs.com/xzqcsj/p/19442863

頁: [1]

琼殿技术论坛's Archiver

分表路由：为什么大神都用 & (n-1)，而不用 % ？一次给你讲透