C++进阶篇5-哈希

一、unordered系列关联式容器

二、底层结构

1、哈希的概念

无论是顺序结构还是平衡树，只要数据量变大，就不可避免的会增加查找的时间，即增加了比较关键字的次数，那么我们能不能通过一次对比就直接找到元素呢？即通过所给的关键字直接找到想要的元素

最理想的方式：直接在key-value之间建立某种函数映射关系，使得每个key只对应一个value，那么我们就能根据所给的key一步找到value

当向该结构中

• 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素 ：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

但是这个哈希表结构是存在一定问题的，比如当我们再往里面插入一个24，就会发现下标为4的位置已经有值了，这个现象叫做哈希冲突或哈希碰撞，即不同关键字通过相同哈希函数计算出相同的哈希地址

2、哈希函数

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

哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

常见哈希函数

1. 直接定址法--(常用)

• 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
• 优点：简单、均匀
• 缺点：需要事先知道关键字的分布情况
• 使用场景：适合查找比较小且连续的情况

2. 除留余数法--(常用)

• 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法--(了解)

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

4. 折叠法--(了解)

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

5. 随机数法--(了解)

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

6. 数学分析法--(了解)

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

3、哈希冲突的解决：闭散列和开散列

闭散列

删除：

//该仿函数作用将各种其他类型的值转化成整形
template<class K>
struct HashFun
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
 
template<>
struct HashFun 
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto& e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
 
namespace zxws 
{
	enum Status {
		EMPTY, 
		DELETED,
		EXIST
	};
 
	template<class K, class V>
	struct HashData {
		pair_kv;
		Status _st = EMPTY;
		HashData() = default;
		HashData(const pair& kv)
			:_st(EXIST)
			, _kv(kv)
		{}
	};
 
	template <class K, class V, class Hash = HashFun>
	class HashTable {
	public:
		HashTable() :_table(10) {}
 
		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _table.size() == 7)//设置的负荷因子为0.7（具体是什么，下面会讲），if条件这样写是为了方便计算
			{
				size_t newSize = _table.size() * 2;
 
				HashTablenewHT;
				newHT._table.resize(newSize);
				for (int i = 0; i < _table.size(); i++)
				{
					if (_table[i]._st == EXIST)
					{
						newHT.Insert(_table[i]._kv);//这里直接复用Insert函数，不是递归，本质是两个对象调用该函数
					}
				}
				_table.swap(newHT._table);
			}
 
			Hash hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._st == EXIST)
			{
				hashi++;
				hashi %= _table.size();
			}
			_table[hashi]._kv = kv;
			_table[hashi]._st = EXIST;
			_n++;
			return true;
		}
 
		HashData* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._st != EMPTY)
			{
				if (_table[hashi]._st == EXIST
					&& _table[hashi]._kv.first == key)
				{
					return &_table[hashi];
				}
				hashi++;
				hashi %= _table.size();
			}
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			HashData* ret = Find(key);
			if (ret->_st == EXIST)
			{
				ret->_st = DELETED;
				_n--;
				return true;
			}
			return false;
		}
 
		void Print()//测试用的函数
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._st == EXIST)
					cout << i << "->" << _table[i]._kv.first << endl;
				else if (_table[i]._st == DELETED)
					cout << i << "->" << "D" << endl;
				else
					cout << i << "->" << endl;
			}
		}
	private:
		vector>_table;
		size_t _n = 0;
	};
}

2.二次探测：即以1^2，2^2，3^2……往后找空位，防止出现堆积再一起的情况 

开散列

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

开散列的实现

namespace zxws
{
	template<class K,class V>
	struct HashNode
	{
		HashNode* next;
		pair_kv;
		HashNode(const pair&kv)
			:next(nullptr)
			,_kv(kv)
		{}
	};
 
	template<class K, class V,class Hash=HashFun>//HashFun这个函数在闭散列的实现代码的最开始
	class HashTable
	{
		typedef HashNode Node;
	public:
		HashTable() 
		{
			_table.resize(10); 
		}
 
		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}
 
		bool Insert(const pair& kv)
		{
			if (Find(kv.first))
				return false;
			Hash hf;
 
			if (_n == _table.size())//增容的条件在下面会讲
			{
				//复用之前的结点
				size_t sz = _table.size()*2;
				vectornewTable;
				newTable.resize(sz);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->next;
						size_t hashi = hf(cur->_kv.first) % sz;//需要重新计算哈希地址
						cur->next = newTable[hashi];
						newTable[hashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}
 
 
			size_t hashi = hf(kv.first) % _table.size();
			Node* newnode = new Node(kv);
			newnode->next = _table[hashi];
			_table[hashi] = newnode;
			++_n;
		}
 
		Node* Find(const K& key)
		{
			Hash hf;
 
			size_t hashi = hf(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)
		{
			Hash hf;
 
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
						_table[hashi] = cur->next;
					else
						prev->next = cur->next;
					delete cur;
					--_n;
					return true;
				}
				cur = cur->next;
			}
			return false;
		}
	private:
		vector_table;
		size_t _n;//有效元素个数
	};
}

