c++如何自定义哈希函数用于unordered_map_c++ unordered_map自定义哈希示例

冰火之心 2025-11-11 00:00:00 次阅读

要使用自定义类型作为unordered_map的键，需定义哈希函数对象并重载operator==。1. 自定义结构体需实现==运算符用于比较；2. 定义仿函数重载operator()返回size_t，可结合std::hash与推荐的哈希混合方式（如0x9e3779b9异或移位）提升均匀性；3. 模板参数传入自定义哈希类型，不可用lambda但可用仿函数。示例中Point结构体通过PointHash实现键功能，确保哈希唯一性与相等比较正确性。

在C++中，unordered_map 使用哈希表实现，其键类型需要能够被哈希函数处理。标准库为常见类型（如 int、string）提供了默认哈希函数，但如果你使用自定义类型（如结构体或类）作为键，就需要提供自己的哈希函数。

如何自定义哈希函数

要让自定义类型用于 unordered_map，你需要做两件事：

定义一个哈希函数对象（仿函数），重载 operator()，返回 size_t
确保该类型支持 == 比较操作（用于处理哈希冲突）

示例：用结构体作为 unordered_map 的键

假设你想用一个表示二维点的结构体作为键：

#include 
#include 
#include 

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
    
    // 必须定义 operator== 用于比较
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数对象
struct PointHash {
    size_t operator()(const Point& p) const {
        // 简单哈希：将 x 和 y 混合
        return std::hash{}(p.x) ^ (std::hash{}(p.y) << 1);
    }
};

int main() {
    std::unordered_map pointMap;
    
    pointMap[Point(1, 2)] = "Point A";
    pointMap[Point(3, 4)] = "Point B";

    for (const auto& [point, label] : pointMap) {
        std::cout << "Key: (" << point.x << ", " << point.y 
                  << ") Value: " << label << "\n";
    }

    return 0;
}

使用 lambda 或函数指针的限制

不能直接传 lambda 给 unordered_map 模板参数，因为模板需要类型，而 lambda 类型是唯一的且无法写出。但你可以使用函数对象或 std::function 包装，不过更推荐仿函数方式。

更好的哈希组合方法

上面用 ^ 和位移组合哈希值简单但不够均匀。推荐使用更健壮的方法：

struct PointHash {
    size_t operator()(const Point& p) const {
        size_t hx = std::hash{}(p.x);
        size_t hy = std::hash{}(p.y);
        // 推荐的哈希合并方式
        return hx ^ (hy + 0x9e3779b9 + (hx << 6) + (hx >> 2));
    }
};

或者参考 Boost 的哈希组合方式，避免冲突。