大数据查重
哈希表
找出第一个出现重复的数字 || 找所有重复出现的数字
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stdlib.h>
#include <time.h>
#include <string>
using namespace std;#if 0
int main()
{vector<int> vec;srand(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);if(it == s1.end()){s1.insert(key);}else{cout << "key:" << key << endl;break;}}统计重复数字以及出现的次数unordered_map<int, int> m1;for(auto key : vec){auto it = m1.find(key);if( it == m1.end()){m1.emplace(key, 1);}else{it->second += 1;}}for(auto pair : m1){if(pair.second > 1){cout << "key:" << pair.first << "cnt:" << pair.second << endl;}}// 一组数据有些数据是重复的，把重复的数据过滤掉unordered_set<int> s2;for(auto key : s2){s2.emplace(key);}return 0;
}问题描述：有两个文件a和b，里面放了ip地址（URL，email）找出两个文件重复的ip，小于100M
分治思想，把大文件分成小文件，1-10，然后分别查重
位图算法
位图法：就是用一个位（0或者1）来存储数据的状态，比较适合状态简单，数据量比较大，要求内存使用率低的问题场景。位图法解决问题，首先需要知道待处理数据中的最大值，然后按照size=(maxNumber/32)+1的大小来开辟一个char类型的数组，当需要在位图中查找某个元素是否存在时，首先需要计算该数字对应的数组中的比特位，然后读取值，0表示不存在，1表示已存在。
题目描述：有一亿个整数，最大不超过一亿，问哪些元素重复了，谁是第一个重复的，内存限制100M
char数组就是8位，short就是16位，int就是32位
如何获取该位的值？
bitmap[index] & (1 << offset) 就是1左移offset位，然后和bitmap[index]相与&，00000000 & 10000000 结果就是00000000，即就是没出现过
如何把这个位置置成1？
即就是bitmap[index] | (1 << offset),10000000 | 00000000 = 10000000
int main()
{vector<int> vec = {12, 78, 90, 12, 8, 9};// 定义位图数组int max = vec[0];for (int i = 1; i < vec.size(); i++){if (vec[i] > max){max = vec[i];}}cout << max << endl;int *bitmap = new int[max / 32 + 1]();unique_ptr<int> ptr(bitmap);for (auto key : vec){int index = key / 32;int offset = key % 32;if (0 == (bitmap[index] & (1 << offset))){bitmap[index] |= (1 << offset);}else{cout << key << "key是第一个重复出现的数字。" << endl;return 0;}}return 0;
}布隆过滤器
布隆过滤器是一种更高级的“位图法”解决方法，之所以它更高级，是因为他没有上面位图法所说的缺陷。
1.Bloom Filter是通过一个位数组和k个哈希函数构成的。
2.Bloom Filter的空间和时间利用率都很高，但它有一定的错误率，虽然错误率很低，他判断一个元素不在一个集合中，那么它一定不在，它判断某个元素在一个集合中，那么该元素可能在，也可能不在。
3.Bloom Filter的查找错误率，当然和位数组大小以及哈希函数的个数有关，具体的错误率计算有相应公式。
4.Bloom Filter默认只支持add和query操作，不支持delete操作（因为存储的状态为有可能也是其他数据的状态为，删除后导致其他元素查找判断出错）
场景一：提示过滤一些非法的网站，或者钓鱼网站等。
把所有可能怀疑有问题的网站的URL添加到布隆过滤器中https://www.xxx.com查找当前访问的网址URL是否在黑名单中，
如果网址URL不存在，那肯定在白名单中的合法的网址，可以访问；如果存在（有误判率），会进行提示网站有风险，禁止访问。
场景二：redis缓存中的应用
查key到底在不在，而且效率要求高，最好还省内存。
如果key不再，那么直接去db层mysql里面去查询，如果显示在，那么就在redis里面查，如果出现误判，则继续去mysql中查询。
setBit(key)
getBit(key) => key不存在 => DB => 缓存redis => return
getBit(key) => key存在 => redis中找key
/** @Author: jyx* @Date: 2025-03-09 13:35:39* @LastEditors: jyx* @Description:*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;class BloomFilter
{
private:/* data */int bitSize_;vector<int> bitMap_;
public:BloomFilter(int bitsize = 1471): bitSize_(bitsize){bitMap_.resize(bitSize_ / 32 + 1);}~BloomFilter(){}void setBit(const char* str){// 计算k组哈希函数的值int idx1 = BKDHash(str) % bitSize_;int idx2 = RHash(str) % bitSize_;int idx3 = JSHash(str) % bitSize_;// 把相应的idx1，idx2，idx3这几个位全部置1int index = 0;int offset = 0;index = idx1 / 32;offset = idx1 % 32;bitMap_[index] |= ( 1 << offset);index = idx2 / 32;offset = idx2 % 32;bitMap_[index] |= (1 << offset);index = idx3 / 32;offset = idx3 % 32;bitMap_[index] |= (1 << offset);}bool getBit(const char* str){int idx1 = BKDHash(str) % bitSize_;int idx2 = RHash(str) % bitSize_;int idx3 = JSHash(str) % bitSize_;int index = 0;int offset = 0;index = idx1 / 32;offset = idx1 % 32;if(0 == (bitMap_[index] = (1 << offset))){return false;}index = idx2 / 32;offset = idx2 % 32;if (0 == (bitMap_[index] = (1 << offset))){return false;}index = idx3 / 32;offset = idx3 % 32;if (0 == (bitMap_[index] = (1 << offset))){return false;}return true;}};class BlackList
{
private:/* data */BloomFilter blackList_;
public:BlackList(/* args */){}~BlackList(){}void add(string url){blackList_.setBit(url.c_str());}bool query(string url){return blackList_.getBit(url.c_str());}
};int main()
{BlackList list;list.add("https://www.baidu.com");list.add("https://www.taobao.com");list.add("https://www.jingdong.com");list.add("https://www.leetcode.com");string url = "https://www.jingdong.com";list.query(url);return 0;
}
