哈希表

哈希，就是给一个元素（可以是数字，字符串，甚至是树）一个在小区间内的编号，以便用数组来存储。
这个从元素到编号的函数就称为哈希函数。
那么，从元素集合到编号集合构成一个映射，并且可能有许多元素对应同一个编号，如果还是要存，这时候称为哈希冲突，下文会提到它的解决办法。
哈希表在STL里面已经给出了实现方法：map与unordered_map，map单次操作是$O(\log n)$的，noip比赛里面可以使用，而unordered_map单次操作是$O(1)$的，但noip比赛里面不可以使用。

图书管理

图书管理

#include <bits/stdc++.h>

using namespace std;
const int N=2e2+5,MOD=1e5,M=1e5+5,P=131;
//P为将字符串哈希成几进制数，下文中会提到
int n;
int head[M],nxt[M],cnt;
string val[M];

//哈希函数
int calc(string str) {
    int res=0;
    for(int i=0;i<str.length();i++)
      res=(res*P%MOD+str[i]-'0'+MOD)%MOD;
    return res;
}

//添加一个值，链式前向星写法
void add(string str) {
    int hsh=calc(str);
    val[++cnt]=str;
    nxt[cnt]=head[hsh];
    head[hsh]=cnt;
}

//判断有无跟它相同的
bool search(string str) {
    int hsh=calc(str);
    bool flg=false;
    for(int i=head[hsh];i;i=nxt[i]) //遍历这一个链表
      flg|=(str==val[i]);   //简便的写法
    return flg;
}

int main() {
    cin>>n;
    while(n--) {
        string opt,str;
        cin>>opt;
        getline(cin,str);   //读入一行数据
        if(opt[0]=='f')
          puts(search(str)?"yes":"no");
        else
          if(!search(str))  //如果已经有值了，就不加入
            add(str);
    }
    return 0;
}

字符串哈希

子串查找

子串查找
两个字符串哈希值相同，我们就认为它们相同，也就是说这种哈希的冲突概率特别地小，并且运算是在ull下进行，那冲突概率就几乎为0了。

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ll;  //直接自然溢出啥事没有
const int N=1e6+5,P=131;

int cnt;
ll mhsh,hsh[N],power[N];
char a[N],b[N];

ll get(int l,int r) {
    return hsh[r]-hsh[l-1]*power[r-l+1];
}

int main() {
    scanf("%s%s",a+1,b+1);
    int lena=strlen(a+1),lenb=strlen(b+1);
    power[0]=1; //不要忘了
    for(int i=1;i<=lena;i++) {
        hsh[i]=hsh[i-1]*P+a[i]-'0'; //处理hsh数组
        power[i]=power[i-1]*P;  //预处理出P的次幂
    }
    for(int i=1;i<=lenb;i++)
      mhsh=mhsh*P+b[i]-'0';
    for(int i=1;i<=lena-lenb+1;i++) {   //遍历每个区间
        int l=i,r=i+lenb-1;
        if(mhsh==get(l,r))
          cnt++;
    }
    cout<<cnt;
    return 0;
}

可以发现这里的哈希只是转为数字，是为了判定的准确，上面转为一个小区间里的数是为了用链表存，这个不要搞混了。