免费模型通过全部单元测试，复杂度曲线暴露O(n²)性能陷阱 | 前端进阶之旅

Full translation

完整中文译文

单元测试证明了正确性，但没有证明复杂度。这不是一个关于测试失败的故事，而是一个关于代码仍有缺陷、测试却全部通过的故事。

在本次案例研究中，一个免费模型的 C++ 哈希表通过了全部 42 个单元测试和两个 Sanitizer 工具，然后在插入 100,000 个真实键时耗时 4.2 秒。扩展曲线在三组数据中暴露了 O(n²) 的碰撞模式。修复只花了一轮。

我使用 MonkeyCode 的免费模型访问生成第一版代码，并在其免费服务器选项上运行验证门控，因此整个过程中编译器、编译参数和环境保持完全一致。声明：本文是 MonkeyCode 产品推广的一部分。

我需要一个用于日志去重工具的小型字符串键映射。热路径读取一行，提取类似 2026-08-23T10:15:30 node=7 seq=000123 这样的键，然后对唯一键计数。映射表就是性能瓶颈。

需求很明确：C++17，仅此而已，无外部依赖，分摊后 O(1) 的插入预期，以及 100,000 次插入在 100ms 内完成。最后一条需求是一份复杂度契约，而非风格偏好。

验收标准如下：

AddressSanitizer 和 UndefinedBehaviorSanitizer 无任何报告。

插入 100,000 个结构化键在 100ms 内完成。

第三条标准是大多数验证流水线都会遗漏的一项。本案例研究要回答的就是：为什么遗漏这一项代价高昂。

模型生成的是一个使用 2 的幂容量的链式哈希表。结构中规中矩，但哈希函数不是：

size_t hash(const std::string& key) const {
    size_t h = 0;
    for (size_t i = 0; i < key.size() && i < 4; ++i) {
        h = (h << 8) | static_cast<unsigned char>(key[i]);
    }
    return h & (capacity_ - 1);
}

键只有前四个字节参与哈希运算。插入路径看起来没问题：

void insert(const std::string& key) {
    size_t idx = hash(key);
    for (auto* node = buckets_[idx]; node; node = node->next) {
        if (node->key == key) return;
    }
    buckets_[idx] = new Node{key, buckets_[idx]};
    ++size_;
}

我的日志数据中每个键都以 2026 开头。它们全部哈希到了同一个桶。每次插入都在扫描一条不断增长的链表。

我按顺序跑了三个阶段。第一阶段是带警告和 Sanitizer 的编译：

g++ -std=c++17 -Wall -Wextra -O1 -fsanitize=address,undefined -o map_test map_test.cpp
./map_test

全部 42 个单元测试通过。ASan 和 UBSan 默不作声。第二阶段是扩展性基准测试：

#include <chrono>
#include <iostream>
#include <string>

int main(int argc, char** argv) {
    const size_t n = std::stoull(argv[1]);
    StringMap map;
    auto start = std::chrono::steady_clock::now();
    for (size_t i = 0; i < n; ++i) {
        std::string key = "2026-08-23T10:15:30 node=7 seq=" + std::to_string(i);
        map.insert(key);
    }
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(
                  std::chrono::steady_clock::now() - start)
                  .count();
    std::cout << n << " " << ms << "ms\n";
}

第三阶段是决策规则。我在 N、2N 和 4N 下运行基准测试，然后比较比值：

for n in 25000 50000 100000; do
  ./map_bench "$n"
done

第一次运行得到：

25000  262ms
50000  1048ms
100000 4197ms

输入翻倍，时间变为四倍。这就是 O(n²) 的特征，仅凭三个数字就能看出来。不需要 Profiler，不需要火焰图，不需要猜测。

我把扩展表反馈给模型，只加了一条指令：哈希必须使用整个键。第二个版本用 std::hash<std::string> 替换了手写的哈希函数：

size_t hash(const std::string& key) const {
    return std::hash<std::string>{}(key) & (capacity_ - 1);
}

25000  9ms
50000  19ms
100000 38ms

输入翻倍，时间也翻倍。同样的 42 个单元测试仍然全部通过。正确性没有任何改变。第一版代码是正确的，同时也是不可用的。

我现在使用的规则是：如果 time(2N) / time(N) 高于 3，就停下来检查算法，在此之前不动任何东西。比值接近 2 意味着线性。接近 4 意味着二次。基准测试耗时约一秒，替换掉的是数小时的猜测。

首先，测试全绿不是性能通行证。42 个单元测试使用的是 alpha 和 beta 这样简短的、不同键名的键。它们的前四个字节各不相同，因此分散到了各个桶中。测试从未模拟过生产数据会产生的分布。

其次，扩展性基准测试是我所知道的最便宜的复杂度检测器。三次运行、一个 shell 循环、一个比值。它发现了一个 Sanitizer、警告和看起来正确的代码审查都漏掉的缺陷。

第三，环境很重要。我在 MonkeyCode 的免费服务器选项上运行了每个阶段，这意味着编译器在每轮中完全一致。如果基准测试在我的笔记本电脑上运行，热节流可能以错误的原因产生相同的 4x 比值。

第四，修复不是重写。只是给哈希函数改了一行代码。模型的结构是合理的，只是分布被破坏了。这是一种常见的失效模式，而且捕获成本很低。

本案例研究范围狭窄。前缀哈希缺陷只在键共享前缀时出现。随机键或短键可能永远不会触发它，这意味着在大多数时候这个门控看起来并不必要，直到某一天它突然变得必要。

不要对只读工作负载、固定字典的场景使用这个方案。带二分查找的有序向量会击败任何哈希表，不管是生成的还是手写的。不要在需要线程安全的地方使用生成的哈希表；这个是单线程设计的。

免费服务器选项是一个验证环境，不是生产主机。我用它来门控代码，而不是提供服务。一个小的 C++17 项目并不是对免费模型的通用判决。可复用的产物是方法：编译、Sanitize、扩展、决策。

如果你在生成的代码上运行了类似门控，把扩展曲线发给我。我想要的是形状，不只是通过/失败。