哈希结构的实现

unordered系列关联式容器

哈希的简介

哈希表闭散列实现

哈希表开散列实现

用哈希表来封装map和set

位图

布隆过滤器与哈希切割

全部代码

unordered系列关联式容器

unordered系列关联式容器有四种，这里主要对unordered_map和unordered_set这两种容器进行介绍

unordered_map

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value

在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序

unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低

unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value

unordered_set

unordered_set和unordered_map在性质上差不多，因为底层结构是一致的，都是哈希结构，区别在与，unordered_set不支持[]，因为它存储的是key与value相同，所以无需支持[]

哈希的简介

概念

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

哈希函数有多种，这里采用除留余数法

哈希冲突

比如14和4取模后都是4，而4对应的位置只能存储一个数字，那么就出现了哈希冲突，而解决哈希冲突的常见两种方法有闭散列和开散列

哈希表闭散列实现

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

寻找下一空位置有线性探测和二次探测两种

线性探测

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

二次探测

从发生冲突的位置开始，跨越探测，直到寻找到下一个空位置为止

index是哈希表的下标

首先因为有闭散列和开散列两种，所以采用命名空间的形式来防止命名冲突

然后定义一个枚举类型，用来判断该下标的空间的状态，是存在数据，还是删除过数据，或者没有数据，便于插入，删除，及查找数据

封装节点，开始必然为每个下标所在的空间必然为空状态，所以初始化为空状态

因为要是除留取余法，必然要是整数，所以还需要借助仿函数来实现

内置类型

string类型

string类型转整形，可以将字符串的每个字母的ASCII码值加起来，但要是只是顺序不同，那总数也会相同，出现哈希冲突，为了尽量减少哈希冲突，就有了下图的方法，其中31是累乘因子

string类型有下列两种写法，任选其一即可

对于其它自定义类型，比如日期，则按照特定方式取整即可

哈希表同样采用模板的形式实现，另外私有成员有中的_n是有效数据个数，便于后续插入数据扩容使用

查找数据

如果表为空，则直接返回nullptr即可

首先用待查找的key模表的长度取模作为待查找的初始下标，然后一直往后查找，同时往后走时，最后别忘了再取模一次，因为可能会存在初始下标空间的前面空间，找不到时，则直接返回nullptr

删除数据

首先先查找数据，找到数据了有效数据就减少一个，然后将那个节点的状态置为删除状态，删除成功返回true即可，没找到就表示删除失败，返回false

插入数据

首先先查找数据，如果存在，就表示待插入的数据已经有了，所以无需再插入，返回false即可

根据有效数据个数，得到负载因子，如果负载因子大于等于0.7则表示需要扩容了，初始没有空间时，也一样需要扩容

负载因子越小，冲突概率越低，效率越高，空间浪费越多

负载因子越大，冲突概率越高，效率越低，空间浪费越少

如果是初始时则开10个空间，其它情况则直接开原来的2倍空间

创建一个新表，开辟新空间大小的空间，再将其数据拷贝到新表，然后将新表对象中的vector成员与this对象中的vector成员交换即可

如果不需要开辟新空间

则先将key取模，找到对应的下标，如果有空间，则直接插入数据，没有，则继续往后面找，与find()类似，最后有效数据+1，返回true即可

闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

哈希表开散列实现

概念

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

封装节点，其实就是单链表的节点封装

私有成员与闭散列一致，同时，还是采用除留去余法，所以会用到仿函数，与上面闭散列一致

查找数据

如果哈希表为空，则直接返回nullptr

找到待查找的数据节点的下标，以及声明一个局部变量来保存这条链的头节点

从头开始往后找，找到了返回节点地址，没找到返回nullptr

删除数据

如果哈希表为空，返回false，表示删除失败

找到待删除数据节点的那条链的头节点

如果找到了，则分为两种情况，如果就是头节点，那就直接头删，否则就中间删除

