我去年处理过一个挺有意思的活儿：某内部工具需要在上亿条日志里按时间窗口做聚合统计，数据的时间戳全部落在最近三个月内。一开始我按教科书思路上了红黑树、跳表这类“高级”结构，结果在真实数据上跑得还不如后来换上的一个普通数组快。原因很简单——我知道时间戳的确定范围，明明可以用直接定址的思路，偏要去搞那些对范围无感的通用结构。这件事给我的教训很直接：算法选型先看数据范围，范围一旦已知，很多“复杂度更优”的通用方案反而会被一个最朴素的数组下标干掉。

这篇内容就想把“根据已知数据范围选择算法”这个话题掰开揉碎。我适合以下人群阅读：写业务代码时经常面对确定值域的数据（比如用户ID、订单号、IP段、时间戳、固定枚举状态），却不太确定该用哈希、树还是数组的人；刷题或做竞赛时知道数据范围却总选错算法的人；以及工作中需要评估算法选型、做性能优化的人。看完你就明白，范围信息不是可有可无的细节，而是能把算法复杂度从 O(n log n) 拉到 O(n) 甚至 O(1) 的关键钥匙。

1. “已知数据范围”为什么能改变算法抉择——从时间复杂度的盲区说起

大多数人学算法时，最先接触的是时间复杂度的渐进分析。这个工具很强大，但它有一个致命盲区：复杂度公式里往往只出现 n（元素个数），而不出现 U（值域大小）。结果就是，当问题里同时存在 n 和 U 这两个维度时，仅看 n 会严重误导选型方向。

1.1 一个反直觉的例子：知道范围后“笨算法”反而最快

先看一个最经典的场景：给 10^7 个整数排序，这 10^7 个数全部落在区间 [0, 10^5] 内。

常规思路是快速排序或归并排序，复杂度 O(n log n)。n = 10^7 时，10^7 × log2(10^7) ≈ 10^7 × 23.25，大约 2.3 亿次基本操作。跑起来一般需要几百毫秒到一秒多，具体看语言和优化情况。

但如果我知道所有数都落在 [0, 10^5] 这个有限范围内，可以用计数排序：

// 已知：arr[0..n-1] 中所有元素满足 0 <= arr[i] <= U_MAX (U_MAX = 100000) void countingSort(vector<int>& arr, int U_MAX) { vector<int> cnt(U_MAX + 1, 0); for (int x : arr) cnt[x]++; int idx = 0; for (int v = 0; v <= U_MAX; v++) { while (cnt[v]--) arr[idx++] = v; } }

这段代码的复杂度是 O(n + U)，其中 U = 10^5。两层循环加起来只有 10^7 + 10^5 的量级，大约 1010 万次操作，比快速排序的 2.3 亿次少了二十多倍。

这里的关键不是“计数排序打败快排”，而是“在范围已知的情况下，复杂度分析必须同时考虑 n 和 U 两个变量，否则会得到错误结论”。如果你只会背“快排就是 O(n log n) 最优”，面对这种确定值域的数据，就会错过一个数量级的性能提升。

1.2 数据范围如何改变“最优解”的定义

数据范围至少包含以下几个维度，每个维度都直接影响选型：

举一个直观类比：假设你要给一万个盒子贴上对应编号的标签，每个盒子上的编号从 1 到 10000。如果你提前知道“编号范围就是 1 到 10000”，最蠢也最有效的办法是准备一万个空位，看见几号盒子就放到几号位子上；如果你不知道编号范围，就得把所有盒子排成一排，一个个比较交换排序。前者就是“范围已知”的威力——你不需要通过互相比较来推断位置，而是直接把“值”当成“位置”。

理解了这个前提，下面就可以进入实际操作层面的拆解了。

2. 四个高频场景的选型拆解：排序、查找、去重、素数处理

范围信息对算法选型的影响，在排序、查找、去重、素数这四个场景里体现得最充分。我分别把它们的决策逻辑讲透。

2.1 排序场景：计数排序碾压快排的边界在哪里

