C++进阶——哈希的实现

C 进阶——哈希的实现

unordered系列关联式容器

在C  11出现中有了重大更新就是添加了移动构造和unordered关联容器。

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

unordered_map

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器（单向只增）。

unordered_set

其实和set基本功能是一样的，但是没有排序能力。

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O( l o g 2 N log_2 N log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一个一个地映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：

• 插入元素
  根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
  对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
  取元素比较，若关键码相等，则搜索成功
  该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称
  为哈希表(Hash Table)(或者称散列表)
  例如：数据集合{1，7，6，4，5，9}；
  哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
  
  用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
  问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
  答：会出现44和4同时都指向下标4这个位置，4不就会被取代了，这该怎么办呢？

哈希冲突

刚刚提到的问题就是哈希冲突的一种体现形式：
对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i != j)，有 k i k_i ki != k j k_j kj，但有：Hash( k i k_i ki) ==
Hash( k j k_j kj)，即：不同关键字通过相同哈希数计算出相同的哈希地址，该种现象称为哈希冲突
或哈希碰撞。

• 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢？

哈希函数

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

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有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. 数学分析法–(了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定
   相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只
   有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散
   列地址。
   注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置
呢？

1. 线性探测
   比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，
   因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
   线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
   插入
   通过哈希函数获取待插入元素在哈希表中的位置
   如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，
   使用线性探测找到下一个空位置，插入新元素
   
   删除
   采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素
   会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影
   响。因此线性探测采用标记的伪删除法来删除一个元素。

    // 哈希表每个空间给个标记
    // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
    enum State{EMPTY, EXIST, DELETE};
   

线性探测的实现

#pragma once
#ifndef __HASH_H__
#define __HASH_H__
#include<iostream>
#include<vector>
using namespace std;
namespace tom
{
	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 HashTable
	{
	public:
		HashData<K,V>* Find(const K& key)//返回的是数据指针
		{
			if (_table.size() == 0)
			{
				//return false;//为什么返回false？
				return nullptr;
			}

			size_t hashi = key % _table.size();
			//线性探测
			size_t i = 1;
			size_t index = hashi;
			while (_table[index]._state != EMPTY)
			{
				if (_table[index]._state == EXIST&&_table[index]._kv.first==key)
				{
					return &_table[index];
				}
				index = hashi   i;
				index %= _table.size();
				  i;
				if (index == hashi)
				{
					break;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{

			HashData<K, V>* res = Find(key);
			if (res)
			{
				res->_state = DELETE;
				--_count;
				return true;
			}
			return false;
		}

		bool Insert(const pair<K, V>& kv)
		{
			if(Find(kv.first)) return false;
			if (_table.size() == 0 || _count * 10 / _table.size() >= 7)//扩容，还能再办？
			{
				size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
				HashTable<K, V> newHt;
				newHt._table.resize(newsize);
				for (auto& data : _table)
				{
					if (data._state == EXIST)
					{
						newHt.Insert(data._kv);//自己掉自己——容量超标的调用一个容量不超标的。不会产生死循环！
					}
				}
				_table.swap(newHt._table);
			}
			size_t hashi = kv.first % _table.size();
			size_t i = 1;
			size_t index = hashi;
			while (_table[index]._state == EXIST)
			{
				index = hashi   i;
				index %= _table.size();
				  i;
			}

			_table[index]._kv = kv;
			_table[index]._state = EXIST;
			_count  ;

			return true;
		}
	private:
		vector<HashData<K, V>> _table;
		size_t _count = 0;//存了多少数据，利用vector的性质减少了封装。
	};
}

#endif // !__HASH_H__

扩容
在实现哈希函数的时候还要考虑扩容，什么时候扩容呢？是满了以后才扩容吗？
这里要引入一个定义：载荷因子（负载因子），当载荷因子=0.7时就开始扩容。
载荷因子怎么算呢：已经存在的数的个数count/哈希表的size=$a$ (载荷因子)。

不需要单独写一个扩容函数了，你如果想要封装也是可以的，我单独拿出来了。
但是要记住我们的count和size都是size_t类型整数，所以不能和0.7这样的浮点数比较，于是要两边都乘十，这样就解决了。

if (_table.size() == 0 || _count * 10 / _table.size() >= 7)//扩容
			{
				size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
				HashTable<K, V> newHt;
				newHt._table.resize(newsize);
				for (auto& data : _table)
				{
					if (data._state == EXIST)
					{
						newHt.Insert(data._kv);//自己掉自己——容量超标的调用一个容量不超标的。不会产生死循环！
					}
				}
				_table.swap(newHt._table);
			}
			size_t hashi = kv.first % _table.size();
			size_t i = 1;
			size_t index = hashi;
			while (_table[index]._state == EXIST)
			{
				index = hashi   i;
				index %= _table.size();
				  i;
			}

测试函数

void TestHashTable1()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(15, 15));

	if (ht.Find(1002))
	{
		cout << "1002在" << endl;
	}
	else
	{
		cout << "1002不在" << endl;
	}

	ht.Erase(13);

	if (ht.Find(13))
	{
		cout << "13在" << endl;
	}
	else
	{
		cout << "13不在" << endl;
	}
}

测试成功！

开散列

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

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

开散列实现

#pragma once
#ifndef __HASHBUCKET_H__
#define __HASHBUCKET_H__
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
namespace tom
{
	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 HashTable
	{
		typedef HashNode<K, V> node;
	public:
		~HashTable()
		{
			for (auto& cur : _table)
			{
				while (cur)
				{
					node* next = cur->_next;
					delete cur;
					cur = next;
				}
				cur = nullptr;
			}	
		}

		node* find(const K&key)
		{
			if (_table.size() == 0)
				return nullptr;
			size_t hashi = 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)
		{
			if (!find(key)) return false;

			size_t hashi = key % _table.size();
			node* prev = nullptr;
			node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					break;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			--_count;
			return true;
		}
		bool insert(const pair<K,V>& kv)
		{
			if (find(kv.first)) return false;
			if (_count == _table.size())//载荷因子为 1 .就开始扩容。
			{
				size_t newsize = _table.size () ? _table.size() * 2 : 10;//让我试一下这样行不行 
				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<node*> newtable(newsize, nullptr);
				for (auto& cur : _table)
				{
					while (cur)
					{
						node* next = cur->_next;//记录旧表的next，不然经过下面的转换就会找不到旧表的next了
						size_t hashi = cur->_kv.first % newsize;
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
				}
				_table.swap(newtable);
			}

			size_t hashi = kv.first % _table.size();
			node* newnode = new node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			  _count;
			return true;
		}
	private:
		vector<node*> _table; //指针数组
		int _count = 0;//有效数据的个数
	};
}

#endif // !__HASHBUCKET_H__

插入：
我们采用头插进行插入数据，这样更加方便操作，维察也可以不过数据链一多，还要挨个遍历一遍哈希桶太臃肿了。

最后变成如下图：

bool insert(const pair<K,V>& kv)
		{
			if (find(kv.first)) return false;
			if (_count == _table.size())//载荷因子为 1 .就开始扩容。
			{
				size_t newsize = _table.size () ? _table.size() * 2 : 10;//让我试一下这样行不行 
				//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<node*> newtable(newsize, nullptr);
				for (auto& cur : _table)
				{
					while (cur)
					{
						node* next = cur->_next;//记录旧表的next，不然经过下面的转换就会找不到旧表的next了
						size_t hashi = cur->_kv.first % newsize;
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
						cur = next;
					}
				}
				_table.swap(newtable);
			}

			size_t hashi = kv.first % _table.size();
			node* newnode = new node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			  _count;
			return true;
		}

这里也要考虑负载因子a不过可以控制在1就可以了。if (_count == _table.size())//载荷因子为 1 .就开始扩容。

扩容是怎么样的呢？扩容 改变数据的位置。
如下图：

删除：
删除就是一个一个查找然后删掉，不过有一个问题要注意：就删除的要是链头就直接用next替代链头（头删），中间或者尾部就是普通删除。

bool erase(const K&key)
		{
			if (!find(key)) return false;

			size_t hashi = key % _table.size();
			node* prev = nullptr;
			node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					break;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			--_count;
			return true;
		}

测试函数

void TestHashTable1()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.insert(make_pair(15, 15));
	ht.insert(make_pair(25, 25));
	ht.insert(make_pair(35, 35));
	ht.insert(make_pair(45, 45));

}

void TestHashTable2()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}

	ht.erase(12);
	ht.erase(3);
	ht.erase(33);
}

测试成功！

这篇好文章是转载于：学新通技术网