自定义哈希函数与等价比较——给特殊物品定制储物柜规则

你有没有想过，为什么我们的书包里能轻松找到数学书，而一堆杂物却很难翻到想要的东西？因为书本有固定的分类和标签（比如学科、年级），而杂物没有统一的规则。在编程中，unordered_set和unordered_map就像是一个智能储物柜，它们能快速存取物品，但前提是物品有可计算的“编号”（哈希值）和判断是否相同的规则（等价比较）。对于整数、字符串这些标准类型，C++和Python已经帮我们准备好了这些规则。但如果你有一个自定义的类型（比如“学生”结构体，包含姓名和学号），储物柜就不认识它了——这时，你需要亲手教它两件事：

如何根据你的物品算出一个号码（哈希值）：就像给每个学生分配学号，储物柜用这个号码决定把学生放在哪个格子。
如何判断两个物品是否相同（相等比较）：就像学校规定“学号相同就是同一个人”，即使姓名写错了也不行。

生活中的类比——图书馆借书与学号牌

假设图书馆里每本书都贴着一个唯一的条形码。管理员扫描条形码（哈希函数），就能知道书应该放在哪个书架上（桶的位置）。如果要找一本书，他只需要扫描条码，然后去对应的书架上找。如果两本书的条形码一样（但通常不会），那它们就是同一本书。对于你自己的“学生”对象，你要做的就是设计出“条形码生成规则”和“匹配规则”。

哈希函数：你把学生对象扔进去，它吐出一个整数（通常是一个大范围数字）。这个整数就像条形码，告诉容器学生应该放在哪个桶里。
等价比较：当容器发现有两个不同的学生对象（比如姓名不同）被算到了同一个桶（哈希冲突），它需要判断它们是不是同一个学生。你的规则决定了：学号相同就算同一个。

C++中的实现方式

C++的unordered_set和unordered_map底层是哈希表，它们依赖两个模板参数：哈希函数和等价比较。默认情况下，哈希函数是std::hash<Key>，等价比较是std::equal_to<Key>（它会调用operator==）。对于自定义类型，你有两种方式让它被容器接受：

方式一：重载operator==，并特化std::hash。这样你的类型就可以像内置类型一样直接使用容器。
方式二：提供自定义的仿函数（函数对象）作为模板参数，不修改类本身（适用于类定义不可修改的情况）。

方式一完整示例：重载`operator==`并特化`std::hash`

下面我们定义一个Student结构体，包含姓名和学号。我们规定：学号相同即为同一个学生。

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

// 定义学生结构体
struct Student {
    string name;   // 姓名
    int id;        // 学号

    // 重载 operator==，用于等价比较
    // 规定：学号相同 => 两个学生相等
    bool operator==(const Student& other) const {
        return id == other.id;
    }
};

// 特化 std::hash<Student>，让 unordered_set 知道如何计算哈希值
namespace std {
    template<>
    struct hash<Student> {
        // 计算 Student 对象的哈希值
        size_t operator()(const Student& s) const {
            // 直接使用学号的哈希值作为学生的哈希值
            // 注意：如果两个学生学号不同，但姓名相同，这个哈希也能区分它们
            return hash<int>()(s.id);
        }
    };
}

int main() {
    // 创建一个存放 Student 的 unordered_set
    unordered_set<Student> students;

    // 插入几个学生
    students.insert({"Alice", 1001});   // 姓名Alice，学号1001
    students.insert({"Bob", 1002});     // 姓名Bob，学号1002
    students.insert({"Charlie", 1003}); // 姓名Charlie，学号1003

    // 尝试插入一个学号相同的“新”学生（虽然姓名是David）
    auto result = students.insert({"David", 1002});  // 学号1002已存在
    if (result.second == false) {
        cout << "插入失败！学号1002的学生已经存在（Bob）" << endl;
    }

    // 查找学号为1002的学生
    Student target = {"", 1002};  // 查找时我们只关心学号，姓名可以空着
    auto it = students.find(target);
    if (it != students.end()) {
        cout << "找到了！姓名：" << it->name << "，学号：" << it->id << endl;
    }

    // 遍历所有学生
    cout << "当前所有学生：" << endl;
    for (const auto& s : students) {
        cout << "  " << s.name << " (学号 " << s.id << ")" << endl;
    }

    return 0;
}

方式二完整示例：使用仿函数作为模板参数

如果你不能修改Student类（例如它是第三方库提供的），可以用仿函数的方式。

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

// 学生类，没有重载 operator==，也没有特化 hash
struct Student {
    string name;
    int id;
};

// 自定义哈希仿函数
struct StudentHash {
    size_t operator()(const Student& s) const {
        // 使用学号作为哈希值
        return hash<int>()(s.id);
    }
};

// 自定义等价比较仿函数
struct StudentEqual {
    bool operator()(const Student& a, const Student& b) const {
        // 学号相同视为相等
        return a.id == b.id;
    }
};

int main() {
    // 创建 unordered_set，需要指定三个模板参数：
    // 键类型、哈希仿函数、等价比较仿函数
    unordered_set<Student, StudentHash, StudentEqual> students;

    // 插入学生
    students.insert({"Alice", 1001});
    students.insert({"Bob", 1002});

    // 查找
    Student target = {"", 1002};
    auto it = students.find(target);
    if (it != students.end()) {
        cout << "找到：" << it->name << " (学号 " << it->id << ")" << endl;
    }

    return 0;
}

