C++ Academy · 课时

性能考量

Q: 「性能考量」这节课中我会学到什么？

桶与负载因子 你通过在浏览器中直接运行的动手代码来练习 C++ Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

桶与负载因子

性能考量 是 CoddyKit 上的免费 C++ Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C++ Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C++ Academy 课程共包含 4 节课。

哈希表如何存储数据

无序容器包含一个由多个 bucket 组成的数组。键的哈希值会选择一个 bucket；同一个 bucket 中的多个键会形成一条链，并按线性方式搜索。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

哪个 bucket

bucket(key) 会告诉您某个键当前映射到哪个 bucket 索引。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

负载因子

负载因子为 size / bucket_count。负载越高，链就越长，查找速度也越慢。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

最大负载因子

max_load_factor() 是阈值。当负载因子超过该阈值时，哈希表会通过重新哈希扩展到更多 bucket。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

重新哈希

重新哈希会使用更多 bucket 重建哈希表，代价很高。当负载因子超过阈值时，它会自动发生。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

使用 reserve 避免重新哈希

如果您提前知道数据规模，请调用 reserve(n) 预先分配 bucket，以避免反复重新哈希。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

直接使用 rehash

rehash(n) 会将 bucket 数量设置为至少 n。请对元素数量使用 reserve，对 bucket 数量使用 rehash。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

检查 bucket 大小

bucket_size(i) 会显示共享 bucket i 的元素数量，有助于诊断冲突。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

最坏情况为 O(n)

如果哈希函数很差并产生大量冲突，所有键都会在一个 bucket 中形成链，操作会退化为线性时间。良好的哈希函数可以保持 O(1) 的性能。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

降低最大负载因子

设置较低的 max_load_factor 是用内存换速度：冲突会减少，但 bucket 会增加。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

迭代器失效

重新哈希会使迭代器失效，但会保持指向元素的引用和指针有效。请据此规划循环。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

快速检查

请检验您对哈希表性能的理解。

回顾

您学到了哈希表的内部机制：

键会映射到桶；冲突会形成链
负载因子 = 大小 / 桶数量；超过 max_load_factor 会触发重新哈希
使用 reserve 可以避免重新哈希；重新哈希会使迭代器失效，但不会使引用失效

下一课程：使用 fstream 读取和写入文件。

常见问题解答

「性能考量」课时是免费的吗？

是的 — 「性能考量」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C++ Academy 课程的其余内容，请升级到 CoddyKit PRO。 C++ Academy 课程共包含 4 节课。

「性能考量」这节课中我会学到什么？

桶与负载因子你通过在浏览器中直接运行的动手代码来练习 C++ Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C++ Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C++ Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「性能考量」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C++ Academy 课中编写并运行代码吗？

能。每节 C++ Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C++ Academy