unordered：哈希、等价与 rehash

Hash 与 KeyEqual 是共同契约

哈希值不是唯一编号，不同键允许碰撞。KeyEqual 决定两个键是否等价，Hash 必须保证等价键得到相同哈希值；反方向不成立。相等谓词要满足等价关系，键存放期间两种函数对同一键的结果都必须保持一致。

示例的 Account 只按 id 识别身份，显示名不参与哈希或相等判断，因此同 id 的两个对象只占一个位置。若相等判断忽略大小写，哈希也必须按同样规则规范化字符；只改其中一个会违反容器要求，而不是单纯让性能差一点。

平均常数背后的桶与负载

查找、普通单元素插入和按键删除通常具有平均常数复杂度，最坏情况可退化到线性；恶劣分布甚至对抗性输入能让许多键集中到少数桶。标准没有承诺某个质数桶表、固定增长倍率或某种哈希算法，也不保证遍历顺序是插入顺序。

load_factor() 是元素数除以桶数，max_load_factor() 控制允许的平均负载。批量构建时先设置负载策略，再 reserve(expected_count)；这里参数是元素数，而 rehash(bucket_count) 的参数是桶数下限，还必须满足当前元素数对应的负载要求。不能断言请求 100 个桶后桶数恰好为 100，也不应靠降低负载修复错误哈希。

重排桶不会搬走元素身份

rehash 会使迭代器失效，并可能改变遍历顺序，却不使元素引用和指针失效。插入若没有触发 rehash，则保持已有迭代器有效；删除只使被删元素句柄失效。因此迭代期间插入新键需要明确容量条件，保守且容易维护的办法是先收集修改，再批量执行。

示例保存元素指针后请求更多桶，随后通过重新 find 获取迭代器，验证对象仍在同一地址。指针稳定不等于生命周期无限：erase、clear 和容器销毁仍结束相应对象的生存期。输出需要稳定顺序时应另行排序键，不要把某次本机遍历顺序写成协议或测试预期。

最低标准 C++11 · 完整程序 · 下载 .cpp

#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>

struct Account { int id; std::string name; };
struct HashId {
    std::size_t operator()(const Account& a) const {
        return std::hash<int>{}(a.id);
    }
};
struct EqualId {
    bool operator()(const Account& a, const Account& b) const {
        return a.id == b.id;
    }
};

int main() {
    std::unordered_set<Account, HashId, EqualId> accounts;
    accounts.max_load_factor(0.75f);
    accounts.reserve(8);
    auto inserted = accounts.insert(Account{7, "Ada"});
    auto duplicate = accounts.insert(Account{7, "Alias"});
    assert(inserted.second && !duplicate.second);
    const Account* saved = &*inserted.first;
    accounts.rehash(accounts.bucket_count() + 1);
    auto found = accounts.find(Account{7, "ignored"});
    assert(found != accounts.end() && &*found == saved);
    assert(saved->name == "Ada" && accounts.size() == 1);
    std::cout << saved->id << ' ' << saved->name << '\n';
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-unordered.cpp -o example && ./example

预期结果

7 Ada

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

一个哈希函数总返回 0，但相等谓词正确。这是否违反 unordered_set 的正确性要求？reserve 能否彻底解决其查找成本？

继续查证

• 标准草案 [unord.req]：哈希一致性、负载和迭代器失效

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。