554-大数据查重-哈希表应用

谁借莪１个温暖的怀抱￠ 2022-09-11 06:19 160阅读 0赞

## 大数据查重-哈希应用 ##

![在这里插入图片描述][1907190930a64a228fc988644e075a14.png]

## 模拟问题1 ##

**vector中放原始的数据，放着10000个随机的数字，有的数字有重复，有的数字没有重复，找第一个出现重复的数字**

#include <iostream>
    #include <vector>
    #include <unordered_set> 
    #include <unordered_map>
    #include <stdlib.h>
    #include <time.h>
    #include <string>
    using namespace std;
    
    int main()
    {
        
        //模拟问题，vector中放原始的数据
        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);// O(1)
            if (it == s1.end())//没有找到 
            {
        
                s1.insert(key);//当前的key是第一次出现 
            }
            else//有找到这个key，说明这个key是第一个重复的数字 
            {
        
                cout << "key:" << key << endl;
                break;
            }
        }
    
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**或者是找所有重复出现的数字**

#include <iostream>
    #include <vector>
    #include <unordered_set> 
    #include <unordered_map>
    #include <stdlib.h>
    #include <time.h>
    #include <string>
    using namespace std;
    
    int main()
    {
        
        //模拟问题，vector中放原始的数据
        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);// O(1)
            if (it == s1.end())//没有找到 
            {
        
                s1.insert(key);//当前的key是第一次出现 
            }
            else//有找到这个key，说明这个key是第一个重复的数字 
            {
        
                cout << "key:" << key << endl;
            }
        }
    
        return 0;
    }

**统计重复数字以及出现的次数**

#include <iostream>
    #include <vector>
    #include <unordered_set> 
    #include <unordered_map>
    #include <stdlib.h>
    #include <time.h>
    #include <string>
    using namespace std;
    
    int main()
    {
        
        //模拟问题，vector中放原始的数据
        vector<int> vec;
        srand(time(NULL));
        for (int i = 0; i < 10000; i++)
        {
        
            vec.push_back(rand() % 10000);
        }
    
        //统计重复数字以及出现的次数
        unordered_map<int, int> m1;
        for (int key : vec)
        {
        
            //pair first second
            //auto it = m1.find(key);//O(1)
            //if (it == m1.end())
            //{
        
            //    m1.emplace(key, 1);//O(1)
            //}
            //else
            //{
        
            //    it->second += 1;
            //}
            m1[key]++;
        }
        for (auto pair : m1)
        {
        
            if (pair.second > 1)
            {
        
                cout << "key:" << pair.first << " cnt:"
                    << pair.second << endl;
            }
        }
    
        return 0;
    }

**一组数据有些数字是重复的，把重复的数字过滤掉，每个数字只出现一次**

int main()
    {
        
        //模拟问题，vector中放原始的数据
        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)
        {
        
            s1.emplace(key);
        }
    }

## 模拟问题2 ##

**有一个字符串，这个字符串里有重复的字符，也有没有重复的字符，让你找出来第一个没有重复出现过的字符**

#include <iostream>
    #include <vector>
    #include <unordered_set> 
    #include <unordered_map>
    #include <stdlib.h>
    #include <time.h>
    #include <string>
    using namespace std;
    
    int main()
    {
        
        string src = "jjhfgiyuhrtytrs";
        //让你找出来第一个没有重复出现过的字符
        unordered_map<int, int> m;
        for (char ch : src)
        {
        
            m[ch]++;
        }
    
        for (char ch : src)
        {
        
            if (m[ch] == 1)
            {
        
                cout << "第一个没有重复出现过的字符是:" << ch << endl;
                return 0;
            }
        }
    
        cout << "所有字符都有重复出现过!" << endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 模拟问题3 ##

**有两个文件分别是a和b，里面放了很多ip地址(url地址、email地址)，让你找出来两个文件重复的ip，输出出来**

**如果是没有对内存限制：**  
把a文件中所有的ip存放在一个哈希表中，然后依次遍历文件b里面的ip，每  
遍历一个ip，在哈希表中搜索一下，搜到的，即是两个文件重复的ip并输出  
用到了哈希表的查询O(1)

**如果是有两个文件分别是a和b，各自存放在约1亿条ip地址，每个ip地址是4个字节限制内存使用100M，让找出来两个文件中重复的ip地址并输出**  
这样子的话，如果使用一张哈希表，  
![在这里插入图片描述][3e6aefd7c8754f79859e0b7692f70be2.png]  
显然，内存远远不够用。  
**怎么办？  
采用分治算法，把文件a和文件b分别分成很多小文件。**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[1907190930a64a228fc988644e075a14.png]: /images/20220828/36c46b3f6bc3465caf06c7d083ef4181.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/57b18bcfb8214786993604ac0f78f9ed.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d22a4a4b184a49a7b7d0a8c270580561.png
[3e6aefd7c8754f79859e0b7692f70be2.png]: /images/20220828/b09a240386514f66a3022c57a4d94c85.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/aa964fb05f7c49debff40a06181d8ec9.png