0Pricing
C++ Academy · 课时

自定义哈希函数

为您自己的类型计算哈希值

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

为什么需要自定义哈希

无序容器需要一种为键计算哈希的方法。内置类型和 std::string 已经提供哈希，但您自己的类型没有。您必须提供一个。

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

std::hash 模板

std::hash 是一个将值映射到 size_t 的函子。您可以像调用函数一样调用它。

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

用于哈希的结构体

假设我们有一个包含两个整数的 Point。要将它存储在无序集合中，我们需要同时提供相等判断和哈希。

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

编写哈希函子

哈希函子是一个返回 size_t 的结构体，其中包含 operator()。请组合各字段的哈希值，通常会使用 XOR 和移位。

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

使用哈希函子

将哈希函子作为无序容器的第二个模板参数传入。

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

同样必须提供相等判断

当哈希值发生冲突时，两个键会落入同一个 bucket。容器随后使用 operator== 区分它们，因此相等判断是必需的。

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

将哈希用于映射键

使用同一个自定义哈希，就可以将结构体作为 unordered_map 的键。

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

组合多个字段

一种常见的辅助函数会逐个字段组合哈希值，使用类似 boost::hash_combine 的乘法加法模式。

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

良好的哈希分布

如果糟糕的哈希函数始终返回同一个值，所有元素都会进入同一个 bucket，性能会退化为 O(n)。请充分混合所有字段的位。

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

特化 std::hash

另一种方法是为您的类型特化 std::hash，这样无需显式传入函子也能使用它。

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

将 Lambda 用作哈希

在 C++20 中，您甚至可以通过传入无状态 Lambda 的类型，将它用作哈希。

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

快速检查

请测试您对自定义哈希的理解。

总结

您已经学会如何为自定义类型进行哈希：

  • 提供一个返回 size_t 的哈希函子（或特化 std::hash）
  • 同时提供 operator==，以区分发生冲突的键
  • 妥善组合各字段的哈希值，以获得良好的分布

接下来，您将探索 bucket 和负载因子对性能的影响。

常见问题解答

「自定义哈希函数」课时是免费的吗？

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

「自定义哈希函数」这节课中我会学到什么？

为您自己的类型计算哈希值 你通过在浏览器中直接运行的动手代码来练习 C++ Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

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

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

「自定义哈希函数」课时需要多长时间？

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

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

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

此课程中的所有课时

  1. std::unordered_map
  2. unordered_set
  3. 自定义哈希函数
  4. 性能考量
← 返回 C++ Academy