一.哈希表在大数据查重中的应用哈希表在大数据查重中可以查找重复或统计重复出现的数字但是其空间的占用率较高。例如我们定义一个数组存储了10000个随机数然后利用CSLT中提供的哈希表解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.统计重复的数字及其出现次数利用CSTL的unordered_map。unordered_mapint,intun_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.去除重复出现的数字CSTL的unordered_set本就不允许数字重复。unordered_mapint, intun_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 }我们想要查找所有重复出现第一个重复出现的数字vectorintvec{ 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_ptrint[] ptr(bitmap); for (auto key : vec) { int index key / 32; int offset key % 32; if ((bitmap[index](1offset))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_queueint 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_queueint,vectorint,greaterint 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_mapint, intun_map; for (auto key : vec) { un_map[key]; } int k 3; using Type pairint, int; using Comp functionbool(Type, Type); priority_queueType, vectorType, Compminheap([](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 (ij 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 (ij 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); } }