【数据结构】深入理解哈希及其底层数据结构

目录

一、unordered系列关联式容器

二、底层结构

2.1 哈希的概念

 2.2 哈希冲突（哈希碰撞）

2.3 哈希函数

2.4 哈希冲突处理

2.4.1 闭散列（开放定址法）

2.4.1.1 代码实现：

2.4.2 开散列（链地址法，较优）

2.4.2.1 扩容

 2.4.2.2 仿函数实现多类型储存

2.4.2.3 代码实现 

 2.4.3 开散列与闭散列比较

 三、哈希表的模拟实现(加迭代器)

1.unordered_set

 2.unordered_map.h

3.test.c

---

一、unordered系列关联式容器

        在c++11中一共添加了4个unordered系列关联式容器，它们提供了基于哈希表的实现，以平均常数时间复杂度进行元素的查找、插入和删除操作。  分别为

std::unordered_map       std::unordered_multimap
std::unordered_set       std::unordered_multiset

        这些unordered系列的容器与stl中的map、multimap、set和multiset相对应，但后者是基于红黑树实现的，提供的是有序的元素集合，而前者的实现则基于哈希表，提供的是无序的元素集合，且在平均情况下，对元素的查找、插入和删除操作具有更好的性能。

二、底层结构

unordered系列的容器之所以效率高，归功于它的底层哈希结构。 

2.1 哈希的概念

        在顺序结构或者树中，元素的储存位置与其值没有什么对应关系，一般查找一个值时我们都需要去经过多次比较，时间复杂度为o(n)，平衡树中为树的高度，效率与比较次数直接挂钩。

这时我们想有没有一个理想的方法可以不经过任何比较，一次直接从表中得到要搜索的元素呢？

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

 在插入时：根据待插入元素的关键码，用哈希函数计算出该元素的存储位置并存放

 在查找时：同插入一样，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

        大佬们将这种方法称为哈希（或者散列）方法，而哈希方法中计算存储位置的函数称为哈希函数，构造出的表叫做哈希表（散列表）。

例如：

 2.2 哈希冲突（哈希碰撞）

 在插入时有时多个值通过哈希函数的计算会计算处相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

2.3 哈希函数

哈希冲突是无法避免的，但只要我们设计出合理的哈希函数，就能极大的降低哈希冲突的概率 

哈希函数的设计有几个原则：

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

常见的哈希函数：   

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

取关键字的某个线性函数为散列地址：hash（key）= a*key + b

优点：简单、均匀

缺点：需要事先知道关键字的分布情况，适合查找比较小且连续的情况

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

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

常用的哈希函数还有数字分析法、平方取中法、折叠法、随机数法等，但上述两种方法最为常用。

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

2.4 哈希冲突处理

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

2.4.1 闭散列（开放定址法）

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

这里我们主要讲解线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

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

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

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

2.4.1.1 代码实现：

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class hashfunc<string>
{
public:
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

namespace open_address
{
	//枚举状态
	enum state
	{
		empty,
		exist,
		delete
	};

	template<class k,class v>
	struct hashdata
	{
		pair<k, v> _kv;//值
		state _state = empty;//状态标记
	};

	template<class k,class v,class hash=hashfunc<k>>
	class hashtable
	{
	public:
		hashtable(size_t size = 10)
		{
			_tables.resize(size);
		}
		hashdata<k, v>* find(const k& key)
		{
			hash hs;
			// 线性探测
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != empty)
			{
				if (key == _tables[hashi]._kv.first
					&& _tables[hashi]._state == exist)
				{
					return &_tables[hashi];
				}

				++hashi;
				hashi %= _tables.size();
			}

			return nullptr;
		}
		bool insert(const pair<k, v>& kv)
		{
			if (find(kv.first))
				return false;
			if (_n * 10 / _tables.size() >= 7)
			{
				hashtable<k, v, hash> newht(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == exist)
					{
						newht.insert(e._kv);
					}
				}
				_tables.swap(newht._tables);
			}
			hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state==exist)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = exist;
			++_n;

			return true;
		}

		bool erase(const k& key)
		{
			hashdata<k, v>* ret = find(key);
			if (ret)
			{
				_n--;
				ret->_state = delete;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<hashdata<k, v>> _tables;
		size_t _n = 0;
	};
}

负载因子：表内元素/表的长度 

 对于开放寻址法来说，由于所有元素都存储在哈希表的数组中，并且不使用额外的数据结构（如链表）来处理冲突，因此负载因子的控制尤为重要。一旦负载因子过高，就可能导致哈希表性能急剧下降，因为插入和查找操作可能需要遍历更多的槽位才能找到所需元素或空槽位。

一般控制在0.7~0.8之间 

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

2.4.2 开散列（链地址法，较优）

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

开散列中每个桶中放的都是发生哈希冲突的元素

2.4.2.1 扩容

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

