C++ unordered_set、unordered_map哈希使用及其封装

2.2乘法散列法

3.1.3开放定址法代码实现

#include<iostream>
#include<vector>
using namespace std;


enum Stat
{
	Empty,
	Exist,
	Delete
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Stat _st;//哈希表里面每个位置的状态
};

template<class K>
struct HashFunc
{
	size_t operator()(const K& k)
	{
		return (size_t)k;
	}
};
template<>
struct HashFunc<string>
{
	size_t operator()(const string& k)
	{
		int hash0 = 0;
		for (auto ch : k)
		{
			hash0 *= 131;
			hash0 += ch;
		}
		return hash0;
	}
};
//插入的值可能是浮点数、负数、字符串，写一个仿函数将它们转为无符号整形
//对于字符串，将每个字符的ASCLL值相加得到对应的无符号整形数字
//但是相同字符组成的不同顺序排列的字符串就是一样的整形，会造成哈希冲突
//所以将每个每次加一个字符之后再乘素数131，保证每个字符串转换之后的独立
//这里需要特化
//对于自定义类型，自己写一个函数去转换为size_t类型的，这里看Data类型
template<class K,class V,class ToSize_t = HashFunc<K>>
class HashTable
{
public:
	HashTable()
		:_t(11)
		,_n(0)
	{}
	inline unsigned long __stl_next_prime(unsigned long n)//库中的素数表
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			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//几乎都是两倍
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first)) return false;//不支持冗余
		if (10 * _n / _t.size() > 7)//扩容
		{
			HashTable<K, V,ToSize_t> ht;
			ht._t.resize(__stl_next_prime(_t.size() + 1));//返回的是比传入大的一个素数
			for (auto data : _t)
			{
				if (data._st == Exist) 
					ht.Insert(data._kv);
			}
			_t.swap(ht._t);//交换比赋值效率高，不需要深拷贝，只是交换指针
		}
		int i = 1;
		size_t hash0 = ToSize_t()(kv.first) % _t.size();
		size_t hashi = hash0;
		while (_t[hashi]._st == Exist)//找到为空或者删除状态的位置进行插入
		{
			hashi = (hashi + i) % _t.size();
			i++;
		}
		_t[hashi]._kv = kv;
		_t[hashi]._st = Exist;
		++_n;
		return true;
	}
	HashData<K, V>* Find(const K& k)
	{
		int i = 1;
		size_t hash0 = ToSize_t()(k) % _t.size();
		size_t hashi = hash0;
		//若是有k，那么hash0对应的位置不会是Empty
		while (_t[hashi]._st != Empty)
		{
			//不为空可能是删除，删除的这个元素可能是k，所以不能直接用数据是否相等作为条件
			if (_t[hashi]._st == Exist && _t[hashi]._kv.first == k) return &_t[hashi];
			hashi = (hashi + i) % _t.size();
			i++;
		}
		return nullptr;
	}
	bool Erase(const K& k)
	{
		HashData<K, V>* ret = Find(k);//这里必须要用指针类型，否则ret只是一个和_t不相关的HashData
		//此时改变了状态也不会使得_t里面数据状态改变；使用指针解决这个问题
		if (ret) ret->_st = Delete;
		else return false;
	}
private:
	vector<HashData<K, V>> _t;
	size_t _n;//哈希表中实际数据个数
};

3.2.1链地址法代码实现

#include<iostream>
#include<vector>
using namespace std;


template<class K>
struct ToSize_t
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>//针对于浮点型的模板特化
struct ToSize_t<string>
{
	size_t operator()(const string& key)
	{
		int ret = 0;
		for (int i = 0; i < (int)key.size(); i++)
		{
			ret += key[i];
			ret *= 31;
		}
		return ret;
	}
};

template<class K,class V>
struct HashData
{
	HashData(const pair<K, V>& kv, HashData<K,V>* next = nullptr)
		:_kv(kv)
		,_next(next)
	{}
	pair<K, V> _kv;
	HashData<K, V>* _next;
};