计数排序的思路本质上是“用空间换时间”，它把数据本身当作数组下标，先统计每个值出现多少次，再按值从小到大把元素回填。

它成立的条件很苛刻，但也很明确：元素必须是非负整数，值域 U 不能太大，而且你能容忍排序后的元素只是数值有序（大多时候这足够了）。当 U 远小于 n 时，计数排序几乎无敌；当 U 和 n 同量级，比如 n = 10^7、U = 10^7，那么 O(n + U) 和 O(n log n) 差别不大，这时反而要考虑内存占用和常数因子。

一个实际的选择标准可以写成：

• U ≤ 10^7，内存允许 4U 字节（int 数组）时，优先考虑计数排序；
• 如果数据中有负数，先做平移，把最小值变为0；
• 如果不只是简单排序，还需要按其他键二次排序，改用基数排序或“计数排序+稳定归并”。

基数排序值得多说一句。它是计数排序的推广：把整数按位拆成多个关键字，每一位分别做一次稳定的计数排序。比如 32 位整数，可以按 8 位一组分成 4 轮。这样即使 U 很大（接近 2^32），只要数据本身分布均匀，也能在 O(n × 位数/组大小) 内排完，大约就是 O(4n)。所以面对 0 到 2^32-1 的大范围整数排序，基数排序是比快速排序更贴近“工程最优”的选择之一。

这里有一个需要警惕的误区：有些资料说“计数排序适合小范围”，但没定义“小”到底是多少。在很多竞赛和面试场景里，值域 10^6 以下才算“小”；但在真实系统里，如果内存很充裕，10^8 也能硬上（需要约 400MB 内存）。我曾经在某数据分析脚本里就真用 10^8 的 int 数组做过一次计数统计，明显比跑外部排序快得多——前提是这台机器内存够大，脚本是短生命周期的。

2.2 查找场景：二分、哈希、还是直接数组下标

查找问题里，“范围已知”的价值被很多人低估了。当数据范围是有限的连续整数时，最猛的查找结构其实是一个普通的数组。

假设你有一个系统，用户ID从 0 递增分配，最多 10^7 个用户，需要根据 ID 快速查到用户信息。此时直接开一个大小为 10^7 的数组，下标就是 ID：

# 建立：直接按下标存 users = [None] * MAX_USER_ID def add_user(uid, info): users[uid] = info def get_user(uid): return users[uid]

查找复杂度为 O(1)，而且没有任何哈希冲突、没有链表指针跳转、没有缓存缺失问题。相比之下，哈希表虽然理论也是 O(1)，但它需要计算哈希、处理冲突、可能触发扩容，常数因子比数组直接定址大不少；红黑树和跳表理论 O(log n)，更是差了一个数量级。

二分查找则适合另一种场景：数据本身已经有序，但你不知道数据的分布密度，只知道范围。比如你要在一个已排序的数组中查找某个值，二分查找完全不关心值域大小，只关心元素个数 n，这是它的天然优势。

所以查找场景的决策逻辑大致如下：

• 值是连续或接近连续的整数，且下界不大 → 直接数组定址；
• 值域稀疏但已知上下界 → 先离散化，再用二分或哈希；
• 值域未知、数据静态有序 → 二分查找；
• 值域未知、数据动态插入删除 → 哈希表或平衡树。

我不是说哈希表不好，哈希表在很多场景确实是全能选手。但“范围已知”这个信息，经常能把哈希表降级成一个更简单的数组，省掉一堆隐形成本。尤其是高并发读取场景，数组定址的局部性好，CPU 缓存友好，性能优势非常明显。

2.3 去重场景：位图与布尔数组的空间账

去重问题的本质是“判断某个值是否出现过”。如果值的范围已知，最简单的办法是布尔数组，甚至位图。

给一个具体例子。某系统需要过滤 10^9 条请求里的重复设备编号，设备编号是 32 位非负整数，最大值约 4×10^9——这个范围太大，直接开 int 数组需要 16GB，显然不现实。但如果换一个角度：我们不关心某个编号出现了多少次，只关心“是否出现过”，就可以用位图来表示，每个编号只占 1 bit，4×10^9 个编号对应约 500MB。虽然也不小，但已经比 int 数组省了 32 倍，配合分段加载、多线程处理，很多场景是可行的。