如果没找到，则继续往后面找，找不到则返回false，表示删除失败

插入数据

首先先查找数据，如果存在，就表示待插入的数据已经有了，所以无需再插入，返回false即可

如果负载因子等于1时，则需要扩容，初始开空间时开10个空间，其余情况开原来的2倍空间

然后将原表的数据按头插拷贝到新表，将原表每条链的表头置空，最后再交换this对象的vector成员与新表的vector成员即可

如果不需要扩容，则直接头插，然后将有效数据个数+1，再返回true即可

为了减少哈希冲突，每次扩容后的空间大小都为素数

用哈希表来封装map和set

改善哈希表

因为既要封装map，又要封装set，所以将数据类型从pair类型变为了T类型

迭代器

因为会用到哈希表，所以提前声明一下

因为要封装map和set，所以多加了一个模板参数KeyOfT，采用了仿函数

因为map和set存储的数据不同，一个是pair<key,value>，一个是key所以对*和对->都要重载

判断相不相等，比较的是节点的地址相不相等

重载++运算符

如果这条链上还有节点，即没有遇到nullptr，则直接往后走即可

如果为nullptr，则从哈希表的下一个元素开始找，比如下图，走完11后，则继续往后面走，下一个元素表头为空，所以就走到了13，不为nullptr，则跳出循环

如果是循环自动结束的，即走完整个哈希表了，则直接置nullptr即可

如果是break出来的，则直接返回到那个节点，比如上述所说的13

拷贝构造

别忘了写一个默认构造函数，因为有了拷贝构造之后，编译器不会默认生成了

这里采用的是头插法，所以顺序会有变化

重载赋值运算符

将实参传给形参时会有一次拷贝构造，所以只需将this对象的两个成员与形参的交换即可

析构函数

从哈希表第一个元素开始销毁节点，直到走完哈希表结束

初始节点

如果哈希表第一个元素的头节点不为nullptr，则它就是初始节点，否则直接返回nullptr的迭代器

结尾节点，即nullptr

重载[]运算符

[]可查找value，也可修改或插入

位图

位图的作用：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在，比如在一堆数据中找5在不在，数据很多时，可以开辟整形最大值那么大的以bit为单位的空间，然后一个整数对应一个比特位，如果5对应的比特位是1，那就在这堆数据中，是0就不在

1byte=8bit，所以开空间数如下图

将某个bit位置为1

将某个bit位置为0

检查某个bit位是否为1

0为假，非0为真

位图：节省空间，效率高，但只能处理整数

布隆过滤器与哈希切割

概念

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

作用：用来解决字符串，自定义类型对象在不在的问题

如果采用将字符串转整数，即将字符串的各个字符加起来取模作为下标，那就可能会存在哈希冲突，比如下图中eat和ate

这种方式，判断不在是准确的，比如eat和ate那个位置的比特位为0，则eat肯定不在，只是判断在会存在误判

解决方式

将一个元素用多个哈希函数映射到一个位图中，比如ate，只要三个种有一个bit位为0，则就表示ate不在，降低了误判率

这里以哈希函数中三个不同的哈希函数为例模板参数


//hashTable-副本
#pragma once
#include<vector>
 
template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
 
//特化
template<>
struct Hash< string >
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
 
