大數據查重
哈希表
找出第一個出現重復的數字 || 找所有重復出現的數字
#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;
}
