https://zybuluo.com/ysner/note/1175387
前言
这两种技巧常用于记录和去重量少而分散的状态。
都体现了映射思想。
(map)
我一般是数组开不下时拿这玩意判重。
据说特别慢？？？
定义：
(注意一下比较规则必须顾及到所有变量，否则会重复）
struct node
{
int x,y;
bool operator < (node const &o) const {return (x<o.x)||(x==o.x&&y<o.y);}
}
map<node,int>Map;
判定是否重复：
if(map[(node){x,y}]) ;
于是因太弱而被(xzy)教育了一番
排序
(map)还有一种排序功能（类比(Tire)树）。如果用(map)存字符串，那么用以下方式就能按字典序遍历所有字符串。
map<node,int>::iterator iter;
for(iter=Map.begin();iter!=Map.end();iter++)
{
string A=iter->first;
int B=iter->second;
...
}
据说还有一种叫(unorder\_map)的玩意儿，存储时不排序，省时间，但我并不想管。。。
(hash)
(map)虽然能有效区分、避免重复，但其自带的(O(logn))复杂度饱受(oier)诟病。
我们可以弃置一定正确性，来换取时间复杂度降为(O(1))，这就是(hash)本质。
如何保证更高的正确性？这个问题没有答案，因而很多(hash)方程都有其合理性。
一般在开始时，我们要选取一个(Base)，原则是使(Hash)值分散，减少冲突。
字符串(hash)
通常将字符串看成一个进制数，比如(ABAF)看成(1216)，
那么哈希值就是
[Hash[x]=1*Base^3+2*Base^2+1*Base+6
]
(Base)值自定，如果态量有限，可以使用较小的(base)使得所有状态不冲突，若状态量较大且分散，可以采用多次取模（多(hash))的方式尽可能避免冲突。
状态量少时状态可逆。
树(hash)
这玩意专为树的同构而生。
怎样的两颗树能称为同构树？
即树的深度相同、孩子、子树大小相同，只有孩子顺序不同。
[Hash[x]=sum_{异或和}(Hash[son_{1..k}]+Base1)*(sz[x]+Base2)+deep[x]*Base3
]
如果用异或和而不是({sum})，就能使(Hash)过程可逆。但(Hash)值密集时容易冲突，改成累乘就好了。
当然，还有另一种方法，就是如果时间复杂度允许(O(n^2)),则可以以每个点为根，累计统计每颗子树大小乘不同素数的和。这些在根上的和排序后如果完全相同，也可证同构。
数(hash)
用来处理状态量大而分散的情况，没有(map)保险。。。
方程自定。