一、哈希

1. 哈希概念

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希算法简介：

Hash算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点，就是很难找到逆向规律。
Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。
Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。

2. 哈希冲突

对于两个数据元素的关键字 $k_i$ 和 $k_j$ (i != j)，有 $k_i$ != $k_j$ ，但有：Hash( $k_i$ ) ==Hash( $k_j$ )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

3. 哈希函数

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

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数:

直接定址法

直接定址法就是取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p（p<=m）。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。

平方取中法

取关键字平方后的中间几位作为散列地址。

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

例如：
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。

通常应用于关键字长度不等时采用此法。

数字分析法

分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

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

【注意】

哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

4. 哈希冲突的解决

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

闭散列

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

寻找下一个空位置的方法：

线性探测

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

插入

通过哈希函数获取待插入元素在哈希表中的位置。

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

如：

删除

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

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State
{
	EMPTY, //空
	EXIST, //存在
	DELETE //删除
};

线性探测的实现：

// 注意：假如实现的哈希表中元素唯一，即key相同的元素不再进行插入
// 为了实现简单，此哈希表中我们将比较直接与元素绑定在一起
template<class K, class V, class HashFunc = DefaultHash<K>>
class HashTable
{
	typedef HashData<K, V> Data;
public:

	bool Insert(const pair<K, V> kv)
	{
		if (Find(kv.first))
		{
			return false;
		}

		//负载因子大于0.7就扩容
		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
		{
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			HashTable<K, V> newHT;
			newHT._tables.resize(newSize);

			//遍历旧表，重新映射
			for (auto& e : _tables)
			{
				if (e._state == EXITS)
				{
					newHT.Insert(e._kv);
				}
			}

			newHT._tables.swap(_tables);
		}

		HashFunc hf{};
		size_t starti = hf(kv.first);
		starti %= _tables.size();

		size_t hashi = starti;
		size_t i = 1;
		//线性探测
		while (_tables[hashi]._state == EXITS)
		{
			hashi = starti + i;
			++i;
			hashi %= _tables.size();
		}

		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXITS;
		++_n;
		return true;
	}

	Data* Find(const K& key)
	{
		if (_tables.size() == 0)
		{
			return nullptr;
		}
		
		HashFunc hf{};
		size_t starti = hf(key);
		starti %= _tables.size();

		size_t hashi = starti;
		size_t i = 1;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}
			hashi = starti + i;
			++i;
			hashi %= _tables.size();
		}				
		return nullptr;
	}

	bool Erase(const K& key)
	{
		Data* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_n;
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	vector<Data> _tables;
	size_t _n = 0; //存储关键字个数

};

注意：

哈希表什么情况下进行扩容？如何扩容？

线性探测优点：

实现非常简单。

线性探测缺点：

一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢? 可以利用二次探测解决。

二次探测

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

如:

研究表明：

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

开散列

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

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列实现：

namespace OpenHash
{
	//定义节点
	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)
		{}
	};

	template<class K, class V, class HashFunc = DefaultHash<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

	public:

		//HashTable(){}

		//HashTable(HashTable<K, V, DefaultHash<K>> ht)
		//{
		//	this->_tables.swap(ht._tables);
		//	_n = ht._n;
		//}

		~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 Insert(const pair<K, V>& kv)
		{
			//kv已经存在
			if (Find(kv.first))
			{
				return false;
			}

			HashFunc hf{};

			//负载因子 == 1， 扩容
			if (_tables.size() == _n)
			{
				//法一， 存在缺陷
				/*size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize, nullptr);

				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}

				newHT._tables.swap(_tables);*/

				//法二，不销毁原节点
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				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 hashi = hf(cur->_kv.first);
						hashi %= newSize;
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}

			size_t hashi = hf(kv.first);
			hashi %= _tables.size();

			//头插到对于的桶
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			//表为空
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			HashFunc hf{};
			size_t hashi = hf(key);
			hashi %= _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			HashFunc hf{};
			size_t hashi = hf(key);
			hashi %= _tables.size();

			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						cur->_next = _tables[hashi];
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}


	private:
		//定义指针数组
		vector<Node*> _tables;
		size_t _n = 0;

	};
}

