1、哈希表：效率高，但内存消耗大

2、位图法：数据不多且最大值很大的时候浪费。例如十个整数最大值为10亿，就得开辟十亿的空间来存储。

3、布隆过滤器：只能确认元素不在（用于过滤钓鱼网站，redis缓存中的应用）

哈希表：

vector<int> vec;
srand((unsigned int)time(NULL));
for (int i = 0; i < 10000; i++) {
	vec.push_back(rand()%10000);
}


//找第一个出现重复的数字
//找所有重复出现的数字
unordered_set<int> s1;
for (auto key : vec) {
	auto it = s1.find(key);//O(1)
	if (it == s1.end()) {
		//没找都，该数字第一次出现
		s1.insert(key);
	}
	else {
		cout << "key:" << key << endl;
		break;//找所有数字时不加break
	}
}

//统计数字以及出现的次数
//统计未重复的数字
unordered_map<int,int> m1;
//pair :first存数字，second存出现的次数
for (int key : vec) {
	auto it = m1.find(key);
	if (it == m1.end()) {
		//不存在	
		m1.emplace(key, 1);//second出现次数记录为1  
	}
	else {
		//存在，second记录次数加一
		it->second += 1;
	}
}
for (auto pair : m1) {
	if (pair.second > 1) {//找未重复时将条件改为=1
		cout << "key:" << pair.first <<" " << "count:" << pair.second << endl;
	}
}

unordered_set和unordered_map的共同、不同点：

相同：同为无序集合容器，存储元素不允许重复，不保持任何顺序，底层实现是哈希表。

区别：unordered_set存储唯一元素（适用于频繁插入和删除），unordered_map存储键值对，键唯一（适用于以键-值形式的存储）。

使用时要包含头文件<unordered_set>/<unordered_map>

位图法：用一个位（0或1）来存储数据状态，适用于状态简单，内存大，要求使用率低的场景。

使用位图法首先要直到待处理数据中的最大值，按照size=（maxNumber/32+1）的大小来开辟char类型的数组。当在位图中找某元素时，首先计算该数字对应数组中的比特位，在读取值。

步骤：1、计算待处理数据最大值，根据最大值来求bitmap的位图数组。

           2、根据"\"、"%"映射到对应的比特位。

           3、读取该值的状态。

int main() {
	vector<int> vec{ 12,78,90,123,9,8,9 };
	//定义位图数组
	//找序列最大元素
	int max = vec[0];
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] > max) {
			max = vec[i];		
		}
	}
	int* bitmap = new int[max / 32 + 1]();
	unique_ptr<int[]>ptr(bitmap);//自动释放堆区内存

	//问题1：找第一个重复的元素
	for (auto key : vec) {
		int index = key / 32;//找在第几号元素上
		int offset = key % 32;//找在第几号位上
		//判断状态是否为1
		if (0 == (bitmap[index] &(1<<offset))) {
			//不存在，用位操作改写状态
			bitmap[index] |= (1 << offset);
		}
		else {
			//存在
			cout << key << "是第一个重复的元素" << endl;
			return 0;
		}
	}
}

布隆过滤器：结合哈希表和位图数组的升级方法。

注意事项：

        1、bloom filter是通过一个位数组+k个哈希函数组成的。

        2、bloom filter时间、空间利用率都很高，但有一定错误率。

        3、bloom filter查找错误率与位数组大小，哈希函数个数直接相关

        4、bloom filter默认只支持add（增加），query（查找）操作。因为存储状态也可能是其他数据的状态位，删除易导致其他元素查找判断出错。

        5、bloom filter只能确保数据不在，不能确保在。

int main() {
	vector<int> vec{ 12,78,90,123,9,8,9 };
	//定义位图数组
	//找序列最大元素
	int max = vec[0];
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] > max) {
			max = vec[i];
		}
	}
	int bitmap_size = max / 32 + 1;
	int* bitmap = new int[bitmap_size]();
	unique_ptr<int[]>ptr(bitmap);//智能指针自动释放堆区内存

	//布隆过滤器：检测重复元素
	for (auto key : vec) {
		//使用哈希函数组合，减少冲突
		int pos1 = (key * 7) % bitmap_size;    //哈希函数1：乘法+取模
		int pos2 = (key * 11) % bitmap_size;   //哈希函数2：乘法+取模
		int pos3 = (key * 13) % bitmap_size;   //哈希函数3：乘法+取模

		//使用位操作检查特定位
		int index1 = pos1 / 32;
		int offset1 = pos1 % 32;
		int index2 = pos2 / 32;
		int offset2 = pos2 % 32;
		int index3 = pos3 / 32;
		int offset3 = pos3 % 32;

		//布隆过滤器判断逻辑
		if ((bitmap[index1] & (1 << offset1)) &&
			(bitmap[index2] & (1 << offset2)) &&
			(bitmap[index3] & (1 << offset3))) {
			//三个哈希位置都为1，元素可能存在（有误判可能）
			cout << key << "可能重复" << endl;
		}
		else {
			//至少有一个位置为0，元素肯定不存在，标记三个位置
			bitmap[index1] |= (1 << offset1);  //使用位或操作设置特定位
			bitmap[index2] |= (1 << offset2);
			bitmap[index3] |= (1 << offset3);
		}
	}
	return 0;
}