namespace CloseHash
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};
 
	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};
 
	struct HashStr
	{
		size_t operator()(const string& s)
		{
			//BKDR
			size_t value = 0;
			for (auto ch : s)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}
	};
 
	template<class K,class V,class HashFunc = Hash<K>>
	class HashTable
	{
	public:
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				--_n;
				ret->_status = DELETE;
				return true;
			}
		}
 
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
 
			HashFunc hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start;
			//线性探测 or 二次探测
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
 
				++i;
				//index = start + i*i;
				index = start + i;
 
				index %= _tables.size();
			}
 
			return nullptr;
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
 
			//负载因子到0.7，就扩容
			//负载因子越小，冲突概率越低，效率越高，空间浪费越多
			//负载因子越大，冲突概率越高，效率越低，空间浪费越少
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//扩容
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//vector<HashData<K,V>> newTables;
				//newTables.resize(newSize);
				//遍历原表，把原表中的数据，重新按newSize映射到新表
				//for(size_t i = 0;i < _tables.size();++i)
				//{
					//
				//}
				//_tables.swap(newTables);
				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
				    }
				}
 
				_tables.swap(newHT._tables);
			}
 
			HashFunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start;
			//线性探测 or 二次探测
			while (_tables[index]._status == EXIST)
			{
				++i;
				//index = start + i * i;
				index = start + i;
 
				index %= _tables.size();
			}
 
			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
 
			return true;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//有效数据个数
	};
 
	void TestHashTable1()
	{
		//HashTable<int,int,Hash<int>> ht;
		HashTable<int, int> ht;
 
		int a[] = { 2,12,22,32,42,52,62 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
 
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(-1, -1));
		ht.Insert(make_pair(-999, -999));
 
		Hash<int> hs;
		cout << hs(9) << endl;
		cout << hs(-9) << endl;
 
		cout << ht.Find(12) << endl;
		ht.Erase(12);
		cout << ht.Find(12) << endl;
	}
 
	struct Date
	{
 
	};
 
	struct HashDate
	{
		size_t operator()(const Date& d)
		{
			//...
		}
	};
 
	void TestHashTable2()
	{
		HashStr hs;
		cout << hs("sort") << endl;
		cout << hs("insert") << endl;
		cout << hs("eat") << endl;
		cout << hs("ate") << endl;
		cout << hs("abcd") << endl;
		cout << hs("aadd") << endl;
 
		HashTable<string, string> ht;
		ht.Insert(make_pair("sort", "排序"));
		ht.Insert(make_pair("string", "字符串"));
 
		//当key是一个定义类型时，需要配置一个仿函数，将key转成整形
		HashTable<Date, string, HashDate> htds;
	}
}
 
namespace LinkHash
{
	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 = Hash<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
 
		bool Erase(const K& key)
		{
			if (_tables.empty())
			{
				return false;
			}
 
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) //头删
					{
						_tables[index] = cur->_next;
					}
					else //中间删除
					{
						prev->_next = cur->_next;
					}
 
					--_n;
 
					delete cur;
 
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
 
			return false;
		}
 
		Node* Find(const K& key)
		{
			if (_tables.empty())
			{
				return nullptr;
			}
 
			HashFunc 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)
		{
			Node* ret = Find(kv.first);
			if (ret)
				return false;
 
			HashFunc hf;
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//...
				vector<Node*> newTables;
				newTables.resize(newSize);
				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) % newTables.size();
						//头插
						cur->_next = newTables[index];
						newTables[index] = cur;
 
						cur = next;
					}
 
					_tables[i] = nullptr;
				}
 
				_tables.swap(newTables);
			}
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
 
			++_n;
			return true;
		}
 
	private:
		/*struct Data
		{
			forward_list<T> _list;
			set<T> _rbtree;
			size_t len;
		};
		vector<Data> _table;*/
		vector<Node*> _tables;
 
		size_t _n = 0;//有效数据的个数
	};
 
	void TestHashTable()
	{
		int a[] = { 4,24,14,7,37,27,57,67,34,14,54 };
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
 
		ht.Insert(make_pair(84, 84));
	}
};
 
//hashTable
#pragma once
#include<vector>
#include<string>
 
template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
 
//特化
template<>
struct Hash< string >
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
 
