哈希表链地址法查找元素是否在集合中出现

Question

给定一个集合，查找元素是否在集合中出现。
每个测试用例由多行组成，第一行是两个整数n和m，两个数范围在1到100000之间。自第二行起一共有n+m个整数，其中前面n个整数代表集合的元素，随后的m个整数是待查询的数。所有的整数在范围[-2^31,2^31)内。
对于每个待查询的数，如果在集合中则输出yes,否则输出no.
样例输入
5 3
7 9 3 2 -5
4 9 -5
5 3
-2 1 0 -2 1
0 -2 3
样例输出
no
yes
yes
yes
yes
no
错误：时间超限
不知道还能怎么提高查找效率，我觉得这个哈希函数挺高效的啊。散列表长度刚好合适时间复杂度会不会更小啊？求解答……

#include <iostream>
#include <iomanip>
#include <cstdio>
using namespace std;

typedef struct node
{
    int key;
    struct node *next;
} Node, *PNode;

typedef struct
{
    PNode *elem;
    int sz;
} HashTable;

void InitHashTable(HashTable &ht, int n)
{
    if(n<100)
        n=7;
    else if(n>=100&&n<10000)
        n=97;
    else if(n>=10000&&n<1000010)
        n=9931;
    ht.sz = n;
    ht.elem = new PNode[n]();
}
bool InsertHashTable(HashTable &ht, int k)
{
    int x = k % ht.sz;
    PNode newnode = new Node;
    newnode->key = k;
    newnode->next = ht.elem[x];
    ht.elem[x] = newnode;
    return true;
}
PNode SearchHashTable(HashTable ht, int j)
{
    int y=j%ht.sz;
    PNode p=ht.elem[y];
    while(p)
    {
        if(j==p->key)
            return p;
        p=p->next;
    }
    return NULL;
}
int main()
{
    HashTable ht;
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        InitHashTable(ht, n);
        int j,k;
        for(int i=0; i<n; i++)
        {
            cin>>k;
            InsertHashTable(ht, k);
        }
        for(int i=0; i<m; i++)
        {
            cin>>j;
            cout <<(SearchHashTable(ht, j) ? "yes" : "no") << endl;
        }
    }
    return 0;
}

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7566284
• 除此之外, 这篇博客: 【面试题】【剑指offer】给定一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次，请找出只出现一次的那两个元素。中的 显然，要想从ret中拆出独立的两个元素非常困难，我们可以换个思路，既然ret是那两个元素的异或，那么在ret的二进制一个位置上（如M位）为1，必然两个元素（假设为x1，x2）其中一个的M位为1，另一个为0（异或时，相同为0，相异为一，二进制仅有0和1两种表示方法）。想到这里，那我们可以将原先数组中M为1的分成一组，M位为0的分成一组，相同的元素，必然会分到同一组，再让为1的一组全部异或得到其中一个独立元素，M为0的一组全部异或，得到另一个独立元素。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

•