从map到hash

map 哈希

---

前言

这两种技巧常用于记录和去重量少而分散的状态。
都体现了映射思想。

$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$函数）

#include<tr1/unordered_map>
struct nnode
{
  int x,y;
  bool operator == (const nnode &o) const {return x==o.x&&y==o.y;}
}p[N*10];
struct Hash
{
  std::size_t operator () (const nnode &o) const{return o.x*N*10+o.y;};
};
std::tr1::unordered_map<nnode,int,Hash>mp;

$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$保险。。。
方程自定。