大数据查重

哈希表 - 找重复数字、字符（不限制内存）

#include<iostream>
#include<vector>
#include<ctime>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int main()
{
    vector<int> vec;
    srand(time(NULL));
    for(int i = 0; i < 1000; ++i)
    {
        vec.push_back(rand() % 100);
    }
    // 问题1：找第一个出现重复的数字 - 需要set来统计
    unordered_set<int> set1;
    int count = 0;
    for(const auto & key : vec)
    {
        const auto it = set1.find(key); // O(1)
        if (it == set1.end())
        {
            set1.insert(key);
        }
        else
        {
            cout << "重复的数字是" << key << endl;
            ++count;
            // break; // 找所有重复出现的数字时，去掉break
        }
    }
    std::cout << "总共重复了" << count << "个数" << endl;
    // 问题2：统计重复的数字以及出现的次数 - 需要map来统计数字及次数
    unordered_map<int, int> map1;
    for(const auto & key : vec)
    {
        const auto it = map1.find(key);   // O(1)
        if (it == map1.end()) 
        {
            // map插入的是pair，这里emplace可以直接构建
            map1.emplace(key, 1); // O(1)
        }
        else
        {
            ++it->second;
        }
        // 以上for区域中的语句可以被一行代码代替：++map1[key]
    }
    for(const auto & pair : map1)
    {
        if(pair.second > 1)
        {
            cout << "数字" << pair.first << "重复" << pair.second << "次" << endl;
        }
    }
    // 问题3：去重
    unordered_set<int> set2;
    for(const auto & key : vec)
    {
        set2.emplace(key);
    }
    // 问题4：字符串中找第一个没有重复出现过的字符
    bool haveDuplicate = false;
    string str = "fgodgnffinogiofdngps";
    unordered_map<char, int> map2;
    for(const auto & key : str)
    {
        ++map2[key];
    }
    for(const auto & key : str)
    {
        if (map2[key] == 1)
        {
            haveDuplicate = true;
            cout << "第一个不重复的字符为" << key << endl;
            break;
        }
    }
    if (!haveDuplicate)
    {
        cout << "所有字符都重复" << endl;
    }
}

哈希表分桶 - 两个大文件，找重复内容（适当限制内存）

有两个文件分别是a和b，各自存放了1亿条IP地址，限制内存100MB，找出两个文件中重复的ip地址。
总体思路是，把一个文件的内容输入到哈希表中，遍历另一个文件中的每一条IP地址，与哈希表中的key比对。因此只需要提供1个文件的内存占用即可。
IPv4地址的大小是4个字节。1亿是100M，则1亿条IP地址就是400MB。如果再加上unordered_map结构的地址域，那就要再翻倍，把一个文件输入到哈希表中就要占800MB内存。这显然是超出了100MB的要求。
可以这样：文件a的IP地址依次读取，取模（或者称之为哈希函数），比如%11，这样把他们都分散到11个“桶”里。
把文件b也像这样，挨个IP地址取模，在a的相应的“桶”号下，去寻找。因为如果IP地址一样，用了相同的取模运算（哈希运算），所以是在同一个桶号里。
这样，就把1亿个IP地址分成了11波。内存压力减少到了80MB。

位数组 - （小内存）

如果数据集中的最大值很大，那么中间有好多无效的空位被浪费。总体上还是浪费内存的。

Bloom Filter 布隆过滤器 - （极限内存）

结合了哈希+位数组的优势。内存使用效率高。