//负载因子到1就扩容
if (_n == _tables.size())
{
	vector<node*> newtables(_tables.size() * 2, nullptr);
	for (size_t i = 0; i < _tables.size(); i++)
	{
		// 取出旧表中节点，重新计算挂到新表桶中
		node* cur = _tables[i];
		while (cur)
		{
			node* next = cur->_next;

			// 头插到新表
			size_t hashi = hs(cur->_kv.first) % newtables.size();
			cur->_next = newtables[hashi];
			newtables[hashi] = cur;

			cur = next;
		}
		_tables[i] = nullptr;
	}

	_tables.swap(newtables);
}

在极端情况下可能会出现一个桶太长的情景，我们可以将这个桶的元素放到红黑树中去，将这棵树作为一个桶 

 2.4.2.2 仿函数实现多类型储存

如果想要存储各种类型的数据，我们可以通过传仿函数来实现

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};


//特化
template<>
class hashfunc<string>
{
public:
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

template<class k,class v,class hash=hashfunc<k>>
class hashtable；

2.4.2.3 代码实现 

代码实现：

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class hashfunc<string>
{
public:
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};

namespace hash_bucket
{
	template<class k,class v>
	struct hashnode
	{
		hashnode<k, v>* _next;
		pair<k, v> _kv;

		hashnode(const pair<k, v>& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
	};

	template<class k,class v,class hash=hashfunc<k>>
	class hashtable
	{
		typedef hashnode<k, v> node;
	public:
		hashtable()
		{
			_tables.resize(10, nullptr);
			_n = 10;
		}
		~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;
			}
		}

		node* find(const k& key)
		{
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
					cur = cur->_next;
			}
			return nullptr;
		}
		bool insert(const pair<k, v>& kv)
		{
			if (find(kv.first))
				return false;
			hash hs;
			//负载因子到1就扩容
			if (_n == _tables.size())
			{
				vector<node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					// 取出旧表中节点，重新计算挂到新表桶中
					node* cur = _tables[i];
					while (cur)
					{
						node* next = cur->_next;

						// 头插到新表
						size_t hashi = hs(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}
			size_t hashi = hs(kv.first) % _tables.size();
			node* newnode = new node(kv);

			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			_n++;
			return true;
		}
		bool erase(const k& key)
		{
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* prev = nullptr;
			node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 删除
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_tables[hashi] = cur->_next;
					}

					delete cur;

					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<node*> _tables;
		size_t _n;
	};

}

 2.4.3 开散列与闭散列比较

        应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。

        事实上, 由于开地址法必须保持大量的空闲空间以确保搜索效率，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

 三、哈希表的模拟实现(加迭代器)

1.unordered_set

unordered_set.h

#pragma once
#include"hashtable.h"

namespace l
{
	template<class k, class hash = hashfunc<k>>
	class unordered_set
	{
		struct setkeyoft
		{
			const k& operator()(const k& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::hashtable<k, const k, setkeyoft, hash>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		bool insert(const k& key)
		{
			return _ht.insert(key);
		}
		bool find(const k& key)
		{
			return _ht.find(key);
		}
		bool erase(const k& key)
		{
			return _ht.erase(key);
		}
	private:
		hash_bucket::hashtable<k, const k, setkeyoft, hash> _ht;
	};


	
}

hashtable.h 

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

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class hashfunc<string>
{
public:
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};


namespace hash_bucket
{
	template<class t>
	struct hashnode
	{
		hashnode<t>* _next;
		t _data;

		hashnode(const t& data)
			:_next(nullptr)
			, _data(data)
		{}
	};
	//前置声明
	template<class k, class t, class keyoft, class hash>
	class hashtable;

	template<class k,class t,class keyoft,class hash>
	struct __htiterator
	{
		typedef hashnode<t> node;
		typedef hashtable<k, t, keyoft, hash> ht;
		typedef __htiterator<k, t, keyoft, hash> self;

		node* _node;
		ht* _ht;

		__htiterator(node* node,ht* ht)
			:_node(node)
			,_ht(ht)
		{}
		t& operator*()
		{
			return _node->_data;
		}
		self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				keyoft kot;
				hash hs;
				size_t hashi = hs(kot(_node->_data)) %_ht->_tables.size();
				hashi++;

				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}

					hashi++;
				}
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
	};

	template<class k, class t, class keyoft,class hash>
	class hashtable
	{
		typedef hashnode<t> node;
		//友元 
		template<class k, class t, class keyoft, class hash>
		friend struct __htiterator;
	public:
		typedef __htiterator<k, t, keyoft, hash> iterator;
		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);
		}
		hashtable()
		{
			_tables.resize(10, nullptr);
			_n = 10;
		}
		~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;
			}
		}

		node* find(const k& key)
		{
			keyoft kot;
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool insert(const t& data)
		{
			keyoft kot;
			if(find(kot(data)))
				return false;
			hash hs;
			//负载因子到1就扩容
			if (_n == _tables.size())
			{
				vector<node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					// 取出旧表中节点，重新计算挂到新表桶中
					node* cur = _tables[i];
					while (cur)
					{
						node* next = cur->_next;

						// 头插到新表
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}
			size_t hashi = hs(kot(data)) % _tables.size();
			node* newnode = new node(data);

			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			_n++;
			return true;
		}
		bool erase(const k& key)
		{
			keyoft kot;
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* prev = nullptr;
			node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->kot(cur->_data) == key)
				{
					// 删除
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_tables[hashi] = cur->_next;
					}

					delete cur;

					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<node*> _tables;
		size_t _n;
	};
}

 2.unordered_map.h

