【C++进阶】哈希（万字详解）—— 运用篇(下）

快来打我* 2024-04-20 06:33 0阅读 0赞

> **🎇C++学习历程：入门**
> 
> --------------------
> 
>  *  **博客主页：**[一起去看日落吗][Link 1]
>  *  **持续分享博主的C++学习历程**
>  *  **`博主的能力有限，出现错误希望大家不吝赐教`**
>  *  **分享给大家一句我很喜欢的话：** 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。
> 
> --------------------
> 
> ![在这里插入图片描述][eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]

🍁 🍃 🍂 🌿

--------------------

#### 目录 ####

*  🍃 1. 模拟实现
 *   *  🌿 1.1 哈希表代码
     *  🌿 1.2 哈希表的改造
     *  🌿 1.3 哈希表的最终代码
     *  🌿 1.4 unordered\_map 的模拟实现
 *  🍃 2. 位图
 *   *  🌿 2.1 库中的位图
     *  🌿 2.2 模拟实现位图
 *  🍃 3. 布隆过滤器
 *   *  🌿 3.1 布隆过滤器提出
     *  🌿 3.2 布隆过滤器概念
     *  🌿 3.3 布隆过滤器优点
     *  🌿 3.4 布隆过滤器缺陷
     *  🌿 3.5 布隆过滤器模拟实现
 *  🍃 4. 海量数据面试题
 *   *  🌿 4.1 位图应用
     *  🌿 4.2 哈希切分+布隆过滤器应用

## 🍃 1. 模拟实现 ##

### 🌿 1.1 哈希表代码 ###

namespace Byih
    {
        
    	template<class K, class V>
    	struct HashNode
    	{
        
    		pair<K, V> _kv;
    		HashNode<K, V>* _next;
    
    		HashNode(const pair<K, V>& kv)
    			:_kv(kv)
    			, _next(nullptr)
    		{
        }
    	};
    
    	size_t GetNextPrime(size_t prime)
    	{
        
    		const int PRIMECOUNT = 28;
    		static const size_t primeList[PRIMECOUNT] =
    		{
        
    			53ul, 97ul, 193ul, 389ul, 769ul,
    			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    			1610612741ul, 3221225473ul, 4294967291ul
    		};
    
    		size_t i = 0;
    		for (; i < PRIMECOUNT; ++i)
    		{
        
    			if (primeList[i] > prime)
    				return primeList[i];
    		}
    
    		return primeList[i];
    	}
    
    	template<class K, class V, class Hash = HashFunc<K>>
    	class HashTable
    	{
        
    		typedef HashNode<K, V> Node;
    	public:
    
    		// 拷贝 和 赋值 需要自己实现桶的拷贝
    
    		~HashTable()
    		{
        
    			for (size_t i = 0; i < _tables.size(); i++)
    			{
        
    				Node* cur = _tables[i];
    				while (cur)
    				{
        
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    				}
    
    				_tables[i] = nullptr;
    			}
    			_n = 0;
    		}
    
    		bool Erase(const K& key)
    		{
        
    			if (_tables.size() == 0)
    			{
        
    				return false;
    			}
    
    			Hash hf;
    			// 素数
    			size_t index = hf(key) % _tables.size();
    			Node* prev = nullptr;
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (cur->_kv.first == key)
    				{
        
    					// 1、cur是头结点
    					// 2、非头节点
    					if (prev == nullptr)
    					{
        
    						_tables[index] = cur->_next;
    					}
    					else
    					{
        
    						prev->_next = cur->_next;
    					}
    
    					delete cur;
    					--_n;
    
    					return true;
    				}
    				else
    				{
        
    					prev = cur;
    					cur = cur->_next;
    				}
    			}
    
    			return false;
    		}
    
    		Node* Find(const K& key)
    		{
        
    			if (_tables.size() == 0)
    			{
        
    				return nullptr;
    			}
    
    			Hash hf;
    			size_t index = hf(key) % _tables.size();
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (cur->_kv.first == key)
    				{
        
    					return cur;
    				}
    				else
    				{
        
    					cur = cur->_next;
    				}
    			}
    
    			return nullptr;
    		}
    
    		bool Insert(const pair<K, V>& kv)
    		{
        
    			Hash hf;
    
    			//当负载因子到1时，进行扩容
    			if (_n == _tables.size())
    			{
        
    				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    				size_t newSize = GetNextPrime(_tables.size());
    
    				//HashTable<K, V> newHT;
    				vector<Node*> newtables;
    				newtables.resize(newSize, nullptr);
    				for (size_t i = 0; i < _tables.size(); ++i)
    				{
        
    					Node* cur = _tables[i];
    					while (cur)
    					{
        
    						Node* next = cur->_next;
    
    						size_t index = hf(cur->_kv.first) % newSize;
    						cur->_next = newtables[index];
    						newtables[index] = cur;
    
    						cur = next;
    					}
    					_tables[i] = nullptr;
    				}
    
    				newtables.swap(_tables);
    			}
    
    			size_t index = hf(kv.first) % _tables.size();
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (cur->_kv.first == kv.first)
    				{
        
    					return false;
    				}
    				else
    				{
        
    					cur = cur->_next;
    				}
    			}
    
    			Node* newnode = new Node(kv);
    			newnode->_next = _tables[index];
    			_tables[index] = newnode;
    
    			++_n;
    
    			return true;
    		}
    
    	private:
    		vector<Node*> _tables;
    		size_t _n = 0; // 存储多少有效数据
    	};
    }

