【C++进阶】：哈希

ゞ浴缸里的玫瑰 2024-03-03 09:06 102阅读 0赞

#### 哈希 ####

*  一.unordered\_map
 *  二.底层结构
 *   *  1.哈希概念
     *  2.解决哈希冲突
     *   *  1.闭散列
         *  2.开散列

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

## 一.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.  它的迭代器至少是前向迭代器。
7.  它的使用几乎与map一致。

## 二.底层结构 ##

### 1.哈希概念 ###

*复杂的说*

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log\_2 N log2N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

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

*简单的说*

![在这里插入图片描述][f7087217a7564d4c87b3547d5593d221.png]

> **上述就是一种k,v的映射关系，为了避免数组越界，我们还会对K(铅笔的号数)进行取模(%capcity)。相信大家也能发现，铅笔的号数肯定远远不止5个，例如：5号铅笔和10号铅笔都会储存在0号位置，这就是下哈希冲突。**

### 2.解决哈希冲突 ###

#### 1.闭散列 ####

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

*第一种：线性探测*

![在这里插入图片描述][f380568f9d264ed793403226afdeb2e5.png]

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

> **总的来说，将数据放入hash表时，如果该位置被占据，就向后查找，直到找到空位置进行插入。在查询数据时，一直查询直到找到或者找到空位置或者原点时停止。基于查找时找到空位置时停止，所以删除时就不能直接置空，需要标记该位置已被删除。接下来还有一个难点就是扩容。**

根据查找规则来看，如果等hash表填满才扩容，毫无疑问会发生很多冲突，这是很低效的，所以必须有一个扩容规则来判断何时扩容。

![在这里插入图片描述][27d0b986b3904e6f91609116b7f3ac1f.png]

enum State
    {
        
    	EXIST,
    	DELETE,
    	EMPTY
    };
    
    template<class K,class V>
    struct HashData//创建hash表的类型
    {
        
    	pair<K, V> _kv;
    	State _state=EMPTY;
    };
    
    template<class K,class V>
    class Hash
    {
        
    public:
    	Hash()
    	{
        
    		_table.resize(10);//初始开10给空间
    	}
    
    	void insert(const pair<K, V>& kv)
    	{
        
    		//判断是否需要扩容
    		if (n * 10 / _table.size() >= 7)
    		{
        
    			//开一个新的表容量为原来二倍
    			size_t newHash = _table.size() * 2;
    			Hash<K, V>newHT;
    			newHT._table.resize(newHash);
    
    			//将旧表的值插入到新表里
    			for (size_t i = 0; i < _table.size(); i++)
    			{
        
    				if (_table[i]._state == EXIST)
    					newHT.insert(_table[i]._kv);
    			}
    			//交换新旧表
    			_table.swap(newHT._table);
    		}
    
    		//线性探测
    		size_t hashi = kv.first % _table.size();//插入位置
    		while (_table[hashi]._state == EXIST)//判断应该插入的位置
    		{
        
    			hashi++;
    			hashi %= _table.size();
    		}
    		_table[hashi]._state = EXIST;
    		_table[hashi]._kv = kv;
    		n++;//有效长度加一
    	}
    private:
    	vector<HashData<K, V>>_table;//创建hash表
    	size_t n = 0;//记录有效长度
    };

*第二种二次探测*

> **二次探测与线性探测基本一致，只是线性探测在找空位时依次向后找，而二次探测在找空位时，一次走i的平方。**

![在这里插入图片描述][9ebe7e8551f94220b7f3b30452460465.png]

#### 2.开散列 ####

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

![在这里插入图片描述][f920f79407124f6389771d8dcc8eb56e.png]

![在这里插入图片描述][dcf70cef7a3b4c7d9fe54a85db7418a7.png]

接下来是扩容操作，其实开散表即使不扩容也能正常使用，但如果数据插入过多，会导致桶越来越长，最终变成长链表，导致查找效率降低。所以我们需要引入负载因子来判断何时应该扩容（负载因子计算看与闭散表一致）。

