面试题：C++ 关联容器性能分析及优化的数据检索策略

Question

假设有一个存储大量学生信息（学号作为键，学生对象作为值）的 `std::unordered_map`，在频繁进行学号检索操作时，发现性能不理想。请分析可能导致性能问题的原因，并提出至少两种优化检索性能的策略，同时说明每种策略在 C++ 中的实现方式。

Answer 1

可能导致性能问题的原因

1. 哈希函数不合理：如果哈希函数对学号的分布不均匀，会导致大量元素被分配到同一个桶（bucket）中，增加查找时间，形成哈希冲突。
2. 负载因子过大：std::unordered_map 有一个负载因子（load factor），当元素数量与桶的数量比例超过一定阈值（默认 1.0）时，哈希冲突的概率会显著增加，导致查找性能下降。
3. 桶的数量过少：初始桶的数量设置不合理，过少的桶数量在元素增加时容易引发哈希冲突。

优化检索性能的策略及实现方式

1. 优化哈希函数
   • 实现方式：自定义哈希函数。例如，如果学号是整数类型，可以根据学号的特性设计一个更均匀分布的哈希函数。假设学号是 int 类型：

struct CustomHash {
    std::size_t operator()(int id) const {
        // 这里可以使用更复杂的哈希算法，比如 Jenkins hash
        return static_cast<std::size_t>(id);
    }
};
std::unordered_map<int, Student, CustomHash> studentMap;

2. 调整负载因子
   • 实现方式：在构造 std::unordered_map 时设置负载因子。例如，将负载因子设置为较低的值（如 0.75）可以减少哈希冲突：

std::unordered_map<int, Student> studentMap(100, 0.75); 
// 100 为初始桶数量，0.75 为负载因子

3. 增加初始桶数量
   • 实现方式：在构造 std::unordered_map 时指定一个合适的初始桶数量。根据预估的学生信息数量，设置一个足够大的初始桶数量，减少动态扩容的次数：

std::unordered_map<int, Student> studentMap(1000); 
// 初始桶数量设为 1000