--------------------

### 🌿 1.2 哈希表的改造 ###

*  模板参数的改造

K:关键码类型  
V: 不同容器V的类型不同，如果是unordered\_map，V代表一个键值对，如果是unordered\_set,V为 K  
KeyOfT: 在哈希表中需要取到value，因为V的类型不同，通过value取key的方式就不同，详细见unordered\_map/set的实现  
Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，如果是Key为string类型，需要将Key转换为整形数字才能取模

template<class K, class T, class KeyOfT, class Hash = HashFunc<T> >
    class HashBucket;

--------------------

*  哈希表节点结构

template<class T>
    struct HashNode
    {
        
        T _data;
        HashNode<T>* _next;
    
        HashNode(const T& data)
            :_data(data)
                , _next(nullptr)
            {
        }
    };

如果是unordered\_map，v代表一个键值对，如果是unordered\_set,v为 K

--------------------

*  operator++模拟实现

当下一个节点不为空时，++后的节点就在当前桶，返回即可，当下一个节点为空时，我们需要找下一个桶，首先通过当前节点计算找到当前节点所在桶的位置index，计算出后，++index即找到了下一个桶，当下一个桶存在时，如果下一个桶里面有数据(即不为空)，则将第一个数据给当前节点，就实现了++，否则继续找下一个桶，当循环出来时，有可能是找到++后的节点了，也有可能说明走完了后面没有桶了，所以循环出来需要判断是不是没有桶了，没有桶则返回nullptr

Self operator++()
    {
        
        if (_node->_next) // 在当前桶迭代
        {
        
            _node = _node->_next;
        }
        else // 找下一个桶
        {
        
            KeyOfT kot;
            const K& key = kot(_node->_data);
            Hash hf;
            size_t index = hf(key) % _ht->_tables.size();
            ++index;
            _node = nullptr;
            while (index < _ht->_tables.size())
            {
        
                if (_ht->_tables[index])
                {
        
                    _node = _ht->_tables[index];
                    break;
                }
                else
                {
        
                    ++index;
                }
            }
    
            // 后面没有桶了
            if (index == _ht->_tables.size())
            {
        
                _node = nullptr;
            }
        }
    
        return *this;
    }

--------------------

*  operator\*的模拟实现

T& operator*()
    {
        
        return _node->_data;
    }

--------------------

*  operator->的模拟实现

T* operator->()
    {
        
        return &_node->_data;
    }

--------------------

*  operator==和operator!=的模拟实现

bool operator!=(const Self& s) const
    {
        
        return _node != s._node;
    }
    
    bool operator==(const Self& s) const
    {
        
        return _node == s._node;
    }

--------------------

