哈希

• unordered关联式容器
• • unordered_map
  • unordered_set
• 底层结构
• • 哈希
  • • 哈希冲突
    • 哈希函数
    • • 直接定址法
      • 除留余数法
      • 平方取中法
      • 折叠法
      • 随机数法
      • 数学分析法
    • 解决哈希冲突
    • • 闭散列
      • • 线性探测
        • • 插入
          • 删除
        • 二次探测
      • 闭散列哈希代码实现
    • 开散列(哈希桶/拉链法)
    • • 开散列代码实现
      • • 实现unordered_set
        • 实现unordered_map
    • 开散列和闭散列的比较
    • 哈希的应用
    • • 位图
      • • 例题1：
        • 例题2：
      • 布隆过滤器

unordered关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次
数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

unordered_map

https://www.cplusplus.com/reference/unordered_map/

• unordered_map是存储<key,value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
• 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
• 在内部,unordered_map没有对<kye,value>按照任何特定的顺序排序,为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
• unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
• unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
• 它的迭代器至少是前向迭代器。

unordered_set

https://www.cplusplus.com/reference/unordered_set/

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

哈希

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log2N)，搜索的效率取决
于搜索过程中元素的比较次数。
理想的搜索方法：
可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

• 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单
  
  注意：
  哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
  

直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）=A*Key+B
适用于整数，且数据范围比较集中
优势：速度快，节省空间
缺陷：1、数据范围大直接定址法会浪费空间2、不能处理浮点数，字符串等数据

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)=key%p(p<=m),将关键码转换成哈希地址
特点：数据范围很大把数据映射到有限的空间里
缺陷：不同的值映射到同一个位置–哈希冲突

bool Insert(const pair<K, V>& kv)
		{
			HashData<K,V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			//计算负载因子
			if (_table.size() == 0)
			{
				_table.resize(10);
			}
			else if ((double)_n / (double)_table.size() > 0.7)
			{
				//增容,重新计算每个数据在新空间中的位置
				HashTable<K, V,KHash> newHT;
				newHT._table.resize(_table.size() * 2);
				for (auto& e : _table)
				{
					if (e._state == EXITS)
					{
						newHT.Insert(e._kv);
					}
				}
				_table.swap(newHT._table);

			}
			KHash kh;
			size_t start = kh(kv.first) % _table.size();
			size_t index = start;
			//探测后面的位置 ：线性探测/二次探测
			size_t i = 1;
			while (_table[index]._state == EXITS)
			{
				index = start + i;
				index %= _table.size();
				i++;
			}
			_table[index]._kv = kv;
			_table[index]._state = EXITS;
			_n++;
			return true;
		}

平方取中法

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)
作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法

数学分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。、

数学分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

解决哈希冲突

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。
那如何寻找下一个空位置呢？

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

线性探测：模出来映射的位置已经冲突，那就需要往后线性找一个空位置，存数据
线性探测缺点：某个连续位置出现冲突，会出现踩踏效应
<.font>

插入

• 通过哈希函数获取待插入元素在哈希表中的位置
• 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。因此线性探测采用标记的伪删除法来删除一个元素。

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
Hi=(H0+i^{2)%m或：Hi=(H0-i}2)%m，H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。
负载因子/载荷因子 = 存的数据个数/空间的大小

• 负载因子越大，冲突的概率越高，增删查改效率低；
• 负载因子越小，冲突的概率越低，增删查改效率高，但是空间利用率低，浪费很多

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置
都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装
满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
闭散列最大的缺陷就是空间利用率比较低，这是哈希的缺陷

闭散列哈希代码实现