如果范围再小一些，比如设备编号实际是 MAC 地址后 24 位（0 ~ 2^24-1，约 1600 万个取值），位图只需要 2MB。直接用 bitset 或手工字节数组都能轻松装进内存。

// 位图去重：假设值域为 [0, MAX_VAL) vector<uint8_t> bitmap((MAX_VAL + 7) / 8, 0); bool markIfFirstSeen(uint32_t val) { uint32_t byteIdx = val >> 3; uint8_t bitMask = 1 << (val & 7); bool first = !(bitmap[byteIdx] & bitMask); bitmap[byteIdx] |= bitMask; return first; }

哈希 Set 也能去重，但它有两个问题：内存占用大（每个元素除了值本身，还有哈希桶、节点指针、负载因子预留空间），而且哈希碰撞后还会退化。所以当范围可控时，位图在内存和时间上都是更优选择。

去重场景的选型逻辑可以总结为：

• 值域 ≤ 10^7，直接用布尔数组（约 10MB）；
• 值域 ≤ 10^9，考虑位图（约 125MB），还是要评估内存预算；
• 值域 > 10^9 且实际元素数量少 → 哈希 Set 或布隆过滤器；
• 允许误判、且数据量极大 → 布隆过滤器，它本质上也依赖“范围预估”来设定位数组大小和哈希函数个数。

布隆过滤器这里尤其值得展开：它需要的位数组大小，依赖于你预估的元素数量 n 和可接受的误判率 p。公式是 m ≈ -(n × ln p) / (ln 2)^2。这不就是“根据已知数据范围（预估规模）选择参数”的典型例子吗？范围估计得越准，布隆过滤器就越省内存且误判可控。

2.4 素数处理：大范围区间筛的偏移存储技巧

素数问题看起来和“数据范围选型”没直接关系，但我做某次数论相关需求时踩过坑，这里必须分享一下。

如果需求是求区间 [L, R] 内的所有素数，L 和 R 可能很大，比如 L = 10^9，R = 10^9 + 10^7。此时你没法直接开一个大小为 R+1 的布尔数组来筛——那要 1GB 以上空间。但区间长度 R - L + 1 只有 10^7，是可以轻松放进内存的。

做法是埃氏筛的“区间偏移”：先用普通埃氏筛把不超过 sqrt(R) 的素数全部找出来，再用这些素数去筛 [L, R] 区间内合数，但数组下标只需要从 0 到 R-L：

vector<bool> isPrime(R - L + 1, true); // 先用经典筛法得到所有 <= sqrt(R) 的素数 primes for (int p : primes) { // 找到 [L, R] 中第一个能被 p 整除的数 long long start = max((long long)p * p, ((L + p - 1) / p) * p); for (long long j = start; j <= R; j += p) { if (j != p) isPrime[j - L] = false; } }

思路核心就是把值域范围从 [0, R] 偏移成 [0, R-L]，也就是“已知区间长度，而不是已知绝对最大值”。这类偏移技巧在算法竞赛和工程里都能见到，本质上是让你不要被问题表面的大数值吓到——多问一句“我关心的范围到底是从哪到哪、跨度有多大”，选型思路就会完全不一样。

类似的还有线性筛（欧拉筛），它在需要频繁查询前缀素数个数、或需要维护每个数的最小质因子时更好用，但代价是需要完整表。如果范围已知且不大（比如 U ≤ 10^7），线性筛是首选；范围很大但只查某个区间，区间筛配合偏移才是正解。

3. 范围已知不等于一切：稀疏、偏移、大值域的边界处理

上一章讲的是“范围已知带来的红利”，实际操作中更常见的却是“范围似乎知道了，但没那么简单”。我把最常见的边界情况列一下。

3.1 稀疏范围是陷阱：值域大而实际元素少