### 🌿 1.3 哈希表的最终代码 ###

namespace Byih
    {
        
    	template<class T>
    	struct HashNode
    	{
        
    		T _data;
    		HashNode<T>* _next;
    
    		HashNode(const T& data)
    			:_data(data)
    			, _next(nullptr)
    		{
        }
    	};
    
    	size_t GetNextPrime(size_t prime)
    	{
        
    		const int PRIMECOUNT = 28;
    		static const size_t primeList[PRIMECOUNT] =
    		{
        
    			53ul, 97ul, 193ul, 389ul, 769ul,
    			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    			1610612741ul, 3221225473ul, 4294967291ul
    		};
    
    		size_t i = 0;
    		for (; i < PRIMECOUNT; ++i)
    		{
        
    			if (primeList[i] > prime)
    				return primeList[i];
    		}
    
    		return primeList[i];
    	}
    
    	// 前置声明
    	template<class K, class T, class Hash, class KeyOfT>
    	class HashTable;
    
    	template<class K, class T, class Hash, class KeyOfT>
    	struct HTIterator
    	{
        
    		typedef HashNode<T> Node;
    		typedef HashTable<K, T, Hash, KeyOfT> HT;
    		typedef HTIterator<K, T, Hash, KeyOfT> Self;
    
    		Node* _node;
    		HT* _ht;
    
    		HTIterator(Node* node, HT* ht)
    			:_node(node)
    			, _ht(ht)
    		{
        }
    
    		bool operator!=(const Self& s) const
    		{
        
    			return _node != s._node;
    		}
    
    		T& operator*()
    		{
        
    			return _node->_data;
    		}
    
    
    		T* operator->()
    		{
        
    			return &_node->_data;
    		}
    
    		Self operator++()
    		{
        
    			if (_node->_next) // 在当前桶迭代
    			{
        
    				_node = _node->_next;
    			}
    			else // 找下一个桶
    			{
        
    				KeyOfT kot;
    				const K& key = kot(_node->_data);
    				Hash hf;
    				size_t index = hf(key) % _ht->_tables.size();
    				++index;
    				_node = nullptr;
    				while (index < _ht->_tables.size())
    				{
        
    					if (_ht->_tables[index])
    					{
        
    						_node = _ht->_tables[index];
    						break;
    					}
    					else
    					{
        
    						++index;
    					}
    				}
    
    				// 后面没有桶了
    				if (index == _ht->_tables.size())
    				{
        
    					_node = nullptr;
    				}
    			}
    
    			return *this;
    		}
    	};
    
    	template<class K, class T,  class KeyOfT, class Hash = HashFunc<K>>
    	class HashTable
    	{
        
    		typedef HashNode<T> Node;
    
    		//template<class K, class T, class Hash, class KeyOfT>
    		friend struct HTIterator<K, T, Hash, KeyOfT>;
    	public:
    		typedef HTIterator<K, T, Hash, KeyOfT> iterator;
    
    		iterator begin()
    		{
        
    			for (size_t i = 0; i < _tables.size(); ++i)
    			{
        
    				if (_tables[i])
    				{
        
    					return iterator(_tables[i], this);
    				}
    			}
    
    			return end();
    		}
    
    		iterator end()
    		{
        
    			return iterator(nullptr, this);
    		}
    
    		// 拷贝 和 赋值 需要自己实现桶的拷贝
    
    		~HashTable()
    		{
        
    			for (size_t i = 0; i < _tables.size(); i++)
    			{
        
    				Node* cur = _tables[i];
    				while (cur)
    				{
        
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    				}
    
    				_tables[i] = nullptr;
    			}
    
    			_n;
    		}
    
    		bool Erase(const K& key)
    		{
        
    			if (_tables.size() == 0)
    			{
        
    				return false;
    			}
    
    			Hash hf;
    			KeyOfT kot;
    
    			// 素数
    			size_t index = hf(key) % _tables.size();
    			Node* prev = nullptr;
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (kot(cur->_data) == key)
    				{
        
    					// 1、cur是头结点
    					// 2、非头节点
    					if (prev == nullptr)
    					{
        
    						_tables[index] = cur->_next;
    					}
    					else
    					{
        
    						prev->_next = cur->_next;
    					}
    
    					delete cur;
    					--_n;
    
    					return true;
    				}
    				else
    				{
        
    					prev = cur;
    					cur = cur->_next;
    				}
    			}
    
    			return false;
    		}
    
    		Node* Find(const K& key)
    		{
        
    			if (_tables.size() == 0)
    			{
        
    				return nullptr;
    			}
    
    			Hash hf;
    			KeyOfT kot;
    			size_t index = hf(key) % _tables.size();
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (kot(cur->_data) == key)
    				{
        
    					return cur;
    				}
    				else
    				{
        
    					cur = cur->_next;
    				}
    			}
    
    			return nullptr;
    		}
    
    		bool Insert(const T& data)
    		{
        
    			Hash hf;
    			KeyOfT kot;
    
    			//当负载因子到1时，进行扩容
    			if (_n == _tables.size())
    			{
        
    				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    				size_t newSize = GetNextPrime(_tables.size());
    
    				//HashTable<K, V> newHT;
    				vector<Node*> newtables;
    				newtables.resize(newSize, nullptr);
    				for (size_t i = 0; i < _tables.size(); ++i)
    				{
        
    					Node* cur = _tables[i];
    					while (cur)
    					{
        
    						Node* next = cur->_next;
    
    						const K& key = kot(cur->_data);
    						size_t index = hf(key) % newSize;
    
    						cur->_next = newtables[index];
    						newtables[index] = cur;
    
    						cur = next;
    					}
    					_tables[i] = nullptr;
    				}
    
    				newtables.swap(_tables);
    			}
    
    			const K& key = kot(data);
    			size_t index = hf(key) % _tables.size();
    			Node* cur = _tables[index];
    			while (cur)
    			{
        
    				if (kot(cur->_data) == kot(data))
    				{
        
    					return false;
    				}
    				else
    				{
        
    					cur = cur->_next;
    				}
    			}
    
    			Node* newnode = new Node(data);
    			newnode->_next = _tables[index];
    			_tables[index] = newnode;
    
    			++_n;
    
    			return true;
    		}
    
    	private:
    		vector<Node*> _tables;
    		size_t _n = 0; // 存储多少有效数据
    	};
    }