namespace CloseHash
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};
 
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};
 
	//struct HashStr
	//{
	//	size_t operator()(const string& s)
	//	{
	//		//BKDR
	//		size_t value = 0;
	//		for (auto ch : s)
	//		{
	//			value *= 31;
	//			value += ch;
	//		}
	//		return value;
	//	}
	//};
 
	template<class K, class V, class HashFunc = Hash<K>>
	class HashTable
	{
	public:
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				--_n;
				ret->_status = DELETE;
				return true;
			}
		}
 
		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}
 
			HashFunc hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start;
			//线性探测 or 二次探测
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
 
				++i;
				//index = start + i*i;
				index = start + i;
 
				index %= _tables.size();
			}
 
			return nullptr;
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			HashData<K, V>* ret = Find(kv.first);
			if (ret)
			{
				return false;
			}
 
			//负载因子到0.7，就扩容
			//负载因子越小，冲突概率越低，效率越高，空间浪费越多
			//负载因子越大，冲突概率越高，效率越低，空间浪费越少
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//扩容
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//vector<HashData<K,V>> newTables;
				//newTables.resize(newSize);
				//遍历原表，把原表中的数据，重新按newSize映射到新表
				//for(size_t i = 0;i < _tables.size();++i)
				//{
					//
				//}
				//_tables.swap(newTables);
				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
 
				_tables.swap(newHT._tables);
			}
 
			HashFunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start;
			//线性探测 or 二次探测
			while (_tables[index]._status == EXIST)
			{
				++i;
				//index = start + i * i;
				index = start + i;
 
				index %= _tables.size();
			}
 
			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;
 
			return true;
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//有效数据个数
	};
 
	void TestHashTable1()
	{
		//HashTable<int,int,Hash<int>> ht;
		HashTable<int, int> ht;
 
		int a[] = { 2,12,22,32,42,52,62 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
 
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(-1, -1));
		ht.Insert(make_pair(-999, -999));
 
		Hash<int> hs;
		cout << hs(9) << endl;
		cout << hs(-9) << endl;
 
		cout << ht.Find(12) << endl;
		ht.Erase(12);
		cout << ht.Find(12) << endl;
	}
 
	struct Date
	{
 
	};
 
	struct HashDate
	{
		size_t operator()(const Date& d)
		{
			//...
		}
	};
 
	void TestHashTable2()
	{
		/*HashStr hs;
		cout << hs("sort") << endl;
		cout << hs("insert") << endl;
		cout << hs("eat") << endl;
		cout << hs("ate") << endl;
		cout << hs("abcd") << endl;
		cout << hs("aadd") << endl;*/
 
		HashTable<string, string> ht;
		ht.Insert(make_pair("sort", "排序"));
		ht.Insert(make_pair("string", "字符串"));
 
		//当key是一个定义类型时，需要配置一个仿函数，将key转成整形
		HashTable<Date, string, HashDate> htds;
	}
}
 