用于 unordered_map 的自定义键

unordered_map的键也需要同样的处理。下面演示将Student作为键，存储其成绩。

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

struct Student {
    string name;
    int id;
    // 重载 operator==
    bool operator==(const Student& other) const {
        return id == other.id;
    }
};

// 特化 hash
namespace std {
    template<> struct hash<Student> {
        size_t operator()(const Student& s) const {
            return hash<int>()(s.id);
        }
    };
}

int main() {
    // unordered_map 的键是 Student，值是 double（成绩）
    unordered_map<Student, double> scoreMap;

    // 插入键值对
    scoreMap[{"Alice", 1001}] = 95.5;
    scoreMap[{"Bob", 1002}] = 88.0;

    // 查找学号1001的学生成绩
    Student key = {"", 1001};
    auto it = scoreMap.find(key);
    if (it != scoreMap.end()) {
        cout << "Alice 的成绩是：" << it->second << endl;
    }

    return 0;
}

Python 中的实现方式

在 Python 中，要使自定义对象可以放入 set 或作为 dict 的键，需要定义 __eq__ 和 __hash__ 两个特殊方法。规则与 C++ 相同：a == b 为 True 时，hash(a) 必须等于 hash(b)。下面给出完整的 Python 示例。

class Student:
    def __init__(self, name, id):
        self.name = name   # 姓名
        self.id = id       # 学号

    # 定义 __eq__，用于判断两个学生是否相等
    def __eq__(self, other):
        if not isinstance(other, Student):
            return NotImplemented  # 如果不是Student类型，返回NotImplemented
        # 规定：学号相同即视为同一学生
        return self.id == other.id

    # 定义 __hash__，用于计算哈希值
    def __hash__(self):
        # 直接使用学号的哈希值
        return hash(self.id)

    # 定义 __repr__，方便打印显示
    def __repr__(self):
        return f"Student({self.name}, {self.id})"

# 创建几个学生对象
alice = Student("Alice", 1001)
bob = Student("Bob", 1002)
charlie = Student("Charlie", 1003)
david = Student("David", 1002)   # 学号与 bob 相同

# 放入集合
students_set = {alice, bob, charlie}
print("初始集合长度：", len(students_set))  # 输出 3

# 尝试添加 david
students_set.add(david)
print("添加 David 后集合长度：", len(students_set))  # 仍然是 3，因为 david 与 bob 相等

# 查找：使用 in 运算符（它会调用 __eq__ 和 __hash__）
target = Student("", 1002)
print("学号1002的学生在集合中吗？", target in students_set)  # True

# 作为字典的键
grades = {alice: 95.5, bob: 88.0}
print("学号1002的学生成绩：", grades.get(Student("", 1002)))  # 输出 88.0

重要提示：Python 要求 __eq__ 和 __hash__ 必须一致。而且，一旦对象被放入集合或字典，它的哈希值所依赖的属性不应该再被修改，否则会破坏容器内部结构。因此，通常建议将作为键的属性设为只读（例如使用 @property）或使用不可变对象。

新手容易犯的错误

只重载了 operator== 却忘记特化 std::hash（C++）
编译时报错：static_assert failed due to requirement ... hash not available。两者必须同时提供。
特化了 std::hash 但 operator== 返回的结果与哈希函数不一致
例如：operator== 用学号判断，而哈希函数用了姓名。这样会违反“相等对象哈希值必须相等”的规则，导致容器行为异常（明明相等的对象却找不到，或者出现重复元素）。
正确做法：哈希函数和比较函数必须基于相同的属性（比如都用学号）。
修改了已放入容器中的对象的哈希属性
比如你先将 Student("Alice", 1001) 插入集合，然后修改它的 id 为 2000。此时哈希值已经改变，但容器还把它放在原来的桶里，之后所有操作（查找、删除）都会出错。
解决办法：如果对象需要作为键，最好设计为不可变对象，或者在插入后绝不修改相关属性。
Python 中忘记定义 __hash__
如果你只定义了 __eq__ 而没有定义 __hash__，Python 会将该对象的 __hash__ 设为 None，类型变为不可哈希（unhashable），放入 set 会抛出 TypeError。
哈希函数写得不好，导致大量冲突
例如所有学生都返回 0，那么所有对象都会挤在同一个桶里，查找退化为线性搜索，效率极低。
好的做法：对于多成员结构体，可以组合各成员的哈希值，比如 hash1 ^ (hash2 << 1) 或使用 boost::hash_combine（C++）。Python 中可以利用 hash((self.attr1, self.attr2)) 组合多个不可变属性的哈希。

总结

自定义类型要放入 unordered_set / unordered_map（C++）或 set / dict（Python），必须提供哈希函数和等价比较。
哈希函数的黄金法则是：如果两个对象相等，它们的哈希值必须相等。
C++ 有两种方式：重载 operator== + 特化 std::hash；或提供自定义仿函数。
Python 中定义 __eq__ 和 __hash__。
不要把哈希依赖的属性在放入容器后修改。
尽量让哈希函数分散，避免冲突。

掌握了这些知识，你就能像定制专用储物柜一样，把任何复杂对象高效地塞进哈希表，享受 O(1) 的平均查找速度。如果你还想了解哈希表的底层原理（比如冲突解决、负载因子、rehash），或者想深入学习 C++ 的 std::hash 特化与 boost::hash_combine，可以参考后续的“哈希表进阶”与“性能优化”章节。

例题精讲