--------------------

### 🌿 1.4 unordered\_map 的模拟实现 ###

#pragma once
    #include "HashTable.h"
    namespace byh
    {
        
    	template<class K, class V>
    	class unordered_map
    	{
        
    		struct MapKeyOfT
    		{
        
    			const K& operator()(const pair<const K, V>& kv) const
    			{
        
    				return kv.first;
    			}
    		};
    	public:
             iterator begin()
    		{
        
    			return _ht.begin();
    		}
    
    		iterator end()
    		{
        
    			return _ht.end();
    		}
            //插入
    		pair<iterator,bool> insert(const pair<const K, V>& kv)
    		{
        
    			return _ht.Insert(kv);
    		}
            //[]运算符重载
             V& operator[](const K& key)
             {
        
                 pair<iterator,bool> ret = insert(make_pair(key,V()));
                 iterator it = ret.first;
                 return it->second;
             }
            //删除
            bool erase(const K& key)
            {
        
                return _ht.Erase(key);
            }
            //查找
            iterator find(const K& key)
            {
        
                return _ht.Find(key);
            }
    	private:
    		Byih::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
    	};
    }

实现unordered\_map只需要调用底层哈希表对应的接口即可，实现unordered\_set不一样的是它不需要实现\[\]运算符重载

--------------------

## 🍃 2. 位图 ##

**所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的**。适用于海量数据的状态：比如：40亿数据，需要16G内存；若用位图存放这些数据在不在的状态，只需要16/32G，约500M。

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

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

**主要应用：**

1.  快速查找某个数据是否在一个集合中
2.  排序 + 去重
3.  求两个集合的交集、并集等
4.  操作系统次磁盘中的标记等

*  优点：节省空间，速度快
 *  缺点：只能处理整形数据

