哈希

Tags：字符串

一、概述

百度百科：
散列表（Hash table/哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

哈希表常用于比较两个字符串是否相同（可以把状态看作字符串，从而比较状态是否相同）

二、实现方式

一个例子

通常将其看成一个进制数，比如\(ABAF\)看成\(1216\)，那么哈希值就是\(Hash=1*base^3+2*base^2+1*base+6\)，\(base\)可以自由决定，如果说状态量有限，可以使用较小的\(base\)使得所有状态不冲突，若状态量较大且分散，可以采用取模或者自然溢出的方式尽可能避免冲突

优缺点

优点是可以\(O(1)\)比较（数组是\(O(1)\)如果用map就要加一个\(log\)）

缺点是会有冲突，为避免冲突可以选择双哈希或三哈希等（选取不同的模数）

哈希方式

1.进制哈希（用于判断状态/数组是否相同）

\[Hash[i]=Hash[i-1]*base+val[i]\]优点：方便好写

　　　状态量小时哈希过程可逆（见）

缺点：毒瘤出题人卡自然溢出，采用双哈希

　　　状态量大时哈希过程不可逆（不能通过Hash值还原数组）

使用范围：基本上这么写

2.树哈希（用于判断树的同构）

\[Hash[x]=\sum_{异或和}(Hash[son_{1...k}]+base1)*(siz[x]+base2)+deep[x]*base3\]其实没有一定要求这么写，只是树的同构要求深度相同，孩子也同构但是与孩子的顺序无关，所以信息就是儿子的\(Hash\)和深度和大小，可以灵活处理

千古神犇陈菊开安利的一种写法：\[Hash[x]=(\sum{Hash[son]})^{size[x]}\]

注意：base的选取原则是使得Hash值尽可能分散，尽可能少的冲突

优点：这里不用累乘而用异或和，使得Hash过程可逆（也就是在树DP中方便换根/删点）

缺点：没有固定套路，灵活多变（有次考试不管怎么调\(base\)总是过不了，把异或和改成累乘马上就过了，原因是数据范围小，Hash值密集容易造成冲突）

三、题单

[ ] [AIZU2784]Similarity of Subtrees

[x] [BZOJ3197/Luogu3296][SDOI2013]Assassin/刺客信条

[x] [BZOJ4754/Luogu4323][JSOI2016]独特的树叶

[x] [BZOJ5248][九省联考2018]一双木棋

[x] [BZOJ3555]企鹅QQ

[ ] [BZOJ3507/Luogu3167][CQOI2014]通配符匹配

[ ] [BZOJ4892/Luogu3763][TJOI2017]DNA

[ ] [SDOI2007]游戏

[ ] [HDU5469]Antonidas

四、代码

// [九省联考2018]一双木棋chess#include
    
     #include
     
      #include
      
       #include
       #define ll long longusing namespace std;int N,M,A[11][11],B[11][11],b[11];map
        
         Map;ll HASH(){    ll Hash=0;    for(int i=1;i<=N;i++) Hash=Hash*11+b[i];    return Hash;}void ReHash(ll Hash){    for(int i=N;i>=1;i--) b[i]=Hash%11,Hash/=11;}int DFS(int op,ll Hash){    if(Map[Hash]) return Map[Hash]==-1?0:Map[Hash];    ReHash(Hash);int ans=1e9*(-op);    for(int i=1;i<=N;i++)        if(b[i]

转载于:https://www.cnblogs.com/xzyxzy/p/9145545.html

你可能感兴趣的文章

VScode常用几个前端插件live HTML previewer和debugger for chrome的配置