前言

关于如何卡 unordered_map，codeforce上已经有传烂掉牙的教程了

这里不阐述 C++ 中unordered_map具体的实现原理和解析，我们只讨论如何优化。

基本原理

在 STL 中，unordered_map的类签名如下

template <typename _Key, typename _Tp, typename _Hash = hash<_Key>,
          typename _Pred = equal_to<_Key>,
          typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
class unordered_map {}

可以看出我们是可以自己传入哈希函数和比较函数的。大部分情况下我们只需要优化哈希函数，避免哈希冲突带来的性能损失即可。

此外，我们 gcc 的拓展库中还有 gp_hash_table 的探测法实现的哈希表，用他可以避免 unordered_map 的桶溢出问题，进一步提速。其中类签名如下

template <typename Key, typename Mapped,
          typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
          typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
          typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
          typename Probe_Fn =
              typename detail::default_probe_fn<Comb_Probe_Fn>::type,
          typename Resize_Policy =
              typename detail::default_resize_policy<Comb_Probe_Fn>::type,
          bool Store_Hash = detail::default_store_hash,
          typename _Alloc = std::allocator<char>>
class gp_hash_table
    : public basic_hash_table<
          Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, gp_hash_tag,
          typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type,
          _Alloc> {}

gp_hash_table 快是快，不过代价就是依赖于评测环境。不过好在目前大部分评测环境都已经是 gcc/clang 编译，采用gcc-libs。不过保险期间我们还是加上条件编译，避免CE。

参考实现代码

这里我们采用 splitmix64 算法来避免被卡哈希

// 若需要添加其他类型的自定义哈希函数，请参考如下 std::pair 的哈希实现
template <typename T1, typename T2> struct hash<pair<T1, T2>> {
    size_t inline operator()(const std::pair<T1, T2> &p) const noexcept {
        size_t seed = std::hash<T1>()(p.first);
        seed ^=
            std::hash<T2>()(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

// 随机数生成器，使用 Unix 时间戳作为种子
static mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
// 自定义哈希功能类
template <typename T> struct CustomHash {
    // 哈希函数（splitmix64 算法结合随机数实现，可以很好的防卡哈希）
    size_t inline operator()(T _x) const noexcept {
        static auto const UNIX_TIME =
            chrono::steady_clock::now().time_since_epoch().count();
        static const hash<T> HASHER; // 兼容原先就支持哈希的类型
        size_t x = HASHER(_x) + UNIX_TIME;
        static const size_t v1{rnd()}, v2{rnd()}, v3{rnd()};
        x += v1;
        x = (x ^ (x >> 33)) * v2;
        x = (x ^ (x >> 30)) * v3;
        return x;
    }
};
// 条件编译，根据不同的编译器选择对应的别名对象
#ifdef _MSC_VER // 玄学 MSVC，一般就 codeforce 会有 winlibs 评测了
template <typename Key, typename Value>
using HashMap = unordered_map<Key, Value, CustomHash<Key>>;
template <typename T> using HashSet = unordered_set<T, CustomHash<T>>;
#else // 通常来说会有这个库，gcc基本都有，里面还有平衡树，字典树什么的
#include <bits/extc++.h> // 用 gp_hash_table 替代，探测法就是比拉链快
template <typename Key, typename Value>
using HashMap = __gnu_pbds::gp_hash_table<Key, Value, CustomHash<Key>>;
template <typename T>
using HashSet =
    __gnu_pbds::gp_hash_table<T, __gnu_pbds::null_type, CustomHash<T>>;
#endif

再举个例子，以免有同学看不懂自定义哈希方法

比如说我有一个结构体如下

struct Point3D {
    int x, y, z;
};

我希望用它当 unordered_map 或者是我已经别名好的 HashMap 的键（也就是下标）。如果我直接用，会有以下错误。

In template: static assertion failed due to requirement 'is_copy_constructible<std::hash<Point3D>>::value': hash function must be copy constructible

问题出在，我们的 Point3D 没有实现 std::hash 的哈希函数，哈希表不知道如何映射我们这个键的类型，所以报错。解决这个办法很简单，我们只需要一个 std::hash 的泛型特化实现，或者一个结构体的实现即可。如下两种。

// 方法一，类型特化，和 C++ 设计结合
namespace std {
template <> struct hash<Point3D> {
    static inline size_t operator()(const Point3D &p) noexcept {
        // 随便给的一个实现，可能容易冲突
        return p.x ^ (p.y << 1) ^ (p.z << 3);
    }
};
// 自定义类型还需要实现判断等于，用于探测匹配
template <> struct equal_to<Point3D> {
    static inline size_t operator()(const Point3D &l, const Point3D &r) noexcept {
        return l.x == r.x and l.y == r.y and l.z == r.z;
    }
};

} // namespace std

// 用法
unordered_map<Point3D, int> mp;
HashMap<Point3D, int> hash_map;

// 方法二，自定义哈希类
struct Point3dHashwer {
    static inline size_t operator()(const Point3D &p) noexcept {
        // 随便给的一个实现，可能容易冲突
        return p.x ^ (p.y << 1) ^ (p.z << 3);
    }
};
// 自定义类型还需要实现判断等于，用于探测匹配
struct Point3dEqual {
    static inline size_t operator()(const Point3D &l, const Point3D &r) noexcept {
        return l.x == r.x and l.y == r.y and l.z == r.z;
    }
};
// 用法
unordered_map<Point3D, int, Point3dHashwer, Point3dEqual> hashmap;
// 我别名的 HashMap 不支持这样写，这样不能方便的复用已有类型的哈希