AcWing 840 模拟散清單

題目描述：

維護一個集合，支援如下幾種操作：

1. “I x”，插入一個數x；
2. “Q x”，詢問數x是否在集合中出現過；

現在要進行N次操作，對于每個詢問操作輸出對應的結果。

輸入格式

第一行包含整數N，表示操作數量。

接下來N行，每行包含一個操作指令，操作指令為”I x”，”Q x”中的一種。

輸出格式

對于每個詢問指令“Q x”，輸出一個詢問結果，如果x在集合中出現過，則輸出“Yes”，否則輸出“No”。

每個結果占一行。

資料範圍

1≤N≤10^5

−10^9≤x≤10^9

輸入樣例：

5
I 1
I 2
I 3
Q 2
Q 5
           

輸出樣例：

Yes
No
           

分析：

哈希表是指通過一個哈希函數将一個key映射為另一個value，這種鍵值對在STL裡有現成的map容器，但是數組模拟的散清單效率更加的高效。

哈希函數有很多種，較為簡單的就是找一個4k + 3的質數mod，對其将x模以mod進而将value映射到0 - mod - 1的範圍内，而且沖突機率并不高。解決沖突的辦法有很多，比如開放尋址法，鍊位址法等，下面僅實作最簡單的開放尋址法，當key映射到某位置上已經存在其它元素時，直接往該位置後面繼續搜尋，直至找到空位為止。

#include <iostream>
using namespace std;
const int mod = 100003,maxn = 200005;
int h[maxn];
int find(int x){
    int t = (x % mod + mod) % mod;
    while(h[t] && h[t] != x)   t++;
    return t;
    
}
int main(){
    int n,x;
    cin>>n;
    char op;
    while(n--){
        cin>>op>>x;
        if(op == 'I')   h[find(x)] = x;
        else    cout<<(h[find(x)] == x ? "Yes" : "No")<<endl;
    }
    return 0;
}