C++ 第36题：为自定义结构体定制 std::hash 仿函数与 operator== 判等

题目

编写程序，设计自定义坐标结构体 Point2D { int x; int y; }，并将其作为 Key 存入 std::unordered_map<Point2D, std::string> 中。完整实现将其用于哈希表的两大必要前提：①在 std 命名空间中特化 std::hash<Point2D>（采用哈希混合算法合并各成员哈希值）；②重载 operator== 处理桶内哈希碰撞时的精准判等。

输入格式：无需外部输入。

输出格式：输出自定义结构体哈希值生成与在无序哈希表中的存取检索结果。

数据范围与约定：自定义类型哈希特化与碰撞判等契约。

思路与算法

1. 哈希表对 Key 的两大硬性要求
红黑树 map 只需要 operator<；而哈希 map 严格需要两样东西：①用于定位桶索引的哈希函数 hash(key)；②当同一个桶内存在多个节点碰撞时，用于逐个比对的判等函数 operator==。

2. 高质量哈希混合器（Hash Combine）
简单地将两个哈希值异或（h1 ^ h2）会导致 (1, 2) 和 (2, 1) 产生完全相同的哈希冲突。业界广泛使用 Boost 风格的位移加法混合常数：seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2) 极大分散雪崩效应。

3. 命名空间规则
在 std 命名空间中特化已有的模板类（如 struct hash<MyClass>）是 C++ 标准所明确允许且推荐的规范做法。

完整程序

#include <iostream>
#include <unordered_map>
#include <string>

struct Point2D {
    int x;
    int y;

    // 判等运算符：解决哈希碰撞时的节点唯一性判定
    bool operator==(const Point2D& other) const {
        return x == other.x && y == other.y;
    }
};

// 规范：在 std 命名空间内特化 std::hash<Point2D>
namespace std {
    template <>
    struct hash<Point2D> {
        size_t operator()(const Point2D& pt) const noexcept {
            size_t h1 = std::hash<int>{}(pt.x);
            size_t h2 = std::hash<int>{}(pt.y);
            // Boost Hash Combine 黄金分割混淆算法
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    };
}

int main() {
    std::unordered_map<Point2D, std::string> mapLandmarks;

    // 插入坐标标注
    mapLandmarks[{10, 20}] = "City Hall";
    mapLandmarks[{0, 0}] = "Origin Center";
    mapLandmarks[{10, 20}] = "City Hall (Updated)"; // 相同 Key 覆盖更新
    mapLandmarks[{20, 10}] = "Library";           // 对称坐标，检验哈希防碰撞

    std::cout << "地标图谱收录数量: " << mapLandmarks.size() << "\n\n";

    // 查询验证
    Point2D target{10, 20};
    auto it = mapLandmarks.find(target);
    if (it != mapLandmarks.end()) {
        std::cout << "成功查到坐标 (" << target.x << ", " << target.y << ") -> 地标名称: " << it->second << "\n";
    }

    Point2D mirror{20, 10};
    std::cout << "镜像坐标 (" << mirror.x << ", " << mirror.y << ") -> 地标名称: " << mapLandmarks[mirror] << "\n";

    return 0;
}

运行示例

输出：

地标图谱收录数量: 3

成功查到坐标 (10, 20) -> 地标名称: City Hall (Updated)
镜像坐标 (20, 10) -> 地标名称: Library