C++进阶篇5-哈希

一、unordered系列关联式容器

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

这里就简单介绍一下unordered_map的常用函数，其他的用法类似，就不多介绍了

bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数
begin()	返回unordered_map第一个元素的迭代器
end()	返回unordered_map最后一个元素的迭代器
operator[]	返回与key对应的value，没有一个默认值，该函数只有unordered_map有
iterator find(const K&key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数
insert	增
erase	删
void clear()	清空有效元素

二、底层结构

1、哈希的概念

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

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

当向该结构中

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

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称

为哈希表(Hash Table)(或者称散列表)

一般用取模运算将数组下标和关键字建立联系，如下

但是这个哈希表结构是存在一定问题的，比如当我们再往里面插入一个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、哈希冲突的解决：闭散列和开散列

闭散列

也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有

空位置，那么可以把key存放到冲突位置中的"下一个"空位置中去

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

插入：

就拿上面的图来说，如果再向里面加24，由于该位置已经被占用，就只能一个一个往后走，看有没有空位置，最后放在下标为8的位置

删除：

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

线性探测的实现---里面有很多的细节值得深究，感兴趣的可以自己去实现看看

//该仿函数作用将各种其他类型的值转化成整形
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)
	{
		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<K, V>_kv;
		Status _st = EMPTY;
		HashData() = default;
		HashData(const pair<K, V>& kv)
			:_st(EXIST)
			, _kv(kv)
		{}
	};

	template <class K, class V, class Hash = HashFun<K>>
	class HashTable {
	public:
		HashTable() :_table(10) {}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			if (_n * 10 / _table.size() == 7)//设置的负荷因子为0.7（具体是什么，下面会讲），if条件这样写是为了方便计算
			{
				size_t newSize = _table.size() * 2;

				HashTable<K, V>newHT;
				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<K, V>* 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<K, V>* 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<HashData<K, V>>_table;
		size_t _n = 0;
	};
}

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

开散列

开散列法又叫链地址法(开链法)，首先对关键字集合用散列函数计算散列地址，具有相同地

址的关键字归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链

接起来，各链表的头结点存储在哈希表中。 如下图

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

开散列的实现

namespace zxws
{
	template<class K,class V>
	struct HashNode
	{
		HashNode* next;
		pair<K, V>_kv;
		HashNode(const pair<K, V>&kv)
			:next(nullptr)
			,_kv(kv)
		{}
	};

	template<class K, class V,class Hash=HashFun<K>>//HashFun这个函数在闭散列的实现代码的最开始
	class HashTable
	{
		typedef HashNode<K, V> 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<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			Hash hf;

			if (_n == _table.size())//增容的条件在下面会讲
			{
				//复用之前的结点
				size_t sz = _table.size()*2;
				vector<Node*>newTable;
				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<Node*>_table;
		size_t _n;//有效元素个数
	};
}

开散列增容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可

能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希

表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，

再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可

以给哈希表增容。

HashFun函数的作用

因为我们写的哈希表的哈希函数为取模运算，只能是整形才能进行计算，所以如果是替他类型，我们就需要先将它转换成一个整形值，HashFun的作用就是将不同类型的值转成整形，我只写了string和一般的整形类型，如果是其他的自定义类型需要自己写仿函数，传入类模板

开散列和闭散列相比

优点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<string>
{
	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<T>* _cur;
		size_t _hashi;
		const HashBucket<K, T, Hash, KeyOfData>* _phb;//

		Iterator(HashNode<T>*cur, size_t hashi, const HashBucket<K, T, Hash, KeyOfData>* 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<T> Node;

		
		typedef Iterator<K, T, T&, T*, Hash, KeyOfData> iterator;
		typedef Iterator<K, T, const 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);
		}

		pair<iterator, bool> 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())
			{
				vector<Node*>v(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<Node*> _ht;
		size_t _n = 0;
	};
}

2.unordered_set的封装

namespace zxws
{
	template <class K,class Hash = HashFun<K>>
	class unordered_set {
		struct KeyOfData 
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

		typedef typename HashBucket<K, K, Hash, KeyOfData>::const_iterator iterator;
		typedef typename HashBucket<K, K, Hash, KeyOfData>::const_iterator const_iterator;

		pair<iterator,bool> 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<K, K, Hash, KeyOfData>_hb;
	};
}

3.unordered_map的封装

namespace zxws
{
	template <class K,class V,class Hash=HashFun<K>>
	class unordered_map {
		struct KeyOfData {
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashBucket<K, pair<const K, V>, Hash, KeyOfData>::iterator iterator;
		typedef typename HashBucket<K, pair<const K, V>, Hash, KeyOfData>::const_iterator const_iterator;
		pair<iterator, bool> insert(const pair<K, V>& 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:
		HashBucket<K, pair<const K,V>,Hash, KeyOfData>_hb;
	};
}