整个扩容需要遍历所有链表，把它们的指针都指向新链表就可以了。

![在这里插入图片描述][7b9a7dcac82e4d26adb4e6bbc50b78db.png]

这里需要补充一点，因为我们的K值不一定都是int类型，所以需要写仿函数来将它转成int，这样才能对应数组下标。

![在这里插入图片描述][134eda5a2afc4b7f930bf949d9bcdcb7.png]

又因为字符串是我们常用的数据类型，所以我们可以将它进行一个特例化，单独将字符串转化拎出来（字符串转化规则是根据字符串哈希转化规则进行转化的，不明白的可以自行百度）。

![在这里插入图片描述][04171e5ad9dc46a6b1e073c1b59f49ca.png]

![在这里插入图片描述][133a80ccd08e4435ab8b751016672522.png]  
![在这里插入图片描述][21dcfc789e5f4793b2dc9b77c6b770dd.png]

接下来删除和查找都比较简单，直接看完整源代码。

*Hash.h*

#include<iostream>
    #include<vector>
    using namespace std;
    
    
    template<class K>
    struct DefaultHashFunc//仿函数
    {
        
    	size_t operator()(const K& key)
    	{
        
    		return (size_t)key;
    	}
    };
    
    template<>
    struct DefaultHashFunc<string>//特例化
    {
        
    	size_t operator()(const string& str)
    	{
        
    		// BKDR
    		size_t hash = 0;
    		for (auto ch : str)
    		{
        
    			hash *= 131;
    			hash += ch;
    		}
    
    		return hash;
    	}
    };
    
    namespace open_adress
    {
        
    	enum State
    	{
        
    		EXIST,
    		DELETE,
    		EMPTY
    	};
    
    	template<class K, class V>
    	struct HashData//创建hash表的类型
    	{
        
    		pair<K, V> _kv;
    		State _state = EMPTY;
    	};
    
    	template<class K, class V>
    	class Hash
    	{
        
    	public:
    		Hash()
    		{
        
    			_table.resize(10);//初始开10给空间
    		}
    
    		void insert(const pair<K, V>& kv)
    		{
        
    			//判断是否需要扩容
    			if (n * 10 / _table.size() >= 7)
    			{
        
    				//开一个新的表容量为原来二倍
    				size_t newHash = _table.size() * 2;
    				Hash<K, V>newHT;
    				newHT._table.resize(newHash);
    
    				//将旧表的值插入到新表里
    				for (size_t i = 0; i < _table.size(); i++)
    				{
        
    					if (_table[i]._state == EXIST)
    						newHT.insert(_table[i]._kv);
    				}
    				//交换新旧表
    				_table.swap(newHT._table);
    			}
    
    			//线性探测
    			size_t hashi = kv.first % _table.size();//插入位置
    			while (_table[hashi]._state == EXIST)//判断应该插入的位置
    			{
        
    				hashi++;
    				hashi %= _table.size();
    			}
    			_table[hashi]._state = EXIST;
    			_table[hashi]._kv = kv;
    			n++;//有效长度加一
    		}
    	private:
    		vector<HashData<K, V>>_table;//创建hash表
    		size_t n = 0;//记录有效长度
    	};
    }
    
    
    
    namespace hash_bucket
    {
        
    	template<class K,class V>
    	struct HashData//创建节点
    	{
        
    		HashData<K, V>* next;
    		pair<K, V>_kv;
    		HashData(const pair<K,V>&kv)
    			:next(nullptr)
    			,_kv(kv)
    		{
        }
    	};
    
    
    	template<class K,class V,class HashFunc= DefaultHashFunc<K>>
    	class Hash
    	{
        
    		typedef HashData<K, V> Node;
    	public:
    		Hash()
    		{
        
    			_table.resize(10,nullptr);
    		}
    		~Hash()
    		{
        
    			for (size_t i = 0; i < _table.size(); i++)
    			{
        
    				Node* cur = _table[i];
    				while (cur)
    				{
        
    					Node* next = cur->next;
    					delete cur;
    					cur = next;
    				}
    
    				_table[i] = nullptr;
    			}
    		}
    		HashFunc hf;
    		bool Insert(const pair<K, V>& kv)
    		{
        
    			//如果重复插入返回false
    			if (Find(kv.first))
    			{
        
    				return false;
    			}
    
    			//扩容
    			if (_n == _table.size())
    			{
        
    				vector<Node*>newTable;
    				newTable.resize(_table.size() * 2, nullptr);
    				//遍历所有节点
    				for (size_t i = 0; i < _table.size(); i++)
    				{
        
    					Node* cur = _table[i];
    					while (cur)
    					{
        
    						size_t hashi = hf(cur->_kv.first) % newTable.size();
    						cur->next = newTable[hashi];
    						newTable[hashi] = cur;
    						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++;
    
    			return true;
    		}
    
    		Node* Find(const K&key)
    		{
        
    			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)
    		{
        
    			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;
    					return true;
    				}
    				prev = cur;
    				cur = cur->next;
    			}
    			--_n;
    			
    			return false;
    		}
    
    		void Print()
    		{
        
    			for (size_t i = 0; i < _table.size(); i++)
    			{
        
    				printf("[%d]->", i);
    				Node* cur = _table[i];
    				while (cur)
    				{
        
    					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
    					cur = cur->next;
    				}
    				printf("NULL\n");
    			}
    			cout << endl;
    		}
    
    	private:
    		vector<Node*>_table;
    		size_t _n = 0;
    	};
    	
    }

*test.cpp*

int main()
    {
        
    	hash_bucket::Hash<int, int> ht;
    	int a[] = {
         1,111,4,7,15,25,44,9 };
    	for (auto e : a)
    	{
        
    		ht.Insert(make_pair(e, e));
    	}
    	ht.Print();
    
    	ht.Insert(make_pair(14, 14));
    	ht.Print();
    
    	ht.Insert(make_pair(24, 24));
    	ht.Print();
    
    	ht.Insert(make_pair(34, 34));
    	ht.Print();
    
    	ht.Erase(44);
    	ht.Erase(4);
    	ht.Erase(24);
    	ht.Print();
    
    	hash_bucket::Hash<string, string> dict;
    	dict.Insert(make_pair("sort", "排序"));
    	dict.Insert(make_pair("left", "xxx"));
    	dict.Insert(make_pair("insert", "插入"));
    	dict.Insert(make_pair("string", "字符串"));
    	dict.Insert(make_pair("bucket", "桶"));
    
    	auto dret = dict.Find("left");
    	//dret->_kv.first = "xx";
    	dret->_kv.second = "左边";
    	dict.Print();
    
    	return 0;
    }

[f7087217a7564d4c87b3547d5593d221.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/a5c24dbea7b849c7b881c9655e33300b.png
[f380568f9d264ed793403226afdeb2e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/55e9e6f25d004c31b5bec6883a5780ad.png
[27d0b986b3904e6f91609116b7f3ac1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/b33b8959862a4d59ad2586c6224a3c9e.png
[9ebe7e8551f94220b7f3b30452460465.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/b4922b7d2ae14c269927744e13240efe.png
[f920f79407124f6389771d8dcc8eb56e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/7512e677948d47e6940402dc4f9ea764.png
[dcf70cef7a3b4c7d9fe54a85db7418a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/f366806c6009438083923c7c7d72b771.png
[7b9a7dcac82e4d26adb4e6bbc50b78db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/6e80b33697164c3c9bbfd6f5552cd224.png
[134eda5a2afc4b7f930bf949d9bcdcb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/10ed9d69c1af4742b93799efbc85da39.png
[04171e5ad9dc46a6b1e073c1b59f49ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/2bfd6a0886b94a8aa73ac25ccd522bf5.png
[133a80ccd08e4435ab8b751016672522.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/83ec1767bba44cad9e31a4e776cc47cd.png
[21dcfc789e5f4793b2dc9b77c6b770dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/06726d1d0d3d4faa970993e5cc570abc.png