一.哈希表在大数据查重中的应用
哈希表在大数据查重中可以查找重复或统计重复出现的数字，但是其空间的占用率较高。
例如，我们定义一个数组，存储了10000个随机数，然后利用C++SLT中提供的哈希表解（unordered_map与unordered_set）决如下问题：
1.查找第一个重复的数字
遍历查找，将没有找到的数字存放在哈希表中，找到的数字直接输出。
for (auto key : vec) { if (!un_set.count(key)) { un_set.emplace(key); } else { cout << key << endl; break; } }2.查找全部重复的数字
为了保证所有重复的数字只输出一次，我们再定义一个哈希表2，遍历查找，将没有找到的数字存放在哈希表1中，找到的数字再判断其是否在哈希表2中，在则说明这个重复的数字已经输出过了，不在则将其存入哈希表2中并输出结果。
for (auto key : vec) { if (!un_set.count(key)) { un_set.emplace(key); } else if(un_set.count(key)&&!un_set1.count(key)) { un_set1.emplace(key); cout << key << endl; } }3.统计重复的数字及其出现次数
利用C++STL的unordered_map。
unordered_map<int,int>un_map; for (auto key : vec) { if (!un_map.count(key)) { un_map.emplace( key,1 ); } else { ++un_map[key]; } } for (auto pair : un_map) { if (pair.second > 1) { cout << pair.first << " : " << pair.second << endl; } }4.去除重复出现的数字
C++STL的unordered_set本就不允许数字重复。
unordered_map<int, int>un_set; for (auto key : vec) { un_set.emplace(key); }二.位图算法
位图法,就是用一个位(0或者1)来存储数据的状态（无法统计重复元素的次数）,比较适合状态简单,数据量比较大,要求内存使用率低的问题场景。
位图法解决问题,首先需要知道待处理数据中的最大值,然后按照size=(maxNumber/32)+1的大小来开辟一个char类型的数组,当需要在位图中查找某个元素是否存在的时候,首先需要计算该数字对应的数组中的比特位,然后读取值,0表示不存在,1表示已存在。
位图法有一个很大的缺点,就是数据没有多少,但是最大值却很大,比如有10个整数,最大值是10亿,那么就得按10亿这个数字计算开辟位图数组的大小,太浪费内存空间。
例如，我们定义一个数组存储{ 12, 12,78,90,123,8,8,9,9 }，我们想要查找所有重复出现（第一个重复出现）的数字
vector<int>vec{ 12, 12,78,90,123,8,8,9,9 }; int max = vec[0]; for (size_t i = 1; i < vec.size(); i++) { if (vec.at(i) > max) { max = vec.at(i); } } 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 ((bitmap[index]&(1<<offset))==0) { bitmap[index] = bitmap[index] | (1 << offset); } else { cout << key << endl; //break; } }三.布隆过滤器
1.Bloom Filter是通过一个位数组+k个哈希函数构成的（综合了前两个方法）。
2.Bloom Filter的空间和时间利用率都很高,但是它有一定的错误率,虽然错误率很低,Bloom Filter判断某个元素不在一个集合中,那该元素肯定不在集合里面;Bloom Filter判断某个元素在一个集合中,那该元素有可能在,有可能不在集合当中。
3.Bloom Filter的查找错误率,当然和位数组的大小,以及哈希函数的个数有关系,具体的错误率计算有相应的公式
4.Bloom Filter默认只支持add增加和query查询操作,不支持delete删除操作(因为存储的状态位有可能也是其它数据的状态位,删除后导致其它元素查找判断出错)。
增加一个元素
1、经过k个哈希函数计算,得到bitmap位数组里面的一组位的序号
2、把相应的位置成1
搜索一个元素
1、经过k个哈希函数计算,得到bitmap位数组里面的一组位的序号
2、判断上面几个位置的值如果全是1,证明相应的key存在,如果有一个是0,则证明key不在bloom filter中
过小的布隆过滤器很快所有的bit位均为1,那么查询任何值都会返回“可能存在”,起不到过滤的目的。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器bit位置为1的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那误报率就会变高。
四.Topk问题
Topk问题，就是找出一组数据中前（第）k大或前（第）k小的问题。
1.大小根堆解法
利用大根堆过滤前top k小的数据;小根堆过滤前top k大的数据
（1）查找vector中值最小的前五个元素
priority_queue<int> maxheap; int k = 5; for (size_t i = 0; i < k; i++) { maxheap.push(vec[i]); } for (size_t i = 5; i < 1000; i++) { if (vec[i] < maxheap.top()) { maxheap.pop(); maxheap.push(vec[i]); } } for (size_t i = 0; i < 5; i++) { cout << maxheap.top() << " "; maxheap.pop(); }（2）查找最大的五个元素
priority_queue<int,vector<int>,greater<int>> minheap; int k = 5; for (size_t i = 0; i < k; i++) { minheap.push(vec[i]); } for (size_t i = k; i < vec.size(); i++) { if (minheap.top() < vec[i]) { minheap.pop(); minheap.push(vec[i]); } } while (!minheap.empty()) { cout << minheap.top() << " "; minheap.pop(); }（3）查找重复次数最多的三个元素
unordered_map<int, int>un_map; for (auto key : vec) { un_map[key]++; } int k = 3; using Type = pair<int, int>; using Comp = function<bool(Type&, Type)>; priority_queue<Type, vector<Type>, Comp>minheap([](Type& a, Type b)->bool {return a.second > b.second; }); auto it = un_map.begin(); for (int i = 0; i < k; i++, ++it) { minheap.push(*it); } for (int i = k; i < un_map.size(); i++, ++it) { if (minheap.top().second < it->second) { minheap.pop(); minheap.push(*it); } } while (!minheap.empty()) { cout << minheap.top().first << " ：" << minheap.top().second << " " << endl;; minheap.pop(); }2.快排分割解法
（1）找值最小的三个元素
int Partaion(int arr[], int begin, int end) { int i = begin; int j = end; int val = arr[i]; while (i < j) { while (i<j && arr[j]>val) j--; if (i < j) { arr[i] = arr[j]; i++; } while (i < j && arr[i] < val) i++; if (i < j ) { arr[j] = arr[i]; j--; } } arr[i] = val; return i; } void SelectTopk(int arr[], int begin, int end, int k) { int pos = Partaion(arr, begin, end); if (pos == k - 1) { return; } else if (pos > k - 1) { SelectTopk(arr, begin, pos - 1,k); } else { SelectTopk(arr, pos + 1, end,k); } }（2）找值最大的三个元素
int Partaion(int arr[], int begin, int end) { int i = begin; int j = end; int val = arr[i]; while (i < j) { while (i<j && arr[j]<val) j--; if (i < j) { arr[i] = arr[j]; i++; } while (i < j && arr[i] > val) i++; if (i < j) { arr[j] = arr[i]; j--; } } arr[i] = val; return i; } void SelectTopk(int arr[], int begin, int end, int k) { int pos = Partaion(arr, begin, end); if (pos == k - 1) { return; } else if (pos > k - 1) { SelectTopk(arr, begin, pos - 1, k); } else { SelectTopk(arr, pos + 1, end, k); } }