namespace CloseHash
{
	enum State
	{
		EMPTY,
		EXITS,
		DELETE
	};
	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;//状态标识
	};
	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	//特化
	template<>
	struct Hash<string>
	{
		struct StringKHash//仿函数的目的：字符串转成对应的整型值，因为整形才能取模算映射位置
		{
			//期望：字符串不同，转出的整型值尽量不同
			size_t operator()(const string& s)
			{
				//BKDR Hash
				size_t value = 0;
				for (auto h : s)
				{
					value += h;
					value *= 131;
				}
				return value;
			}
		};
	};
	struct KHash
	{

	};
	template<class K,class V,class KHash = Hash<K>>//KHash仿函数
	class HashTable
	{
	public:
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K,V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
			//计算负载因子
			if (_table.size() == 0)
			{
				_table.resize(10);
			}
			else if ((double)_n / (double)_table.size() > 0.7)
			{
				//增容,重新计算每个数据在新空间中的位置
				HashTable<K, V,KHash> newHT;
				newHT._table.resize(_table.size() * 2);
				for (auto& e : _table)
				{
					if (e._state == EXITS)
					{
						newHT.Insert(e._kv);
					}
				}
				_table.swap(newHT._table);

			}
			KHash kh;
			size_t start = kh(kv.first) % _table.size();
			size_t index = start;
			//探测后面的位置 ：线性探测/二次探测
			size_t i = 1;
			while (_table[index]._state == EXITS)
			{
				index = start + i;
				index %= _table.size();
				i++;
			}
			_table[index]._kv = kv;
			_table[index]._state = EXITS;
			_n++;
			return true;
		}
		HashData<K,V>* Find(const K& key)
		{
			if(_table.size() == 0)
			{
				return nullptr;
			}
			KHash kh;
			size_t start = kh(key) % _table.size();
			size_t index = start;
			size_t i = 1;
			while (_table[index]._state == EXITS && _table[index]._state != EMPTY)
			{
				if (_table[index]._kv.first == key)
				{
					return &_table[index];
				}
				index = start + i;
				index %= _table.size();
				i++;

			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			{
				if (ret == nullptr)
				{
					return false;
				}
				else
				{
					ret->_state = DELETE;
					return false;
				}
			}
		}
	private:
		/*HashData* _table;
		size_t _size;
		size_t _capacity;*/
		vector<HashData<K,V>>  _table;
		size_t _n = 0;//存储的有效数据
	};
	struct IntKHash
	{
		int operator()(int i)
		{
			return i;
		}
	};
	struct StringKHash//仿函数的目的：字符串转成对应的整型值，因为整形才能取模算映射位置
	{
		//期望：字符串不同，转出的整型值尽量不同
		size_t operator()(const string& s)
		{
			//BKDR Hash
			size_t value = 0;
			for (auto h : s)
			{
				value += h;
				value *= 131;
			}
			return value;
		}
	};
	
}

开散列(哈希桶/拉链法)

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列代码实现

