- 一、海量数据的查重问题
- 二、无限制哈希表查重（重复出现的数字、重复出现的次数、第几个重复）
- 三、内存限制哈希表查重（重复出现的数字以及出现的次数）
- 四、哈希表unordered_set查重（重复的数字、第几个重复）
- 五、位图查重（重复的数字、第几个重复）
- 查重：数据是否有重复，以及数据重复的次数
- topK：有几亿个数字。求元素的值，前K大/小，第K大/小
- 去重：去掉重复多次的数字，数字只保留一份
- 哈希表：得看有没有对内存的限制，如果没有限制，就是直接用哈希表解决。比如说 50亿（5G）个整数的查重问题， 10亿个整数内存大约是1G，50亿个整数相当于内存是5G，一个整数4个字节，如果要用一个哈希表把这50亿个数据全部存储下来，就得花20G的内存，链式哈希表每个节点还得有一个地址域，又占4字节，所以总共需要（20G+20G=40G） 的内存空间。哈希表就是空间换时间的这么一个结构
C++STL中的无序容器底层就是通过哈希表实现的，其中主要涉及四个容器：
在实际解决问题的过程中，如果需要使用哈希表，可以直接使用上面的无序容器，哈希表的增删查的时间复杂度趋近于O(1)，效率非常高
-
分治思想：如果对内存有要求，就要使用分治思想，对数据的大小进行划分。第1和第2个方法思想是解决查重问题的根本出发点，就是用哈希表。
-
Bloom Filter：布隆过滤器，节省内存，但是有点误差
-
如果是字符串类型的查重，除了哈希表，布隆过滤器，还可以使用TrieTree字典树(前缀树)
https://blog.csdn.net/QIANGWEIYUAN/article/details/88815772
二、无限制哈希表查重（重复出现的数字、重复出现的次数、第几个重复）int main() {
const int SIZE = 10000;
int ar[SIZE] = { 0 };
for (int i = 0; i < SIZE; ++i) {
ar[i] = rand();
}
unordered_map map;
int n = 1;
for (int val : ar) {
if (map[val] > 0) {
cout << val << "是第" << n <<"个重复的" << endl;
++n;
}
map[val]++;
}
for (auto pair : map) {
if (pair.second > 1) {
cout << pair.first << "重复 " << pair.second << " 次" << endl;
}
}
return 0;
}
三、内存限制哈希表查重（重复出现的数字以及出现的次数）
场景一：有一个文件，有50亿个整数，内存限制400M，找出文件中重复的数字和重复的次数
我们知道50亿大概是5G，每个整数4字节，就需要20G内存存储，如果使用链式哈希表每个节点还需要4字节存储地址域，总共需要40G内存，这么大的内存是我们不能接受的
我们可以使用分治法，大文件划分成小文件，使得每一个小文件能够加载到内存当中，求出对应的重复的元素，把结果写入到一个存储重复元素的文件当中
40G的大文件可以划分成大约120个（文件的数量最好是素数）400M的小文件（系统默认一个进程使用的文件数不超过1024）
data0.txt data1.txt ... data126.txt
当然哈希算法可能是不均匀分配的，导致有的文件存放的整数很多，甚至超过了400M，这时就需要增大小文件的数量，确保使用哈希函数后，每个小文件存储的整数不超过400M
然后遍历大文件的整数，把每一个整数根据哈希映射函数val % 127 = file_index，放到对应序号的小文件当中。整数值相同，通过一样的哈希映射函数，肯定是放在同一个小文件中
这样就从小文件里把数据全部读出来放在内存中，使用哈希表进行查重，可以求出重复出现的数字以及出现的次数，但是不能知道是第几个重复的数字
场景二：有a、b两个大文件，里面都有10亿个整数，内存限制400M，求出在a，b两个文件中都出现的数字
10亿大概是1G，10个整数需要4G，使用哈希表还需要存储地址域，则需要8G内存，显然我们需要使用分治策略
8G / 400M > 20，我们取素数23，将每个大文件中10亿个数据分别用哈希算法val % 23 = file_index存储至23个小文件中
a0.txt b0.txt a1.txt b1.txt ... a22.txt b22.txt
a和b两个文件中，值相同的元素，进行哈希映射以后，肯定在相同序号的小文件当中
接下来一组一组处理，读取a0.txt中所有的整数到哈希表，然后从b0.txt中挨个读取，在哈希表中查找，这样就能找到在a0.txt和b0.txt中都出现的数字了。然后处理a1和b1，然后处理a2和b2…直到处理a22和b22，可以求出重复出现的数字以及出现的次数，但是不能知道是第几个重复的数字
此外，我们还可以用a文件的数据构建Bloom Filter的位数组中的状态值，然后再读取b文件的数据进行布隆过滤的查找操作就可以了
四、哈希表unordered_set查重（重复的数字、第几个重复）问题：有10亿个整数，整数取值范围也是0到10亿，找出第一个重复的数字？
如果只是使用unordered_set只能知道哪个数字重复以及第几个重复，不能确定重复的次数。可以借助unordered_map记录重复的数字以及重复次数
int main()
{
vector vec;
for (int i = 0; i < 1000; ++i)
{
vec.push_back(rand());
}
// 用哈希表解决查重，因为只查重，所以用无序集合解决该问题
unordered_set hashSet;
int n = 1;
for (int val : vec)
{
// 在哈希表中查找val
auto it = hashSet.find(val);
if (it != hashSet.end())
{
cout << *it << "是第"<
// 没找到
hashSet.insert(val);
}
}
return 0;
}
五、位图查重（重复的数字、第几个重复）
题目已经告诉了数据的取值范围，最大值是10亿，如果问题没有告知数据最大值，用位图法处理问题，需要先遍历一遍数组找出最大值，根据最大值开辟位图
最大值是10亿，我们得开辟10亿个bit，即125000000字节，大约是120MB，这就很节省空间了
位图法有一个很大的缺点：就是数据没有多少，但是最大值却很大，比如有10个整数，最大值是10亿，那么就得按10亿这个数字计算开辟位图数组的大小，也就是在10个数字中找重复的，就需要120MB的空间，这种极端情况很浪费空间
#include#include #include using namespace std; int main() { vector vec; for (int i = 0; i < 100000; ++i) { vec.push_back(rand()); } // 用位图法解决问题 typedef unsigned int uint; uint maxNumber = 1000000000; int size = maxNumber / 8 + 1; char *p = new char[size](); int n = 1; for (uint i = 0; i < vec.size(); ++i) { // 计算整数应该放置的数组下标 int index = vec[i] / 8; // 计算对应字节的比特位 int offset = vec[i] % 8; // 获取相应比特位的数值 int v = p[index] & (1 << offset); if (0 != v) { cout << vec[i] << "是第"<< n <<"个重复的数据" << endl; ++n; } else { // 表示该数据不存在，把相应位置置1，表示记录该数据 p[index] = p[index] | (1 << offset); } } delete[]p; return 0; }
