散列之散列的定义及整数散列

/*
描述：散列(hash)

1 问题描述：给定N个正整数与M个正整数，判断M中每个数值是否在N集合中存在。
其中N与M的规模均达到十万级别，且所有数值均小于十万。
例如：当N=5，M=3时，若N集合为{8, 3, 7, 6, 2}，而M集合为{7, 4, 2}，则在N中仅能找到7和2两个元素，4则未出现。

2 解决方法：
最直接的处理方式是针对每一个待查询的数值x，在N集合中逐个比对是否存在相等的元素。然而此方法的时间复杂度为O(M*N)，对于如此大规模的数据显然无法承受。
采用空间换取时间的方式：创建一个布尔型数组hashtable[10010]，其中hashtable[x]被标记为true时表示数值x存在于数据集中。通过这种方式，在读取N个数值时即可完成预处理操作。具体而言，在读取到某个数值x时，将hashtable[x]设为true（需注意初始状态下该数组应全部初始化为false）。这样在后续处理M个待查询数值时，只需通过访问hashtable数组即可快速判断每个数值是否存在。该方案的时间复杂度显著降低至O(N+M)。
*/
代码如下：
#include
using namespace std;

const int maxn = 10010;
bool hashtable[maxn] = { false };
i