namespace LinkHash
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
 
		HashNode(const T& data) :_data(data), _next(nullptr)
		{}
	};
 
	template<class K, class T,class KeyOfT, class HashFunc>
	class HashTable;
 
	template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;
 
		Node* _node;
		HashTable<K, T, KeyOfT, HashFunc>* _pht;
 
		__HTIterator(Node* node,HashTable<K,T,KeyOfT,HashFunc>* pht):_node(node),_pht(pht)
		{}
 
		Ref operator*()
		{
			return _node->_data;
		}
 
		Ptr operator->()
		{
			return &_node->_data;
		}
 
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % _pht->_tables.size();
				++index;
				//找下一个不为空的值
				while (index < _pht->_tables.size())
				{
					if (_pht->_tables[index])
					{
						break;
					}
					else
					{
						++index;
					}
				}
 
				//表走完了，都没有找到下一个桶
				if (index == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[index];
				}
			}
			return *this;
		}
 
		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 HashFunc>
	class HashTable
	{
		typedef HashNode<T> Node;
		
		template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>
		friend struct __HTIterator;
		typedef HashTable<K, T, KeyOfT, HashFunc> self;
	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;
 
		HashTable()
		{}
		//显示指定编译器去生成默认构造函数
		//HashTable() = default;
 
		HashTable(const self& ht)
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); ++i)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
 
					cur = cur->_next;
				}
			}
		}
 
		//ht1 = ht2
		self& operator=(self copy)
		{
			swap(_n, copy._n);
			_tables.swap(copy._tables);
			return *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;
			}
		}
 
		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);
		}
 
		bool Erase(const K& key)
		{
			if (_tables.empty())
			{
				return false;
			}
 
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) //头删
					{
						_tables[index] = cur->_next;
					}
					else //中间删除
					{
						prev->_next = cur->_next;
					}
 
					--_n;
 
					delete cur;
 
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
 
			return false;
		}
 
		iterator Find(const K& key)
		{
			if (_tables.empty())
			{
				return end();
			}
 
			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				else
				{
					cur = cur->_next;
				}
			}
 
			return end();
		}
 
		size_t GetNextPrime(size_t num)
		{
			static const unsigned long __stl_prime_list[28] =
			{
				53,97,193,389,769,
				1543,3079,6151,12289,24593,
				49157,98317,196613,393241,786433,
				1572869,3145739,6291469,12582917,25165843,
				50331653,100663319,201326611,402653189,805306457,
				1610612741,3221225473,4294967291
			};
 
			for(size_t i = 0;i < 28;++i)
			{
				if (__stl_prime_list[i] > num)
				{
					return __stl_prime_list[i];
				}
			}
			return __stl_prime_list[27];
		}
 
		pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if (ret != end())
				return make_pair(ret,false);
 
			HashFunc hf;
 
			//负载因子 == 1时扩容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//...
				size_t newSize = GetNextPrime(_tables.size());
				/*if (newSize == _tables.size())
				{
					break;
				}*/
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
 
						size_t index = hf(kot(cur->_data)) % newTables.size();
						//头插
						cur->_next = newTables[index];
						newTables[index] = cur;
 
						cur = next;
					}
 
					_tables[i] = nullptr;
				}
 
				_tables.swap(newTables);
			}
			size_t index = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _tables[index];
			_tables[index] = newnode;
 
			++_n;
			return make_pair(iterator(newnode,this),false);
		}
 
	private:
		/*struct Data
		{
			forward_list<T> _list;
			set<T> _rbtree;
			size_t len;
		};
		vector<Data> _table;*/
		vector<Node*> _tables;
 
		size_t _n = 0;//有效数据的个数
	};
}
 
//unordered-map
#pragma once
#include"HashTable.h"
 
namespace bit
{
	template<class K,class V,class hash = Hash<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
 
		iterator end()
		{
			return _ht.end();
		}
 
		V& operator[](const K& key)
		{
			auto ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
 
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
 
	private:
		LinkHash::HashTable<K, pair<K,V>, MapKeyOfT, hash > _ht;
	};
 
	void test_unordered_map()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字符串"));
		dict.insert(make_pair("map", "地图、映射"));
		/*cout << dict["sort"] << endl;
		cout << dict["string"] << endl;
		cout << dict["map"] << endl;*/
 
		//dict["right"] = "右边";
 
		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
 
		unordered_map<string, string> copy(dict);
		for (auto& kv : copy)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
		cout << endl;
	}
}
 
//unordered-set
#pragma once
namespace bit
{
	template<class K,class hash = Hash<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, K, SetKeyOfT, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
 
		iterator end()
		{
			return _ht.end();
		}
 
		pair<iterator,bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		LinkHash::HashTable<K, K, SetKeyOfT, hash> _ht;
	};
 
	void test_unordered_set()
	{
		unordered_set<int> us;
		us.insert(4);
		us.insert(14);
		us.insert(34);
		us.insert(7);
		us.insert(24);
		us.insert(17);
		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
 
		unordered_set<int> uss(us);
		unordered_set<int>::iterator It = uss.begin();
		while (It != uss.end())
		{
			cout << *It << " ";
			++It;
		}
		cout << endl;
 
		/*unordered_set<string> uss;
		uss.insert("sort");
		uss.insert("hash");*/
 
		/*unordered_set<int> us;
		for (size_t i = 0; i < 100; ++i)
		{
			us.insert(i);
		}*/
	}
}
 
