hash在ACM中的一些运用

我装作看窗外的样子，

看窗户上映着的你。

前言

哈希表是一种高效的数据结构。
散列方法是使用函数 h 将 U 映射到表 $T[0..m-1]$ 的下标上$（m=O(|U|)）$。这样以 $U$ 中关键字为自变量，以 $h$ 为函数的运算结果就是相应结点的存储地址。从而达到在 $O(1)$ 时间内就可完成查找。

Hash 表

Hash 表又称为散列表，一般由 Hash 函数（散列函数）与链表结构共同实现。与离散化思想类似，当我们要对若干复杂信息进行统计时，可以用 Hash 函数把这些复杂信息映射到一个容易维护的值域内，因为值域变简单没有可能两个不同的原始信息被 Hash 函数映射为相同的值。所以我们需要处理这种冲突情况。

整数 Hash 函数的构造方法一般有直接取余法，乘积取整法，平方取中法，等等，此处不详说。

字符串 Hash

树 Hash

矩阵 Hash

即二维 Hash

杂言

适合 hash 的素数

1572869, 3145739, 6291469, 12582917, 25165843, 50331653
good hash table primes
https://planetmath.org/goodhashtableprimes

pb_ds 中的哈希表

wiki

CFblog C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

gp_hash_table<int, int> mp;
cc_hash_table<int, int> mp;