【hash表】图书管理

【哈希和哈希表】图书管理

题目描述

图书管理是一件十分繁杂的工作，在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书（以便于帮助想要借书的客人快速查找他们是否有他们所需要的书），我们需要设计一个图书查找系统。
该系统需要支持 2 种操作：

• add(s) 表示新加入一本书名为 s 的图书。
• find(s) 表示查询是否存在一本书名为 s 的图书。

输入

第一行包括一个正整数 n（n≤30000），表示操作数。 以下n行，每行给出 2 种操作中的某一个指令条，指令格式为：
add s
find s
在书名s与指令（add，find）之间有一个隔开，我们保证所有书名的长度都不超过200。可以假设读入数据是准确无误的。

输出

对于每个 find(s) 指令，我们必须对应的输出一行 yes 或 no，表示当前所查询的书是否存在于图书馆内。
注意：一开始时图书馆内是没有一本图书的。并且，对于相同字母不同大小写的书名，我们认为它们是不同的。

---

【题解】：

　　利用链式前向星来模拟hash表的链，同时使用了双hash结构，代码是抄袭书本的。。。。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int Mod1 = 1e6+3;
const int Mod2 = 1e6+9;
const int p1 = 47 ;
const int p2 = 79 ;
int cnt = 0 , Next[N+5],Head[Mod2+10],W[N];
void Insert(int x,int y ){
    Next[++cnt] = Head[x] ;
    Head[x] = cnt ;
    W[cnt] = y ;
}
bool Query(int x,int y){
    for(int i=Head[x];i;i=Next[i]){
        if( W[i] == y ) return true;
    }
    return false ;
}
int main()
{
    ios_base :: sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    int n;
    char op[10],s[5006];
    cin >> n ;
    while (n--) {
        cin >> op ;
        cin.getline(s,sizeof(s));
        int len = strlen(s);
        long long  sum1 = 0 ,sum2 = 0;
        for(int i=0;i<len;i++){
            sum1 = ( sum1 * p1 + s[i] ) % Mod1;
            sum2 = ( sum2 * p2 + s[i] ) % Mod2;
        }
        if ( op[0] == 'a' ){
            Insert(sum1,sum2);
        }else{
            if( Query(sum1,sum2) ){
                printf("yes
");
            }else{
                printf("no
");
            }
        }
    }
    return 0;
}