开散列和闭散列相比

• 优点1：不会出现不同的关键字哈希之后的地址相互影响的情况，就比如找24，闭散列要找5次，开散列只要2次，即查找速率加快
• 优点2：链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

三、unordered_set和unordered_map的模拟实现(与STL中的实现有所差异)

1.底层结构HashTable

template<class K>
struct HashFun 
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
 
template<>
struct HashFun
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto& e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};
 
namespace zxws
{
    //函数模板的前置声明
	template<class K, class T, class Hash, class KeyOfData>
	class HashBucket;
 
	template <class T>
	struct HashNode 
	{
		HashNode* next;
		T _data;
 
		HashNode(const T& data)
			:next(nullptr)
			, _data(data)
		{}
	};
 
	template<class K,class T, class Ref, class Ptr, class Hash, class KeyOfData>
	struct Iterator 
	{
		typedef Iterator Self;
 
		HashNode* _cur;
		size_t _hashi;
		const HashBucket* _phb;//
 
		Iterator(HashNode*cur, size_t hashi, const HashBucket* phb)//
			:_cur(cur)
			,_hashi(hashi)
			,_phb(phb)
		{}
 
		Iterator(const Self& t)
			:_cur(t._cur)
			, _hashi(t._hashi)
			, _phb(t._phb)
		{}
 
		Self& operator++()
		{
			if (_cur->next)
			{
				_cur = _cur->next;
				return *this;
			}				
			else
			{
				_hashi++;
				while (_hashi<_phb->_ht.size())//
				{
					if (_phb->_ht[_hashi])
					{
						_cur = _phb->_ht[_hashi];
						return *this;
					}
					_hashi++;
				}
				_cur = nullptr;//
				//_hashi = -1;
				return *this;
			}
		}
 
		bool operator==(const Self& t) const
		{
			return _cur == t._cur;
		}
 
		bool operator!=(const Self& t) const
		{
			return _cur != t._cur;
		}
 
		Self operator++(int)
		{
			Iterator it(*this);
			this->operator++();
			return it;
		}
 
		Ref operator*()
		{
			return _cur->_data;
		}
 
		Ptr operator->()
		{
			return &_cur->_data;
		}
	};
 
 
 
	template<class K,class T,class Hash,class KeyOfData>
	class HashBucket {
		//类模板的友元声明
		template<class K, class T,class Ref,class Ptr,class Hash, class KeyOfData>
		friend struct Iterator;	
	public:
		typedef HashNode Node;
 
		
		typedef Iterator iterator;
		typedef Iteratorconst T&, const T*, Hash, KeyOfData> const_iterator;
		
		
		HashBucket():_ht(10) {}
 
		iterator begin()
		{
			for (size_t i = 0; i < _ht.size(); i++)
			{
				if (_ht[i])
					return iterator(_ht[i], i, this);
			}
			return end();
		}
 
		iterator end()
		{
			return iterator(nullptr, -1, this);
		}
 
		const_iterator begin() const
		{
			for (size_t i = 0; i < _ht.size(); i++)
			{
				if (_ht[i])
					return const_iterator(_ht[i], i, this);
			}
			return end();
		}
 
		const_iterator end() const
		{
			return const_iterator(nullptr, -1, this);
		}
 
 
		void swap(const HashBucket& tmp)
		{
			std::swap(_ht, tmp._ht);
			std::swap(_n, tmp._n);
		}
 
		pairbool> insert(const T& data)
		{
			Hash hf;
			KeyOfData kod;
			auto ret = find(kod(data));
			if (ret!=end())
				return make_pair(ret,false);
			if (_n == _ht.size())
			{
				vectorv(2 * _ht.size());
				for (size_t i = 0; i < _ht.size(); i++)
				{
					Node* cur = _ht[i];
					while (cur)
					{
						Node* next = cur->next;
						size_t hashi = hf(kod(cur->_data)) % v.size();
						cur->next = v[hashi];
						v[hashi] = cur;
						cur = next;
					}
					_ht[i] = nullptr;
				}
				_ht.swap(v);
			}
			size_t hashi = hf(kod(data)) % _ht.size();
			Node* newnode = new Node(data);
			newnode->next = _ht[hashi];
			_ht[hashi] = newnode;
			_n++;
			return make_pair(iterator(newnode, hashi, this), false);
		}
 