namespace OpenHash
{
	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			size_t value = 0;
			for (auto e : s)
			{
				value += e;
				value *= 131;
			}
			return value;
		}
	};
	template<class T>
	struct HashNode
	{
		HashNode<T>* _next;
		T _data;
		HashNode(const T& data)
			:_next(nullptr)
			, _data(data)
		{}
	};
	//前置声明
	template<class K, class T, class KeyofT, class KHash>
	class HashTable;


	
	//迭代器
	template<class K, class T, class KeyofT, class KHash = Hash<K>>
	struct  _HTIterator
	{
	
		typedef HashNode<T> Node;
		typedef _HTIterator<K, T, KeyofT, KHash>  Self;
		typedef HashTable<K, T, KeyofT, KHash> HT;
		Node* _node;
		HT* _pht;
		
		_HTIterator(Node* node, HT* pht)
			:_node(node)
			, _pht(pht)
		{}

		Self& operator++()
		{
			//当前桶中还有数据，就在当前桶往后走
			//当前桶走完了，需要往下一个桶去走
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyofT kot;
				KHash hf;
				size_t index = hf(kot()(_node->_data)) % _pht->_table.size();
				index++;
				while (index < _pht->_table.size())
				{
					if (_pht->_table[index])
					{
						_node = _pht->_table[index];
						return *this;
					}
					else
					{
						++index;
					}
					
				}
				_node = nullptr;
				

			}
			return *this;
		}
		
		T& operator*()
		{
			return _node->_data;
		}
		T* operator->()
		{
			return _node->_data;
		}
		bool operator != (const Self& s) const
		{
			return _node == s._node;
		}
		bool operator == (const Self& s) const
		{
			return _node == s._node;
		}
	};
	template<class K, class T, class KeyofT,class KHash = Hash<K>>
	class HashTable
	{
		typedef HashNode<T> Node;
		template<class K, class T, class KeyofT, class KHash = Hash<K>>
		friend struct _HTIterator;
	public:
		typedef _HTIterator<K, T, KeyofT, KHash> iterator;
		HashTable() = default;//显示指定生成默认构造函数
		HashTable(const HashTable& ht)
		{
			_n = ht._n;
			_table.resize(ht._table.size());
			for (size_t i; i < ht._table.size(); i++)
			{
				Node* cur = ht._table[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					//头插到新表
					copy->_next = _table[i];
					_table[i] = copy;
					cur = cur->_next;
				}
			}
		}
		HashTable& operator=(HashTable ht)
		{
			_table.swap(ht._table);
			swap(_n, ht._n);
			return *this;
		}
		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
		iterator begin()
		{
			size_t i = 0;
			while (i < _table.size())
			{
				if (_table[i])
				{
					return iterator(_table[i],this);//找到第一个桶
				}
				i++;
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}

		pair<iterator,bool> Insert(const T& data)
		{
			KeyofT kot;
			auto ret = Find(kot(data));
			if (ret != end())
			{
				return make_pair(ret, false);
			}
			KHash hf;
			//负载因子到1时，进行增容
			if (_n == _table.size())
			{
				vector<Node*>  newtable;
				size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
				newtable.resize(newsize, nullptr);


				//遍历旧表，把位置映射到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i])
					{
						Node* cur = _table[i];
						while (cur)
						{
							Node* next = cur->_next;
							size_t index = hf(kot(cur->_data)) % newtable.size();
							//头插
							cur->_next = newtable[index];
							newtable[index] = cur;
							cur = next;

						}
						_table[i] = nullptr;
					}
				}
				_table.swap(newtable);
			}

			size_t index = hf(kot(_data)) % _table.size();
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _table[index];
			_table[index] = newnode;
			_n++;
			return make_pair(iterator(newnode, this), true);
		}
		iterator* Find(const K& key)
		{
			if (_table.size() == 0)
			{
				return end();
			}
			KeyofT kot;
			KHash hf;
			size_t index = hf(key) % _table.size();
			Node* cur = _table[index];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				else
				{
					cur = cur->_next;
				}
			}
			return end;
		}
		bool Erase(const K& key)
		{
			KHash hf;
			size_t index = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[index];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (_table[index] == cur)
					{
						//删除的是第一个
						_table[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					
					_n--;
					delete cur;
					return true;
				}
				
					prev = cur;
					cur = cur->_next;
				
			}
			return false;
		}
	private:
		vector<Node*> _table;
		size_t _n;//有效数据的个数



	};

}

实现unordered_set

#include "HashTable.h"
namespace hs
{
	template<class K>
	class unordered_set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
	public:
		
		typedef typename OpenHash::HashTable<K, K,SetKeyofT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		
		pair<iterator,bool> insert(const K& k)
		{
			_ht.Insert(k);
			return true;
		}
	private:
		OpenHash::HashTable<K, K,SetKeyofT> _ht;
	};
	
}

实现unordered_map

#pragma once
#include "HashTable.h"
namespace hs
{
	template<class K,class V>
	class unordered_map
	{
		struct MapkeyofT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename OpenHash::HashTable<K, pair<K, V>, MapkeyofT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		OpenHash::HashTable<K, pair<K, V>, MapkeyofT> _ht;
	};
}

开散列和闭散列的比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a<=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

哈希的应用

位图