//bitSet
#pragma once
#include<vector>
 
namespace bit
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1, 0);
		}
 
		void set(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
 
			_bits[i] |= (1 << j);
		}
 
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
 
			_bits[i] &= (~(1 << j));
		}
 
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
 
			return _bits[i] & (1 << j);
		}
 
	private:
		std::vector<char> _bits;
		//std::vector<int> _bits;
	};
 
	void test_bitset()
	{
		bitset<100> bs;
		bs.set(5);
		bs.set(4);
		bs.set(10);
		bs.set(20);
 
		cout << bs.test(5) << endl;
		cout << bs.test(4) << endl;
		cout << bs.test(10) << endl;
		cout << bs.test(20) << endl;
		cout << bs.test(21) << endl;
		cout << bs.test(6) << endl << endl;
 
		bs.reset(20);
		bs.reset(10);
		bs.reset(5);
 
		cout << bs.test(5) << endl;
		cout << bs.test(4) << endl;
		cout << bs.test(10) << endl;
		cout << bs.test(20) << endl;
		cout << bs.test(21) << endl;
		cout << bs.test(6) << endl;
 
		//bitset<0xffffffff> bs;
		//bitset<-1> bs;
	}
}
 
template<size_t N>
class TwoBitSet
{
public:
	void Set(size_t x)
	{
		if (!_bs1.test(x) && !_bs2.test(x)) //00 -> 01
		{
			_bs2.set(x);
		}
		else if (!_bs1.test(x) && _bs2.test(x)) //01 -> 10
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		//10 表示已经出现2次或以上，不用处理
	}
 
	void PrintOnceNum()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (!_bs1.test(i) && _bs2.test(i)) // 01
			{
				cout << i << endl;
			}
		}
	}
private:
	bit::bitset<N> _bs1;
	bit::bitset<N> _bs2;
};
 
void TestTwoBitSet()
{
	int a[] = { 99,0,4,50,33,44,2,5,99,0,50,99,50,2 };
	TwoBitSet<100> bs;
	for (auto e : a)
	{
		bs.Set(e);
	}
	bs.PrintOnceNum();
}
 
void TestFindIntersection()
{
	int a1[] = { 5,30,1,99,10 };
	int a2[] = { 8,10,11,9,30,10,30 };
}
 
//BloomFilter
#pragma once
 
#include<bitset>
#include<string>
#include<time.h>
 
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 3;
			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;
    }
};
 
template<size_t N,
size_t X = 8,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
    void Set(const K& key)
    {
        size_t len = X * N;
        size_t index1 = HashFunc1()(key) % len;
        size_t index2 = HashFunc2()(key) % len;
        size_t index3 = HashFunc3()(key) % len;
        cout << index1 << endl;
        cout << index2 << endl;
        cout << index3 << endl << endl;
 
        _bs.set(index1);
        _bs.set(index2);
        _bs.set(index3);
    }
 
    bool Test(const K& key)
    {
        size_t len = X * N;
        size_t index1 = HashFunc1()(key) % len;
        if (_bs.test(index1) == false)
            return false;
 
        size_t index2 = HashFunc2()(key) % len;
        if (_bs.test(index2) == false)
            return false;
 
        size_t index3 = HashFunc3()(key) % len;
        if (_bs.test(index3) == false)
            return false;
 
        return true;  //存在误判的
    }
 
    //不支持删除，删除可能会影响其它值。
    void Reset(const K& key);
private:
    bitset<X* N> _bs;
};
 
void TestBloomFilter1()
{
    BloomFilter<100> bm;
    bm.Set("sort");
    bm.Set("left");
    bm.Set("right");
    bm.Set("eat");
    bm.Set("ate");
    bm.Set("https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");
 
}
 