		iterator find(const K& key)
		{
			Hash hf;
			KeyOfData kod;
 
			size_t hashi = hf(key) % _ht.size();
			Node* cur = _ht[hashi];
			while (cur)
			{
				if (kod(cur->_data) == key)
					return iterator(cur, hashi, this);
				cur = cur->next;
			}
			return end();
		}
 
		bool erase(const K& key)
		{
			Hash hf;
			KeyOfData kod;
 
			size_t hashi = hf(key) % _ht.size();
			Node* cur = _ht[hashi];
			Node* pre = nullptr;
			while (cur)
			{
				if (kod(cur->_data) == key)
				{
					if (pre == nullptr)
					{
						_ht[hashi] = cur->next;
					}
					else
					{
						pre->next = cur->next;
					}
					delete cur;
					_n--;
					return true;
				}
				pre = cur;
				cur = cur->next;
			}
			return false;
		}
 
		iterator erase(iterator pos)
		{
			if (pos == end())
				return pos;
			KeyOfData kod;
			Node* cur = pos._cur;
			++pos;
			erase(kod(cur->_data));
			return pos;
		}
 
		const_iterator erase(const_iterator pos)
		{
			if (pos._cur == nullptr)
				return pos;
			KeyOfData kod;
			Node* cur = pos._cur;
			++pos;
			erase(kod(cur->_data));
			return pos;
		}
 
 
		size_t size()
		{
			return _n;
		}
 
		bool empty()
		{
			return _n == 0;
		}
 
		size_t bucket_count()
		{
			size_t cnt = 0;
			for (size_t i = 0; i < _ht.size(); i++)
			{
				if (_ht[i])
					cnt++;
			}
			return cnt;
		}
 
		size_t bucket_size(const K& key)
		{
			Hash hf;
			size_t cnt = 0;
			size_t hashi = hf(key);
			for (Node* cur = _ht[hashi]; cur; cur = cur->next)
				cnt++;
			return cnt;
		}
	private:
		vector _ht;
		size_t _n = 0;
	};
}

 2.unordered_set的封装

namespace zxws
{
	template <class K,class Hash = HashFun>
	class unordered_set {
		struct KeyOfData 
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
 
		typedef typename HashBucket::const_iterator iterator;
		typedef typename HashBucket::const_iterator const_iterator;
 
		pairbool> insert(const K& data)
		{
			auto ret=_hb.insert(data);
			return make_pair(iterator(ret.first._cur, ret.first._hashi, ret.first._phb), ret.second);
		}
 
		iterator begin() const
		{
			return _hb.begin();
		}
 
		iterator end() const
		{
			return _hb.end();
		}
 
		iterator find(const K& key)
		{
			auto ret = _hb.find(key);
			return iterator(ret._cur, ret._hashi, ret._phb);
		}
 
		bool erase(const K& key)
		{
			return _hb.erase(key);
		}
 
		iterator erase(iterator pos)
		{
			return _hb.erase(pos);
		}
 
 
		size_t bucket_count()
		{
			return _hb.BucketCount();
		}
 
		size_t bucket_size(const K& key)
		{
			return _hb.BucketSize(key);
		}
 
		size_t size()const
		{
			return _hb.size();
		}
 
		bool empty()const
		{
			return _hb.empty();
		}
	private:
		HashBucket_hb;
	};
}

namespace zxws
{
	template <class K,class V,class Hash=HashFun>
	class unordered_map {
		struct KeyOfData {
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashBucketconst K, V>, Hash, KeyOfData>::iterator iterator;
		typedef typename HashBucketconst K, V>, Hash, KeyOfData>::const_iterator const_iterator;
		pairbool> insert(const pair& data)
		{
			return _hb.insert(data);
		}
 
		V& operator[](const K& key)
		{
			auto ret = _hb.insert(make_pair(key, V()));
			return ret.first->second;
		}
 
		iterator begin()
		{
			return _hb.begin();
		}
 
		iterator end()
		{
			return _hb.end();
		}
 
		const_iterator begin() const
		{
			return _hb.begin();
		}
 
		const_iterator end() const
		{
			return _hb.end();
		}
 
		iterator find(const K& key)
		{
			return _hb.find(key);
		}
 
		bool erase(const K& key)
		{
			return _hb.erase(key);
		}
 
		iterator erase(iterator pos)
		{
			return _hb.erase(pos);
		}
 
 
		size_t bucket_count() 
		{ 
			return _hb.BucketCount();
		}
 
		size_t bucket_size(const K& key) 
		{ 
			return _hb.BucketSize(key);
		}
 
		size_t size()const
		{
			return _hb.size(); 
		}
		
		bool empty()const 
		{
			return _hb.empty(); 
		}
	private:
		HashBucketconst K,V>,Hash, KeyOfData>_hb;
	};
}