位图是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的
1代表存在0代表不存在

• 优点：节省空间，快
• 缺点：只能处理整形

例题1：

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

• 方案1：依次读取第一个文件中的所有整数标记映射到一个位图，再读取另一个文件中的所有整数，判断在不在位图，在就是交集中的数，不在就不是
• 方案二：依次读取第一个文件所有整数标记映射为位图1，依次读取第二个文件所有整数标记映射为位图2，再对两个位图进行与(依次与位图中的整数)与完还是1的位映射的整数就是交集

例题2：

给定100亿个整数，设计算法找到只出现一次的整数
答：标记一个整数的几种状态：

• 出现0次：00
• 出现1次：01
• 出现两次及以上：10

template<size_t N>//N是多大，就开多大的位图
	class BitSet
	{
	public:
		BitSet()
		{
			_bs.resize(N / 32 + 1, 0);
		}
		//把X映射的位标记成1
		void Set(size_t x)
		{
			//算出X映射的位在第i个整数
			//算出X映射的位在这个整数的第j个位
			size_t i = x / 32;
			size_t j = x % 32;
			//把bs[i]的第j位标记成1，并且不影响其他位
			_bs[i] |= (1 << j);

		}
		void RSet(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			//把bs[i]的第j位标记成0，并且不影响其他位
			_bs[i] &= (~(i << j));
		}
		bool Test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			//如果第j位是1，结果是非0，非0为真
			//如果第j位是1，结果是0，0为假
			return _bs[i] & (i << j);
		}
		void set(size_t x)
		{
			//00->01
			if (!_bs1.Test(x) && !_bs[2].Test(x))
			{
				_bs1.Set(x);
			}
			//01->10
			else if (!_bs1.Test(x) && _bs2.Test(x))
			{
				_bs1.Set(x);
				_bs2.RSet(x);
			}
			//10->10
			else if (_bs1.Test(x) && !_bs2.Test(x))
			{
				//不处理
			}
			else
			{
				assert(false);
			}

		}
	private:
		vector<int> _bs;
	};

布隆过滤器

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

• 优点：节省空间(相对于平衡搜索数和哈希表)，效率高
• 缺点：存在误判，判断在是不准确的，不在是准确的

#pragma once
#include "BitSet.h"

struct HashBKDR
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// BKDR Hash
		size_t value = 0;
		for (auto ch : s)
		{
			value += ch;
			value *= 131;
		}

		return value;
	}
};

struct HashAP
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// AP Hash
		register size_t hash = 0;
		size_t ch;
		for (long i = 0; i < s.size(); i++)
		{
			ch = s[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct HashDJB
{
	// "int"  "insert" 
	// 字符串转成对应一个整形值，因为整形才能取模算映射位置
	// 期望->字符串不同，转出的整形值尽量不同
	// "abcd" "bcad"
	// "abbb" "abca"
	size_t operator()(const std::string& s)
	{
		// BKDR Hash
		register size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};

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;
		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:
	bit::BitSet<N> _bitset;
	bit::vector<char> _bitset;

};


void TestBloomFilter()
{
	/*BloomFilter<100> bf;
	bf.Set("张三");
	bf.Set("李四");
	bf.Set("牛魔王");
	bf.Set("红孩儿");

	cout << bf.Test("张三") << endl;
	cout << bf.Test("李四") << endl;
	cout << bf.Test("牛魔王") << endl;
	cout << bf.Test("红孩儿") << endl;
	cout << bf.Test("孙悟空") << endl;*/

	BloomFilter<600> bf;

	size_t N = 100;
	std::vector<std::string> v1;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(1234 + i);
		v1.push_back(url);
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	for (auto& str : v1)
	{
		cout << bf.Test(str) << endl;
	}
	cout << endl << endl;

	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(6789 + i);
		v2.push_back(url);
	}

	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.Test(str))
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://zhuanlan.zhihu.com/p/43263751";
		url += std::to_string(6789 + i);
		v3.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;

}