void TestBloomFilter2()
{
    BloomFilter<100> bf;
    bf.Set("张三");
    bf.Set("李四");
    bf.Set("牛魔王");
    bf.Set("红孩儿");
    bf.Set("eat");
 
    cout << bf.Test("张三") << endl;
    cout << bf.Test("李四") << endl;
    cout << bf.Test("牛魔王") << endl;
    cout << bf.Test("红孩儿") << endl;
    cout << bf.Test("孙悟空") << endl;
    cout << bf.Test("二郎神") << endl;
    cout << bf.Test("猪八戒") << endl;
    cout << bf.Test("ate") << endl;
 
    //BloomFilter<100> bf;
 
    srand(time(0));
    size_t N = 100;
    std::vector<std::string> v1;
    for (size_t i = 0; i < N; ++i)
    {
        std::string ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
        ur1 += std::to_string(1234 + i);
        v1.push_back(ur1);
    }
 
    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 ur1 = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
        ur1 += std::to_string(6789 + i);
        v2.push_back(ur1);
    }
 
    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)
    {
        string ur1 = "zhihu.com";
        //std::string ur1 = "https://mail.qq.com/cgi-bin/frame_html?sid=0QvJ6bvfhn3EC1Iw&r=5976c09322eae24513a5ff315428cd86&lang=zh";
        //std::string ur1 = "https://www.sogou.com/tx?query=%E5%88%98%E5%BC%BA%E4%B8%9C%E4%BA%8B%E4%BB%B6%20%E5%A5%B3%E6%96%B9%E7%A7%B0%E8%87%AA%E6%84%BF%E5%8F%91%E7%94%9F%E5%85%B3%E7%B3%BB&hdq=sogou-site-706608cfdbcc1886&ekv=3&ie=utf8&";
        //std::string ur1 = "https://www.sogou.com/sogou?ie=utf8&pid=sogou-wsse-af64b05ee108fa0c&query=%E4%BA%BA%E6%B0%91%E7%BD%91%3A%E5%BE%B7%E4%BA%91%E7%A4%BE%E8%AF%A5%E8%87%AA%E6%88%91%E6%A3%80%E8%A7%86%E4%BA%86";
        ur1 += std::to_string(rand());
        v3.push_back(ur1);
    }
 
    size_t n3 = 0;
    for (auto& str : v3)
    {
        if (bf.Test(str))
        {
            ++n3;
        }
    }
    cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

设置为1

首先先用三个哈希函数算出对应的下标

再复用前面的位图的函数将其bit位设为1即可

注意:当len越大时，即空间开的越大时，误判率会越低

检查在不在

三个bit位，只要有一个bit位为0，则表示不在

注意:布隆过滤器不支持删除，因为支持删除会消耗很多空间，而且会存在误删，比如上图中的ate和eat，如果删除ate，那就会改变eat中的其中一个bit位

哈希切割

例:给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法,这里就要用到哈希切割

注意:如果Ai和Bi都太大，可以考虑换个哈希函数，再切割一次

全部代码

相关阅读:
自然之州阿肯色及温泉国家公园
 如果你是一个 Java 面试官，你会问哪些问题？
怎样才能让百度搜索到自己的博客？--九五小庞
 Mybatis SQL构建器
 jdk1.8中list按对象的某个属性分组
 每日练习------随机产生一个1-100之间的整数，看能几次猜中。要求：猜的次数不能超过7次，每次猜完之后都要提示“大了”或者“小了”。
云端炼丹,算力白嫖,基于云端GPU(Colab)使用So-vits库制作AI特朗普演唱《国际歌》
原码，反码，补码以及计算
 Flutter布局组件：水平/垂直组件、叠加布局组件、流式布局组件
 取证之查看本机保存的WiFi密码
原文地址：https://blog.csdn.net/weixin_58867976/article/details/125464703