哈希表

哈希表有两种用法，第一种是字符串哈希，用于匹配字符，第二种是用来查找或去重的.

例题1：一个数列中有n个数，查找x在数列中是否存在。（$1\leq n,\max \left( a\left[ i\right] \right) \leq 10^9$，）

做法一：桶排，时间复杂度为$O(1)$，但空间必须开到$\max \left( a\left[ i\right] \right)$，空间会爆。

做法二：顺序查找，枚举n个数，是否存在，时间复杂度$O(n)$，若采用二分查找，数列无序，排序时间为$O(nlogn)$，虽然二分查找复杂度为$O(logn)$，但总复杂度为$O(nlogn+logn)$，时间超限。

做法三：哈希查找，时间复杂度可自由控制。

哈希表原理

          ||  映射成
          \/  k%13

但这会出现另一种情况，就是出现多个数都是同一个余数的情况。这时候我们可以拉一个链表，存同一个余数的多个数。

定义一个数组vector v[MOD]。

1.插入：

void insert(int s){
	v[s%MOD].push_back(s);
}

2.查找：

bool find(int s){
	for(int i=0;i<v[s%MOD].size();i++){
		if(v[s%MOD][i]==s)return true;
	}
	return false;
}

注意，MOD最好是一个质数，而且大小要根据输入数组的大小调整好，这样才能实现时间和空间复杂度的平衡。