开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

void _CheckCapacity()
{
	size_t bucketCount = BucketCount();
	if (_tables.size() == bucketCount )
	{
		//法一， 存在缺陷
		/*size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		HashTable<K, V> newHT;
		newHT._tables.resize(newSize, nullptr);

		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				newHT.Insert(cur->_kv);
				cur = cur->_next;
			}
		}

		newHT._tables.swap(_tables);*/

		//法二，不销毁原节点
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		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 hashi = hf(cur->_kv.first);
				hashi %= newSize;
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				cur = next;
			}
			_tables[i] = nullptr;
		}
		newTables.swap(_tables);
	}
}

开散列与闭散列比较

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

二、哈希表

哈希表是哈希函数的一个主要应用，使用哈希表能够快速的按照关键字查找数据记录。（注意：关键字不是像在加密中所使用的那样是秘密的，但它们都是用来“解锁”或者访问数据的。）例如，在英语字典中的关键字是英文单词，和它们相关的记录包含这些单词的定义。在这种情况下，哈希函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

哈希表的实现

模板参数列表

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

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

增加迭代器

//定义节点
	//T既可以接收key，也能接收pair类型
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//声明HashTable ,为了实现简单，在哈希桶的迭代器类中需要用到HashTable本身，
	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable;

	//定义迭代器
	template<class K, class T, class KeyOfT, class HashFunc>
	class _Iterator
	{
		typedef HashNode<T> Node;
		typedef _Iterator<K, T, KeyOfT, HashFunc> Self;


	public:
		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;

		_Iterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot{};
				HashFunc hf{};

				size_t hashi = hf(kot(_node->_data));
				hashi%=_pht->_tables.size();
				++hashi;
				//寻找下一个不为空的桶
				for (; hashi < _pht->_tables.size(); ++hashi)
				{
					if (_pht->_tables[hashi])
					{
						_node = _pht->_tables[hashi];
						break;
					}
				}

				//没有找到
				if (hashi == _pht->_tables.size())
				{
					_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;
		}
	};

HashTable的实现

	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable
	{
		template<class K, class T, class KeyOfT, class HashFunc>
		friend class _Iterator;

		typedef HashNode<T> Node;

	public:

		typedef _Iterator<K, T, KeyOfT, HashFunc> iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return iterator(cur, 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 = 0;
		}

		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
			};

			// 获取比prime大那一个素数
			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[i];
		}

		pair<iterator, bool> Insert(const T& data)
		{
			HashFunc hf{};
			KeyOfT kot{};

			iterator pos = Find(kot(data));

			//kv已经存在
			if (pos != end())
			{
				return make_pair(pos, false);
			}


			//负载因子 == 1， 扩容
			if (_tables.size() == _n)
			{
				//法一， 存在缺陷
				/*size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize, nullptr);

				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}

				newHT._tables.swap(_tables);*/

				//法二，不销毁原节点
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

				size_t newSize = GetNextPrime(_tables.size());
				if (newSize != _tables.size())
				{
					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 hashi = hf(kot(cur->_data)) % newSize;
							cur->_next = newTables[hashi];
							newTables[hashi] = cur;

							cur = next;
						}
						_tables[i] = nullptr;
					}
					newTables.swap(_tables);
				}
			}

			size_t hashi = hf(kot(data));
			hashi %= _tables.size();

			//头插到对于的桶
			Node* newnode = new Node(kot(data));
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return make_pair(iterator(newnode, this), true);
		}

		iterator Find(const K& key)
		{
			//表为空
			if (_tables.size() == 0)
			{
				return iterator(nullptr, this);
			}

			HashFunc hf{};
			KeyOfT kot{};
			size_t hashi = hf(key);
			hashi %= _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
				return iterator(nullptr, this);
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return false;
			}

			KeyOfT kot{};
			HashFunc hf{};
			size_t hashi = hf(key);
			hashi %= _tables.size();

			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						cur->_next = _tables[hashi];
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}


	private:
		//定义指针数组
		vector<Node*> _tables;
		size_t _n = 0;

	};