template<class K,class V,class T = ToSize_t<K>>
class HashBucket
{
public:
	HashBucket()
		:_table(__stl_next_prime(0))
		//:_table(11)
		,_n(0)
	{}
	~HashBucket()
	{
		for (int i = 0; i < (int)_table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				_n--;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}
	//具有申请资源的，就要写析构和拷贝构造和赋值重载
	HashBucket(HashBucket<K, V, T>& ht)
	{
		int size = ht._table.size();
		_table.resize(size);
		for (int i = 0; i < size; i++)
		{
			Node* cur = ht._table[i];
			while (cur)
			{
				this->Insert(cur->_kv);
				cur = cur->_next;
			}
		}
	}
	//赋值重载
	HashBucket<K, V, T> operator=(HashBucket<K, V, T>& ht)
	{
		HashBucket<K, V, T> tmp = ht;//拷贝构造一个临时哈希桶
		this->_table.swap(tmp._table);
		this->_n = tmp._n;
		return *this;
	}
	typedef HashData<K, V> Node;
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
		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
		};

		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	bool Insert(const pair<K,V>& kv)
	{
		if (_n / _table.size() >= 1)//扩容
		{
//这里扩容不能和开放定址法一样
//原因：若是创建一个新的哈希表，并且遍历旧的哈希表并且重新向新的哈希表里面插入
//意味着在新的哈希表中要创建newnode，而旧的哈希表的vector里面在析构时不会销毁下面挂着的一些节点指针，
//这里选择创建一个顺序表，将原来哈希桶中的节点转移过来，节点指针还是一样的
			vector<Node*> newtable;
			newtable.resize(__stl_next_prime(_table.size() + 1));
			//newtable.resize(2*_table.size());

			for (int i = 0; i < (int)_table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;//记录旧表下一个节点指针，避免逻辑出错
					int hashi = T()(cur->_kv.first) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
			}
			_table.swap(newtable);
		}
		int hashi = T()(kv.first) % _table.size();
		//找到位置了头插进入
		Node* newnode = new Node(kv);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		_n++;
		return true;
	}
	Node* Find(const K& key)
	{
		int hashi = T()(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
				return cur;
			cur = cur->_next;
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		int hashi = T()(key) % _table.size();
		Node* prev = nullptr;
		Node* cur = _table[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				//分两种情况：可能删的是头部或者中间的
				if (prev == nullptr)//说明进来就是要删除的即头部
				{
					Node* next = cur->_next;
					delete cur;
					_table[hashi] = next;
				}
				else//说明prev已经更新过了，删除的是中间部分的
				{
					Node* next = cur->_next;
					prev->_next = next;
					delete cur;
				}
				_n--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}
private:
	vector<Node*> _table;
	size_t _n;
};

三、哈希封装

哈希封装底层是哈希桶，迭代器是单向的，并且实现迭代器的++时逻辑和map一块的也不一样；

先引入unordered_xxx的头文件

#pragma once
#include"HashBucket.h"

template<class K,class Hash = HashFun<K>>
class UnOrderedSet
{
	struct SetKoT
	{
		const K& operator()(const K& data)
		{
			return data;
		}
	};
public:
	typedef typename HashBucket<K, const K, SetKoT, Hash> :: Iterator iterator;//unordered_set的值不支持修改，因为这个值同时也是key
	typedef typename HashBucket<K, const K, SetKoT, Hash> :: ConstIterator const_iterator;

	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}
	const_iterator cbegin()const
	{
		return _ht.cBegin();
	}
	const_iterator cend()const
	{
		return _ht.cEnd();
	}
	pair<iterator,bool> insert(const K& data)
	{
		return _ht.Insert(data);
	}
	iterator find(const K& k)
	{
		return _ht.Find(k);
	}
	bool erase(const K& k)
	{
		return _ht.Erase(k);
	}
private:
	HashBucket<K, const K, SetKoT,Hash> _ht;
};

#pragma once
#include"HashBucket.h"

template<class K,class V,class Hash = HashFun<K>>
class UnOrderedMap
{
	struct MapKoT
	{
		const K& operator()(const pair<const K,V>& data)
		{
			return data.first;
		}
	};
public:
	typedef typename HashBucket<K, pair<const K, V>, MapKoT, Hash> ::Iterator iterator;
	typedef typename HashBucket<K, pair<const K, V>, MapKoT, Hash> ::ConstIterator const_iterator;

	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}
	const_iterator cbegin()const
	{
		return _ht.cBegin();
	}
	const_iterator cend()const
	{
		return _ht.cEnd();
	}
	pair<iterator,bool> insert(const pair<const K, V>& data)
	{
		return _ht.Insert(data);
	}
	iterator find(const K& k)
	{
		return _ht.Find(k);
	}
	bool erase(const K& k)
	{
		return _ht.Erase(k);
	}
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
		return ret.first->second;//return *(ret.first).second//*的优先级高于.
	}