最常见的翻车场景是：系统文档告诉你“编号范围是 1 到 10^9”，于是你想开一个 10^9 的数组，然后发现内存直接爆炸。但你仔细看看数据，实际出现的编号总共只有 10^4 个——这就是稀疏范围。

在稀疏范围面前，直接定址不可行，应该转向离散化：把所有出现过的值收集起来，排序去重后映射成 0 到 m-1 的紧凑下标，再用数组或树状数组处理。

比如你要对一堆区间做覆盖次数统计，编号是 10^9 量级的离散点。开数组不可能，但把这些点离散化后，问题规模就变成“实际点数 m”，所有基于范围下标的算法都能继续用：

vector<int> allVals = originalVals; sort(allVals.begin(), allVals.end()); allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end()); // 之后要查某个 val，先二分定位：lower_bound(allVals.begin(), allVals.end(), val)

这里“范围已知”的信息并没有失效，而是换了一种用法：范围决定了你能预判离散化后 m 的大小上限，进而决定是选树状数组还是线段树、是选普通数组还是哈希。离散化后的查找用二分 O(log m)，也可以再套哈希 O(1)；如果 m 不超过 10^6，甚至可以直接开一个大小为 m 的数组配合“反离散化映射”。

我个人的经验是：在做任何依赖“值域大小 U”的算法之前，先统计“实际互异元素数量 m”。如果 m 远小于 U，走离散化；如果 m 和 U 同量级且 U 可控，才考虑直接开数组。

3.2 负数与起始偏移：让下标从0开始的三种映射方式

已知范围是从负数开始，或者最小值远大于 0 时，不能直接使用原始值作为数组下标。处理办法很简单：建立从“原始值”到“数组下标”的映射，常见有三种。

第一种是整体平移。如果范围是 [-10^5, 10^5]，把所有值加上 10^5，变成 [0, 2×10^5]，再开数组。这种方式最简单，但前提是范围不大，否则平移只是把问题延后，内存照样过大。

第二种是取模或哈希映射。适用于大值域但稀疏的情况，本质上是哈希表，不保证下标连续。

第三种是排序后二分定位。也就是前面说的离散化，适合值域范围大、但实际值集合固定且数量不多的查询场景。

这三种方式的选型判断依据，还是回到第一张表里那几个维度：范围跨度、连续性、实际元素数量。如果跨度小且连续，平移开数组最优；跨度大且稀疏，离散化加二分；动态插入且无法排序，哈希。

一个我曾经忽略的细节：做平移时，一定要确认映射后的最大值不超过数组边界。比如值是 [10^6, 10^6 + 10^4]，平移量是 10^6，但有些人只平移了最小值，却忘了数组长度等于“最大值减最小值加一”，导致越界访问。测试时数据不靠边界根本发现不了，一旦上线就偶发崩溃，非常难排查。

3.3 分布不均时：基数排序比计数排序更稳

计数排序在值域很小但分布极不均匀时有一个隐藏问题：回填阶段需要把所有值域遍历一遍，哪怕绝大多数值从来没有出现过。如果 U = 10^8，n = 10^6，那么 O(n + U) 实际约等于 1.01 亿次操作，大部分时间浪费在空转的 for 循环上。虽然也不算慢，但内存开销已经不小（400MB 左右的 int 数组）。

此时可以考虑基数排序的变体：按二进制位分组做 LSD 排序。32 位整数按 8 位一桶，只需 4 轮，每轮 O(n)，总共 O(4n)。它不要求值域连续，只依赖于位宽。实测中，当数据非常集中（比如所有数都在 0 到 2^20 附近）时，基数排序依然稳定；而计数排序则会因为 U 大而吃亏，或者因为 U 小而先要扫描全范围。

还有一个更实用的组合：先根据高位做一次粗分桶，把数据拆到若干个区间里，区间内部如果值域跨度已经很小，再对每个区间单独做计数排序。这种“桶排序 + 计数排序”的思路，在很多大数据排序系统里都能见到，本质就是利用数据范围的层次性——外层看范围分桶，内层看区间跨度再细化。