--------------------

### 🌿 2.1 库中的位图 ###

**主要接口：set（将某位设为1） reset（将某位设为0） test（判断某一位是否为1）**

bitset<100> bs;
    	//将某位设置为1
    	bs.set(11);bs.set(5);bs.set(78);bs.set(23);bs.set(12);
    	//将某位设置为0
    	bs.reset(11);
     
    	//判断某位是否为1
    	for (size_t i = 0; i < 100; i++)
    	{
        
    		//cout << i << ":" << bs.test(i) << " ";
    		//if (i != 0 && i % 10 == 0)
    		//	cout << endl;
    		if (bs.test(i) == 1)
    			cout << i << " ";
    	}
    	cout << endl;

--------------------

### 🌿 2.2 模拟实现位图 ###

template<size_t N>
    	class byh
    	{
        
    	public:
    		BitSet()
    		{
        
    			_bits.resize(N / 32 + 1, 0);//默认构造，会对位图进行初始化
    		}
     
    		// 把x映射的位标记成1
    		void Set(size_t x)
    		{
        
    			assert(x < N);
     
    			// 算出x映射的位在第i个整数
    			// 算出x映射的位在这个整数的第j个位
    			size_t i = x / 32;
    			size_t j = x % 32;
     
    			// _bits[i] 的第j位标记成1，并且不影响他的其他位
    			_bits[i] |= (1 << j); //或等于
    			//(1 << j)
    			//00000001000000000
    		}
     
    		void Reset(size_t x)
    		{
        
    			assert(x < N);
     
    			size_t i = x / 32;
    			size_t j = x % 32;
     
    			// _bits[i] 的第j位标记成0，并且不影响他的其他位
    			_bits[i] &= (~(1 << j)); //与等于
    			//对 1 << j 取反就行
    			//~(1 << j)
    			//1111111101111111111	
    		}
     
     
    		bool Test(size_t x)
    		{
        
    			assert(x < N);
     
    			size_t i = x / 32;
    			size_t j = x % 32;
     
    			// 如果第j位是1，结果是非0，非0就是真
    			// 如果第j为是0，结果是0，0就是假
    			return _bits[i] & (1 << j);//直接把这一位取出来是1还是0
    			//return (_bits[i] >> j) & 1;//这样写也可以
    		}
    	private:
    		vector<int> _bits;
    	};

--------------------

## 🍃 3. 布隆过滤器 ##

### 🌿 3.1 布隆过滤器提出 ###

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1.  用哈希表存储用户记录，缺点：浪费空间
2.  用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3.  将哈希与位图结合，即布隆过滤器

--------------------

### 🌿 3.2 布隆过滤器概念 ###

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 **一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中**。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

![在这里插入图片描述][b40d6a6807a64413a9225080c8910c3e.png]  
[原理讲解][Link 2]

--------------------

### 🌿 3.3 布隆过滤器优点 ###

1.  增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2.  哈希函数相互之间没有关系，方便硬件并行运算
3.  布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4.  在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5.  数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6.  使用同一组散列函数的布隆过滤器可以进行交、并、差运算

--------------------

### 🌿 3.4 布隆过滤器缺陷 ###

1.  有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2.  不能获取元素本身
3.  一般情况下不能从布隆过滤器中删除元素
4.  如果采用计数方式删除，可能会存在计数回绕问题

--------------------

### 🌿 3.5 布隆过滤器模拟实现 ###