private:
	HashBucket<K, pair<const K,V>, MapKoT,Hash> _ht;
};

这里封装的MapKoT和SetKoT是因为哈希表进行比较时比较键值key，所以这里传一个类，将数据里面的key拿出来；

这里unordered_set模板参数传两个K是为了迎合unordered_map；

Hash这个类是将key转为整形方便取模放入哈希桶；

封装的这两个类底层都是一个哈希桶，即_ht；

pair<>只是类型不是一个值，要是要返回一个pair<>类型的值，可以使用{}进行隐式类型转换或者调用make_pair()函数。

#pragma once
#include<iostream>
#include<vector>
using namespace std;

//HashFun将K转为无符号整形方便取模
template<class K>
struct HashFun
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>//针对于浮点型的模板特化
struct HashFun <string>
{
	size_t operator()(const string& key)
	{
		int ret = 0;
		for (int i = 0; i < (int)key.size(); i++)
		{
			ret += key[i];
			ret *= 31;
		}
		return ret;
	}
};
/
//哈希桶的数据
//这里是T因为HashData类里面存了真实数据，T可以是set的v也可以是map的pair
template<class T>
struct HashData
{
	HashData(const T& data, HashData<T>* next = nullptr)
		:_data(data)
		, _next(next)
	{}
	T _data;
	HashData<T>* _next;
};
//
template<class K, class T, class KoT,class Hash>
class HashBucket;//哈希桶类模板前置声明，因为在迭代器实现中使用到了哈希桶类
                 //而编译器是只会向上查找有无声明定义的
//迭代器实现
template<class K, class T,class Ref,class Ptr, class KoT, class Hash = HashFun<K>>
struct HTIterator
{
	typedef HashData<T> Node;
	typedef HashBucket<K, T, KoT, Hash> HT;
	typedef HTIterator<K, T, Ref, Ptr, KoT, Hash> Self;

	//迭代器构造函数
	HTIterator(Node* node = nullptr , const HT* ht=nullptr)
		:_node(node)
		, _ht(ht)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return !(_node == it._node);
	}
	Self& operator++()
	{
		if (_node->_next)//_node下一个有挂着的节点
			_node = _node->_next;
		else
		{
			size_t hashi = Hash()(KoT()(_node->_data)) % _ht->_table.size();
			hashi++;
			while (hashi < _ht->_table.size())
			{
				if (_ht->_table[hashi])
				{
					_node = _ht->_table[hashi];
					break;//找到了下一条不为空的链表的首节点
				}
				hashi++;
			}
			if (hashi == _ht->_table.size())//可能越过哈希桶的大小
				_node = nullptr;
		}
		return *this;
	}

	Node* _node;
	const HT* _ht;

};
//
//哈希桶实现
template<class K, class T, class KoT,class Hash >
class HashBucket
{
	template<class K, class T, class Ref, class Ptr, class KoT, class Hash >
	friend struct HTIterator;//迭代器中需要使用_table私有成员，所以将迭代器给成友元类
public:
	typedef HTIterator<K, T, T&, T*, KoT, Hash> Iterator;
	typedef HTIterator<K, T, const T&,const T*, KoT, Hash> ConstIterator;