3.4 时间与内存的权衡：bitset、压缩与分段处理

当范围 U 很大但你又想保留“范围直接定址”的好处时，内存会成为瓶颈。这时有几个工程手段值得掌握。

位压缩：前面提过，值域 U 的布尔数组至少 U 字节，位图只要 U/8 字节。例如 U = 10^8，布尔数组 100MB，位图 12.5MB，差距非常明显。

分段处理：如果一次性装不下，可以考虑按值域分段。比如值域 0 到 10^9，我把范围切成 100 段，每段长度 10^7，每次只加载一段到内存处理，处理完写回结果再换下一段。这种方式牺牲了随机访问的便利性，但能把“范围已知”的优势从内存受限场景中拯救出来。

压缩编码：当数据的值域连续但分布极不均匀时，可以用差值编码、前缀和编码等方式压缩存储。这已经进入数据结构的深层定制了，一般只在存储成本极高时才会考虑。我的建议是：先别急着上压缩，先用位图和分段扛一扛，绝大多数场景已经够用。

4. 从一次翻车经历谈选型前必问的六个问题

讲完了原理，我想用一段真实踩坑记录收尾。某次我负责一个内部统计系统，需求是给海量请求按来源IP段聚合计数。IP是IPv4，四个字节，我当时想当然地以为“IPv4范围就是 0 到 2^32-1，均匀分布”，于是一开始就准备了一张大小为 2^32 的数组，算一下 16GB，直接超了内存预算。后来又改成哈希表，但因为 IP 段极不均匀地集中在少数几个C段，哈希表碰撞率很高，性能又不行。

最后我做了两件事：先用采样统计出实际出现的IP段数量；再把“IP地址范围”转换成“CIDR前缀范围”，按前缀长度分层处理。最终方案是：高频前缀用紧凑数组直接定址，低频稀疏部分用离散化加二分。整体内存不到原来的十分之一，性能还比哈希表快了三倍。

这次经历让我总结出选型前必问的六个问题，也推荐给你：

这六个问题看着简单，但真到项目里，很多人是在写完代码之后才开始考虑的，顺序反了。正确做法是：写算法前先做 5 分钟的数据分析，哪怕是粗略估算，也远比凭感觉选结构要可靠。

选完算法之后，还有一步容易被漏掉：用多组不同规模的数据做基准测试，而不是只看理论复杂度。理论分析只告诉我们增长趋势，常数因子、缓存行为、内存分配开销，只有实测才能暴露。具体做法我一般是这样：

• 先把数据规模从小到大各测一轮，比如 n = 10^4、10^5、10^6、10^7；
• 同一规模下再测分布极不均匀的情况；
• 对比时间时，顺带记录内存峰值；
• 如果理论曲线和实测曲线偏离超过一个数量级，回头检查是不是忽略了对数项或线性扫描项。

还是拿时间戳那个例子说。当时我把直接定址数组换成“哈希 + 红黑树”，理论上排序和聚合看起来都严谨，但实测下来，数组版本因为缓存友好，反而快了接近一个数量级。这个现象用大O符号很难解释，但在真实硬件上就是那么残酷——常量因子、内存局部性，往往比渐进复杂度更能决定一个系统的最终性能。而“范围已知”恰好能让你在更多场景里选择那个常量极小、局部性极好的数组方案。

最后一个我个人的实操习惯：在代码注释里，把“为什么选这个算法”写下来。记录数据范围是多少、为什么认为范围可控、如果范围翻十倍应该怎么切换方案。这看起来像小事，但对后来维护代码的人来说（包括三个月后的自己），这比写十行“这段代码实现了XXX”有用得多。算法选型不是一锤子买卖，数据范围可能随着业务增长而变化，那时就是重新评估算法的时候。

以上就是我根据已知数据范围做算法选型的完整思路和实操经验。信息密度确实不低，但如果你在真实项目中遇到确定值域的数据，回来看一眼这六个问题，应该能少走不少弯路。