三、封装unordered系列关联式容器

1. 封装unordered_set

unordered_set中存储的是Key模型，HashFunc是哈希函数类型。在实现时，只需将HashTable中的接口重新封装即可。

template<class K, class HashFunc = DefaultHash<K>>
class unordered_set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

public:

	typedef typename Hash::HashTable < K, K, SetKeyOfT, HashFunc>::iterator iterator;


	pair<iterator, bool> insert(const K& key)
	{
		return _ht.Insert(key);
	}

	iterator begin()
	{
		return _ht.begin();
	}

	iterator end()
	{
		return _ht.end();
	}

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}
private:
	Hash::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
};

2. 封装unordered_map

unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HashFunc是哈希函数类型。在实现时，只需将HashTable中的接口重新封装即可。

#pragma once
#include"HashTable.h"

namespace lhf
{
	template<class K, class V, class HashFunc = DefaultHash<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:

		typedef typename Hash::HashTable < K, pair<K, V>, MapKeyOfT, HashFunc>::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.first);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		Hash::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
	};
}

四、哈希表的应用

1. 位图

概念

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

应用

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中。

遍历，时间复杂度O(N)，并且空间消耗很大。

排序(O(NlogN))，利用二分查找: logN。

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

位图的实现

// N个比特位图
template<size_t N>
class bitset
{
public:
	bitset()
	{
		// +1 保证有足够多的比特位，最多浪费8个
		_bits.resize(N / 8 + 1, 0);
	}

	//x映射的位置标记为1
	void set(size_t x)
	{
		// x映射的比特位在第几个char对象
		size_t i = x / 8;

		// x在char第几个比特位
		size_t j = x % 8;

		_bits[i] |= (1 << j);
	}

	void reset(size_t x)
	{
		// x映射的比特位在第几个char对象
		size_t i = x / 8;

		// x在char第几个比特位
		size_t j = x % 8;

		_bits[i] &= (~(1 << j));
	}

	bool test(size_t x)
	{
		// x映射的比特位在第几个char对象
		size_t i = x / 8;

		// x在char第几个比特位
		size_t j = x % 8;

		return _bits[i] & 1 << j;

	}

private:
	std::vector<char> _bits;
};

2. 布隆过滤器

概念

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

布隆过滤器的插入

向布隆过滤器中插入：“baidu”

向布隆过滤器中插入：“tencent”:

布隆过滤器的实现

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

struct JSHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 1315423911;
		for (auto ch : s)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};

template<size_t M,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash,
	class HashFunc4 = JSHash>
class BloomFilter
{
public:

	void Set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % M;
		size_t hash2 = HashFunc2()(key) % M;
		size_t hash3 = HashFunc3()(key) % M;
		size_t hash4 = HashFunc4()(key) % M;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
		_bs.set(hash4);
	}

	bool Test(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % M;
		if (_bs.test(hash1 == false))
		{
			return false;
		}

		size_t hash2 = HashFunc2()(key) % M;
		if (_bs.test(hash2 == false))
		{
			return false;
		}

		size_t hash3 = HashFunc3()(key) % M;
		if (_bs.test(hash3 == false))
		{
			return false;
		}

		size_t hash4 = HashFunc4()(key) % M;
		if (_bs.test(hash4 == false))
		{
			return false;
		}

		return true;
	}


private:
	bitset<M> _bs;
};

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：

布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：
将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。 但是无法确认元素是否真正在布隆过滤器中，并且存在计数回绕。

布隆过滤器优缺点

优点

增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

哈希函数相互之间没有关系，方便硬件并行运算

布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺陷

有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

不能获取元素本身

一般情况下不能从布隆过滤器中删除元素

如果采用计数方式删除，可能会存在计数回绕问题

哈希原理、模拟封装unordered系列关联式容器及其应用

目录