[Codevs 1230]元素查找(手寫哈希表)

[Codevs 1230]元素查找(手寫哈希表)

說白了就是要我們自己手寫一個哈希表的數據結構來實現添加和查找功能，map也能直接過（我第一次寫就是用map騙AC的）

提一下個人理解的哈希表的實現（下面說的是線性尋址法），如果有誤還請各位大神不吝指教

用一個數組模擬哈希表，函數f(x)=數字x在哈希表中出現的下標的最小可能值，一般f(x)=x mod t，t就是哈希表的長度

下面就是一個哈希表的示例，如果遍歷哈希表時指針走出了哈希表的終點，就進入起點重新遍歷

對於每次向哈希表中添加一個數x，從下標f(x)開始查找，以上文所說的遍歷方式查找，直到找到裝有x這個數的哈希表元素，返回查找成功（哈希表中有x這個數）。如果遍歷過程中遇到了空的哈希表的一個元素就返回查找失敗（哈希表中沒有x這個數）。

插入元素的過程類似於查找，向哈希表中插入數字x時，首先從下標f(x)開始查找，直到找到第一個為0的哈希表元素，將數字x插入進去。

下面是此題代碼：

#include 
#include 
#include 
#include 
#include 

#define MAXN 1000008
#define MOD 1000007

using namespace std;

int hashTable[MAXN];

void update(int x) //將數字x加入哈希表
{
    int num=x;
    x%=MOD;
    while(1)
    {
        if(!hashTable[x])
        {
            hashTable[x]=num;
            return;
        }
        if(hashTable[x]!=num)
        {
            x++;
            if(x==MAXN) x=0;
        }
        else return;
    }
}

bool query(int x) //查找哈希表中是否有數字x
{
    bool found=false;
    int num=x;
    x%=MOD;
    while(1)
    {
        if(!hashTable[x]) return false;
        if(hashTable[x]!=num)
        {
            x++;
            if(x==MAXN) x=0;
        }
        else return true;
    }
}

int main()
{
    int n,m,x;
    scanf(%d%d,&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf(%d,&x);
        update(x+1);
    }
    for(int i=1;i<=m;i++)
    {
        scanf(%d,&x);
        if(query(x+1)) printf(YES
);
        else printf(NO
);
    }
    return 0;
}