	Iterator Begin()
	{
		if (_n == 0) return End();
		//有数据就找第一个不为空的桶的首节点
		size_t hashi = 0;
		while (_table[hashi] == nullptr)
		{
			hashi++;
		}
		return Iterator( _table[hashi],this );
	}
	Iterator End()
	{
		return Iterator( nullptr,this );
	}
	ConstIterator cBegin()const
	{
		if (_n == 0) return cEnd();
		//有数据就找第一个不为空的桶的首节点
		size_t hashi = 0;
		while (_table[hashi] == nullptr)
		{
			hashi++;
		}
		return ConstIterator( _table[hashi],this );
	}
	ConstIterator cEnd()const
	{
		return ConstIterator( nullptr,this );
	}

	HashBucket()
		:_table(__stl_next_prime(0))
		, _n(0)
	{}
	~HashBucket()
	{
		for (int i = 0; i < (int)_table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				_n--;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}
	//具有申请资源的，就要写析构和拷贝构造和赋值重载
	HashBucket(HashBucket<K, T, KoT, Hash>& ht)
	{
		int size = ht._table.size();
		_table.resize(size);
		for (int i = 0; i < size; i++)
		{
			Node* cur = ht._table[i];
			while (cur)
			{
				this->Insert(cur->_data);
				cur = cur->_next;
			}
		}
	}
	//赋值重载
	HashBucket<K, T, KoT,Hash> operator=(HashBucket<K, T, KoT, Hash>& ht)
	{
		HashBucket<K, T, KoT,Hash> tmp = ht;//拷贝构造一个临时哈希桶
		this->_table.swap(tmp._table);
		this->_n = tmp._n;
		return *this;
	}
	typedef HashData<T> Node;
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
		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
		};

		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	pair<Iterator,bool> Insert(const T& data)
	{
		Iterator it = Find(KoT()(data));
		if (it!= End())//不支持冗余值
			return make_pair(it, false);
		if (_n / _table.size() >= 1)//扩容
		{
			//这里扩容不能和开放定址法一样
			//原因：若是创建一个新的哈希表，并且遍历旧的哈希表并且重新向新的哈希表里面插入
			//意味着在新的哈希表中要创建newnode，而旧的哈希表的vector里面在析构时不会销毁下面挂着的一些节点指针
			vector<Node*> newtable;
			newtable.resize(__stl_next_prime(_table.size() + 1));
			//newtable.resize(2*_table.size());

			for (int i = 0; i < (int)_table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;//记录旧表下一个节点指针，避免逻辑出错
					size_t hashi = Hash()(KoT()(cur->_data)) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
			}
			_table.swap(newtable);
		}
		size_t hashi = Hash()(KoT()(data)) % _table.size();
		//找到位置了头插进入
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		_n++;
		return make_pair(Iterator(newnode,this),true);
	}
	Iterator Find(const K& key)
	{
		size_t hashi = Hash()(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (KoT()(cur->_data) == key)
				return Iterator(cur, this);
			cur = cur->_next;
		}
		return End();
	}
	bool Erase(const K& key)
	{
		int hashi = Hash()(key) % _table.size();
		Node* prev = nullptr;
		Node* cur = _table[hashi];
		while (cur)
		{
			if (KoT()(cur->_data) == key)
			{
				//分两种情况：可能删的是头部或者中间的
				if (prev == nullptr)//说明进来就是要删除的即头部
				{
					Node* next = cur->_next;
					delete cur;
					_table[hashi] = next;
				}
				else//说明prev已经更新过了，删除的是中间部分的
				{
					Node* next = cur->_next;
					prev->_next = next;
					delete cur;
				}
				_n--;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}
private:
	vector<Node*> _table;
	size_t _n;
};