我们在实现一些算法题的时候，难免会遇到需要哈希表储存坐标的场景，但是我们发现使用例如unordered_set<pair<int,int>> 时编译器会报错，这是因为容器unordered_set的三个模板参数分别为:

template <class _Kty, class _Hasher = hash<_Kty>, class _Keyeq = equal_to<_Kty>

其中第一个参数_Kty就是我们要储存的数据类型。

第二个_Hasher将键(_Kty)映射到一个size_t类型的哈希值，决定元素在哈希表中的存储位置（即哪个“桶”），其中默认参数hash<_Kty>,它就是负责处理键映射的函数，是标准库里的，存在于<functional>头文件中，它可以对内置类型数据进行哈希映射,比如int,char....以及string。

第三个参数_Keyeq = equal_to<_Kty>，它的核心作用是精确判断两个键是否相等，哈希函数 (_Hasher) 负责将键映射到哈希表的某个“桶”中。但不同的键可能计算出相同的哈希值，这就是哈希冲突，当冲突发生，多个元素被放入同一个桶后（通常以链表形式组织），unordered_set需要在这个桶内遍历，并使用 _Keyeq来逐一比较，从而找到确切的目标键或确定新键是否已存在，例如，即使两个不同的字符串 "apple"和 "pear"万一哈希到了同一个桶，_Keyeq会确保它们能被正确区分，并且确保哈希表里的数据唯一

啰嗦了这么多，我们就先来看看如何才能用哈希表储存坐标吧

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

struct Hasher
{
	size_t operator()(const pair<int,int>& p) const
	{
		hash<int> ha;
		size_t h1 = ha(p.first);
		size_t h2 = ha(p.second);
		return h1 ^ (h2 << 1);
	}
};

int main()
{
	unordered_set<pair<int,int>,Hasher> s;
	s.insert({ 1,1 });
	s.insert({ 1,2 });
	s.insert({ 1,3 });
	return 0;
}

如此以来，我们就完成了对坐标的储存，但是这里面有几个很坑的地方我会先介绍再解释:

1.哈希函数返回的值必须是size_t，不然程序会报错，因为我们使用了库里的hash<int>函数（当然你要是要弄string就写hash<string>）返回值是size_t。

2.所传值必须是const pair<>& 后面再加const修饰,这里每一步都不能错，不然就会报错，我下面会根据一些STL库的实现（不贴出代码了，大家可以在自己的编译器上转到定义看看）深刻的说明原因，只对哈希表使用有需求的同学可以跳过下面这部分：(深黑色)

函数参数问题：库里unordered_set的insert,erase,find操作所需的传值都是const _Key& val,而在这些函数里我们是要调用（Hasher）operator()(pair<int,int>)的，你不加const相当于造成了权限的放大，这是不被允许的。问题本质是对象作为参数传入时的权限放大。

现在我们来谈谈为什么还得加个const来修饰这个仿函数,那是因为我们有可能设计一个const unordered_set类型的变量，加上设计这个容器本身就不希望改变储存的值，所以const 对象和普通对象是共用一个operator()的（我都用模板了你总不能让我写一个普通的再写一个const的吧），这也就是不加const修饰函数会报错的原因，同样造成了权限放大。

至此，我们实现了对pair<>类型的储存，现在我来介绍第三个模板参数_Keyeq的作用，它是为了重载＝号，像一些内置类型和string，pair<>，已经在类里重载了operator==,那么如果我们想用unordered_set储存自定义类型，我们就必须在自定义类型类中重载一下==运算符，不然容器是无法正常工作的，下面我用一段简洁的代码演示一下

#include <unordered_set>
#include <string>

struct Person {
    std::string name;
    std::string id_card; // 身份证号，作为唯一标识
    int age;
};

// 1. 自定义哈希函数（第二个模板参数）
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>{}(p.id_card); // 仅对身份证号哈希
    }
};

// 2. 自定义相等比较函数（第三个模板参数 _Keyeq）
struct PersonEqual {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.id_card == p2.id_card; // 仅比较身份证号是否相同
    }
};

// 使用自定义的 Hash 和 KeyEqual 来实例化 unordered_set
std::unordered_set<Person, PersonHash, PersonEqual> people_set;

// 现在可以这样使用
people_set.insert({"Alice", "123456789012345678", 30});
people_set.insert({"Bob", "123456789012345678", 25}); 
// 这个插入会失败，因为身份证号与Alice相同，KeyEqual认为键已存在

解决上图最后的插入失败问题，我们只需改写一些PersonEqual函数即可，当然了映射那里也可以加上对名字的映射。

说完了unordered_set其实也就说完了unordered_map，因为它们其实是通过模板参数实现了同一个模板稍微修改一下就是另一个，这个有趣的操作具体实现感兴趣的话可以看看我的上一篇博客，相信会让刚学习STL的你受益匪浅。

文章的最后，我们再用模板来提供一个简单的pair<T1，T2>的哈希仿函数（还有个小点就是如果你头文件没有包含两种哈希表还想用库里的hash函数那就加上头文件functional）

struct PairHash 
{
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1, T2> &p) const 
    {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 << 1);
    }
};

std::unordered_map<std::pair<int, int>, std::string, PairHash> myMap;