我去年处理过一个挺有意思的活儿：某内部工具需要在上亿条日志里按时间窗口做聚合统计，数据的时间戳全部落在最近三个月内。一开始我按教科书思路上了红黑树、跳表这类“高级”结构，结果在真实数据上跑得还不如后来换上的一个普通数组快。原因很简单——我知道时间戳的确定范围，明明可以用直接定址的思路，偏要去搞那些对范围无感的通用结构。这件事给我的教训很直接：算法选型先看数据范围，范围一旦已知，很多“复杂度更优”的通用方案反而会被一个最朴素的数组下标干掉。这篇内容就想把“根据已知数据范围选择算法”这个话题掰开揉碎。我适合以下人群阅读：写业务代码时经常面对确定值域的数据（比如用户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 数据范围如何改变“最优解”的定义数据范围至少包含以下几个维度，每个维度都直接影响选型：维度含义示例影响的算法选择值域上界 U元素最大可能取值0 ~ 10^5、0 ~ 2^31-1决定能否用数组直接定址连续性值域是否基本连续用户ID是否从0递增分配决定数组是否浪费空间密集程度实际出现的元素数量 vs 值域大小稀疏与密集数组 vs 哈希表重复程度是否有大量重复元素状态枚举值计数排序 vs 比较排序偏移量最小值是否远大于0时间戳、ID从大数开始是否做映射、平移分布形态均匀、偏斜、幂律长尾数据基数排序 vs 计数排序举一个直观类比：假设你要给一万个盒子贴上对应编号的标签，每个盒子上的编号从 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”有用得多。算法选型不是一锤子买卖，数据范围可能随着业务增长而变化，那时就是重新评估算法的时候。以上就是我根据已知数据范围做算法选型的完整思路和实操经验。信息密度确实不低，但如果你在真实项目中遇到确定值域的数据，回来看一眼这六个问题，应该能少走不少弯路。
我去年处理过一个挺有意思的活儿：某内部工具需要在上亿条日志里按时间窗口做聚合统计，数据的时间戳全部落在最近三个月内。一开始我按教科书思路上了红黑树、跳表这类“高级”结构，结果在真实数据上跑得还不如后来换上的一个普通数组快。原因很简单——我知道时间戳的确定范围，明明可以用直接定址的思路，偏要去搞那些对范围无感的通用结构。这件事给我的教训很直接：算法选型先看数据范围，范围一旦已知，很多“复杂度更优”的通用方案反而会被一个最朴素的数组下标干掉。这篇内容就想把“根据已知数据范围选择算法”这个话题掰开揉碎。我适合以下人群阅读：写业务代码时经常面对确定值域的数据（比如用户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 数据范围如何改变“最优解”的定义数据范围至少包含以下几个维度，每个维度都直接影响选型：维度含义示例影响的算法选择值域上界 U元素最大可能取值0 ~ 10^5、0 ~ 2^31-1决定能否用数组直接定址连续性值域是否基本连续用户ID是否从0递增分配决定数组是否浪费空间密集程度实际出现的元素数量 vs 值域大小稀疏与密集数组 vs 哈希表重复程度是否有大量重复元素状态枚举值计数排序 vs 比较排序偏移量最小值是否远大于0时间戳、ID从大数开始是否做映射、平移分布形态均匀、偏斜、幂律长尾数据基数排序 vs 计数排序举一个直观类比：假设你要给一万个盒子贴上对应编号的标签，每个盒子上的编号从 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”有用得多。算法选型不是一锤子买卖，数据范围可能随着业务增长而变化，那时就是重新评估算法的时候。以上就是我根据已知数据范围做算法选型的完整思路和实操经验。信息密度确实不低，但如果你在真实项目中遇到确定值域的数据，回来看一眼这六个问题，应该能少走不少弯路。