#pragma once
#include"hashtable.h"
namespace l
{
	template<class k, class v, class hash = hashfunc<k>>
	class unordered_map
	{
		struct mapkeyoft
		{
			const k& operator()(const pair<k, v>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::hashtable<k, pair<const k, v>, mapkeyoft, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

		bool insert(const pair<k, v>& kv)
		{
			return _ht.insert(kv);
		}
	private:
		hash_bucket::hashtable<k, pair<const k, v>, mapkeyoft, hash> _ht;
	};
	
}

hashtable.h

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

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};

template<>
class hashfunc<string>
{
public:
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto e : s)
		{
			hash += e;
			hash *= 131;
		}
		return hash;
	}
};


namespace hash_bucket
{
	template<class t>
	struct hashnode
	{
		hashnode<t>* _next;
		t _data;

		hashnode(const t& data)
			:_next(nullptr)
			, _data(data)
		{}
	};
	//前置声明
	template<class k, class t, class keyoft, class hash>
	class hashtable;

	template<class k,class t,class keyoft,class hash>
	struct __htiterator
	{
		typedef hashnode<t> node;
		typedef hashtable<k, t, keyoft, hash> ht;
		typedef __htiterator<k, t, keyoft, hash> self;

		node* _node;
		ht* _ht;

		__htiterator(node* node,ht* ht)
			:_node(node)
			,_ht(ht)
		{}
		t& operator*()
		{
			return _node->_data;
		}
		self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				keyoft kot;
				hash hs;
				size_t hashi = hs(kot(_node->_data)) %_ht->_tables.size();
				hashi++;

				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}

					hashi++;
				}
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
	};

	template<class k, class t, class keyoft,class hash>
	class hashtable
	{
		typedef hashnode<t> node;
		//友元 
		template<class k, class t, class keyoft, class hash>
		friend struct __htiterator;
	public:
		typedef __htiterator<k, t, keyoft, hash> iterator;
		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);
		}
		hashtable()
		{
			_tables.resize(10, nullptr);
			_n = 10;
		}
		~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;
			}
		}

		node* find(const k& key)
		{
			keyoft kot;
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool insert(const t& data)
		{
			keyoft kot;
			if(find(kot(data)))
				return false;
			hash hs;
			//负载因子到1就扩容
			if (_n == _tables.size())
			{
				vector<node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					// 取出旧表中节点，重新计算挂到新表桶中
					node* cur = _tables[i];
					while (cur)
					{
						node* next = cur->_next;

						// 头插到新表
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}
			size_t hashi = hs(kot(data)) % _tables.size();
			node* newnode = new node(data);

			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			_n++;
			return true;
		}
		bool erase(const k& key)
		{
			keyoft kot;
			hash hs;
			size_t hashi = hs(key) % _tables.size();
			node* prev = nullptr;
			node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->kot(cur->_data) == key)
				{
					// 删除
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_tables[hashi] = cur->_next;
					}

					delete cur;

					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<node*> _tables;
		size_t _n;
	};
}

3.test.c

#include"my_unordered_map.h"
#include"my_unordered_set.h"
//void test_set1()
//{
//	l::unordered_set<int> us;
//	us.insert(3);
//	us.insert(1);
//	us.insert(5);
//	us.insert(15);
//	us.insert(45);
//	us.insert(7);
//
//	l::unordered_set<int>::iterator it = us.begin();
//	while (it != us.end())
//	{
//		//*it += 100;
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : us)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//void test_map1()
//{
//	l::unordered_map<string, string> dict;
//	dict.insert(make_pair("sort", "1"));
//	dict.insert(make_pair("left", "2"));
//	dict.insert(make_pair("right", "3"));
//
//
//	l::unordered_map<string, string>::iterator it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << (*it).first << " " << (*it).second << endl;
//		//cout << *it.first << " " << *it.second << endl;
//		/*pair<string, string> t=*it;
//		cout << t.first << " " << t.second<<endl;*/
//		++it;
//	}
//	cout << endl;
//	//for (auto& kv : dict)
//	//{
//	//	//kv.first += 'x';
//	//	kv.second += 'y';
//
//	//	cout << kv.first << ":" << kv.second << endl;
//	//}
//}

int main()
{
//	l::test_set1();
//	l::test_map1();
	return 0;
}