//布隆过滤器实际上是对位图的改进，所以实现上也是对位图的封装，一般只提供set和test接口，不能实现reset（删除）
    template<size_t N, class K = std::string,class Hash1 = HashBKDR,class Hash2 = HashAP,class Hash3 = HashDJB>
    //后面几个是字符串哈希函数的仿函数
    class BloomFilter
    {
        
    public:
    	void Set(const K& key)
    	{
        
    		//Hash1 hf1;
    		//size_t i1 = hf1(key);//以下写法也可以
    		size_t i1 = Hash1()(key) % N;//Hash1()是仿函数的匿名对象
    		size_t i2 = Hash2()(key) % N;
    		size_t i3 = Hash3()(key) % N;
     
    		cout << i1 << " " << i2 << " " << i3 << endl;
     
    		_bitset.Set(i1);
    		_bitset.Set(i2);
    		_bitset.Set(i3);
    	}
     
    	bool Test(const K& key)//判断是否存在
    	{
        
    		size_t i1 = Hash1()(key) % N;
    		if (_bitset.Test(i1) == false)
    		{
        
    			return false;
    		}
     
    		size_t i2 = Hash2()(key) % N;
    		if (_bitset.Test(i2) == false)
    		{
        
    			return false;
    		}
     
    		size_t i3 = Hash3()(key) % N;
    		if (_bitset.Test(i3) == false)
    		{
        
    			return false;
    		}
     
    		// 这里3个位都在，有可能是其他key占了，在是不准确的，存在误判
    		// 不在是准确的
    		return true;
    	}
     
    private:
    	byh::BitSet<N> _bitset; // 对位图的封装
    	//byh::vector<char> _bitset;
    };

--------------------

## 🍃 4. 海量数据面试题 ##

### 🌿 4.1 位图应用 ###

*  题目一

**给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？**

**思路**：100亿的整数范围还是42亿，因此用一个位图来存储只需要512M  
将一个文件映射到位图中，再依次读取另一个文件的数据，看在不在位图中，在就是交集；或者构建两个位图，求他们的交集；

*  题目二

**给定100亿个整数，设计算法找到只出现一次的整数？**

**思路**：用位图的思想，一个bit位能表示两种状态，这里至少是3种状态，因此需要两个bit位00表示没出现；01表示只出现一次；10表示出现过2次及以上；将所有数插入位图中，然后遍历位图，找出标志位01的位即为所求

--------------------

### 🌿 4.2 哈希切分+布隆过滤器应用 ###

**哈希切分的原理**：就是将一个大文件，利用哈希的原理（i = Hash()(ip) % 100， i表示小文件的编号），将其分为若干个小文件。

**哈希切割的特点**：相同的ip一定进入了同一个小文件当中。

*  题目三

**给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法**

1.  **近似算法**：利用布隆过滤器100亿个query（ip），可以看做string，假设为100G，那么两个文件一共是200G。将A文件依次映射到一个布隆过滤器中，再依次读取B文件中的数据，与布隆过滤器里的内容比较，在就是交集，但是会有一定的误判率。
2.  **精确算法**：利用哈希切分 + 布隆过滤器  
    可以将AB文件都切割成200个小文件（哈希切分并不是均匀的，依次要保证小文件小于内存大小），按照同样的映射函数 i = Hash()(ip) % 200 这样AB中相同的ip，都进了各自对应的编号i的小文件，因此只需要依次比较Ai和Bi中的交集即可

![在这里插入图片描述][575bdc5e2ed84ea8b848ad3d6ae419fc.png]

*  题目四

**给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？**

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

**思路**：哈希切分，切分成100个小文件（相同的ip一定进入了同一个小文件）然后只需统计各个小文件各个ip的频次（比如用一个map<string, int>统计），找出每个小文件频次最高的ip地址进行比较即可；要求 top K的ip，可以建一个K个元素小堆，后面的元素依次与堆顶元素比较，比它大就替换进堆，最终这个小堆就是top K ；

![在这里插入图片描述][0ef290c96c2041cba561d2a0f466735c.png]

--------------------

[Link 1]: https://blog.csdn.net/m0_60338933?type=blog
[eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ae36f26ffa3b4478b894ceb82f58f08a.jpeg
[c4d338a3871440d5a8b5abcb4798ed49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4fbb1998ea604c61987a91a1fd0fa406.png
[b40d6a6807a64413a9225080c8910c3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ab04efb838c24e238d35c557cee36ba1.png
[Link 2]: https://zhuanlan.zhihu.com/p/43263751/
[575bdc5e2ed84ea8b848ad3d6ae419fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/493fdcc4a33747a3b238947c87f0dd55.png
[0ef290c96c2041cba561d2a0f466735c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e998499571074105bfa69895088fe3c0.png