Hash

一种快速判定的方法，具体是将一个复杂的结构映射成一个整数，用极低的错误概率换取极快的比较效率。

进制Hash

对于序列的Hash，关心元素之间的位置关系。
不要把任意字符对应到数字0，比如假如把a对应到数字0，那么将不能只从Hash结果上区分ab和b.

注意有时候卡自然溢出和 int 范围内的模数，可以使用 \(10^{18}+3\) 。

异或Hash

针对于集合的Hash，可以实现出现一个数时加入，再次出现时删除。

随机赋权

加和Hash

针对于可重集的Hash，\(+w_x\) 即向集合加入一个 \(x\) ，\(-w_x\) 即从集合中删除一个 \(x\)。

记一种随机权值Hash的快速查表方法

对于 for(int i=1;i<=n;i++)w[i]=rnd();如果我们要查询一个 \(W\) 在不在 \(\{w\}\) 里，或者进一步的想知道对应的下标是什么，有以下方法。

朴素想法：unordered_map，就是之间建立反过来的映射，这样常数太大。

手写Hash表：即取 \(w\) 后若干位，将相同的放入一个vector每次遍历查找，由于 \(w\) 是随机的，期望大小为 \(\mathcal O(1)\)。

进阶想法：直接将 \(w_i\) 的二进制下的后__lg(n)位变成 \(i\)，这样遇到一个数 \(W\)，取出后__lg(n)位，设作 \(x\)，如果 \(x\in [1,n]\land w_x=W\)，则 \(W\) 存在。