【C++】开散列哈希表封装实现unordered_map和unordered_set

川长思鸟来 2024-04-21 19:15 0阅读 0赞

在未达成目的之前，一切具有诱惑力的事物都显得那么不堪一击

![在这里插入图片描述][322a15bb58944208ac67d852c44089c8.jpeg_pic_center]

#### 文章目录 ####

*  一、unordered系列关联式容器
 *  二、哈希函数和哈希冲突
 *  三、闭散列（你抢我的位置，我抢他的位置）
 *   *  1.哈希表结构
     *  2.Insert()
     *  3.Erase()（标记的伪删除法）
     *  4.Find()
     *  5.哈希表key值不能取模无法映射的解决方法（BKDRHash）
 *  四、开散列（挂哈希桶的方式）
 *   *  1.哈希表结构 && 构造和析构函数
     *  2.Insert()（单链表的头插）
     *  3.Erase()（归还结点空间的使用权）
     *  4.Find()
 *  五、封装实现unordered系列容器（不一样的const迭代器）
 *   *  1.普通迭代器（单向迭代器）
     *  2.为什么hashTable的const迭代器要重新写一个类？
     *   *  2.1 库里面是怎么做的？
         *  2.2 不能通过增加模板参数解决吗？（权限不能放大）
         *  2.3 哈希表和其他STL容器 支持普通迭代器构造const迭代器的本质是什么？（权限的缩小和平移）
     *  3.unordered\_map的\[ \]操作

--------------------

## 一、unordered系列关联式容器 ##

1.  
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log\_2 N log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。  
最好的查询是，只要进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，他们不再以红黑树作为底层结构，而是以挂哈希桶的哈希表作为底层结构，就是用存储结点指针的vector来实现哈希表，哈希表的每个位置是一个桶，桶结构是一个存储value的单链表，unordered\_set的桶中结点存储的是一个key值，unordered\_map的桶中结点存储的是一个键值对。

2.  
哈希最大的作用就是查找，如果你想进行排序什么的，哈希迭代器遍历的结果是无序的，只有map和set遍历的结果才是有序的，所以哈希并不具有排序的功能，unordered\_map和unordered\_set仅仅只有去重的功能而已。  
所以如果你想快速查找一个值，那就用哈希，如果你想排序什么的，就不要用哈希了，哈希只能帮助你快速查找，因为他的查找效率基本上接近常数次，效率很快。

## 二、哈希函数和哈希冲突 ##

1.通过某种映射关系得到关键码在哈希表中的哈希地址，这样的计算关系其实就是哈希函数。

1.  直接定址法–(常用)  
    取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B，常用的A是1，B是0。  
    优点：简单、均匀  
    缺点：需要事先知道关键字的分布情况，若分布较广，则空间消耗比较高。  
    使用场景：适合查找比较小且连续的情况
2.  除留余数法–(常用)  
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，  
    按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址，一般不这么干，最常用的就是拿vector.size()作为除数，每次扩容将vector.size()扩容二倍。但后面开散列的解决方式那里，我们会仿照库，用质数的集合作为vector.size()，然后用其作为除数。

下面是SGI版本的质数集合，容器每次扩容的大小用的都是下面集合中的某一个质数。

![在这里插入图片描述][592669665a5348d598319e2039a108cb.png]  
2.  
当多个关键码key在通过哈希函数映射之后，得到了相同的哈希地址，也就是多个key映射到同一个位置上时，这种现象称为哈希冲突或哈希碰撞。解决哈希冲突的办法一般为两种，一种是闭散列的方式解决，即用线性探测或二次探测的方式向后寻找空的哈希位置，一种是开散列的方式解决，即将哈希冲突的元素通过单链表链接，逻辑上像哈希表挂了一个个的桶，所以这样的解决方式也可称为拉链法，或哈希桶方式。

数据集合\{1, 7, 6, 4, 5, 9\}  
在下面的哈希表中插入一个31，则其映射位置是1，但是1位置已经有元素1了，此时就会发生哈希冲突，那就需要向后找空的位置插入31，这就是闭散列。  
![在这里插入图片描述][eb8a8e60933b4a4ba73e4995ffbddaab.png]

数据集合\{3, 13, 4, 7, 17, 1, 21, 6, 46, 2, 16\}  
发生哈希冲突的元素都被挂到原有结点的下面去了，逻辑上就像哈希表挂了一个个的桶。桶里面是哈希冲突元素的集合。  
![在这里插入图片描述][faadb2bd266f41dfb94f2dc66056ac2e.png]

## 三、闭散列（你抢我的位置，我抢他的位置） ##

### 1.哈希表结构 ###

1.  
由于这里的闭散列方法无须重点掌握，所以在实现时我们就不分key和键值对分别为存储元素时的情况了，这里只用键值对作为存储元素讲解哈希闭散列的方法。

2.  
对于闭散列结构，我们采用vector作为底层容器，用vector来存储哈希结点，哈希结点是一个结构体，其中存储键值对和状态值，\_state用于标定哈希映射位置为空、存在、删除三种状态。  
为了判断什么时候进行哈希表的扩容，在hashTable类中多增加了一个无符号整型的\_n变量，表示当前哈希表中存储数据的个数，方便我们用数据个数和vector.size()作除法，看结果是否大于负载因子，如果大于则扩容，如果不大于则继续插入。

enum state
    {
        
    	EMPTY,
    	EXIST,
    	DELETE
    };
    template <class K, class V>
    struct HashNode
    {
        
    	HashNode()
    		: _state(EMPTY)
    	{
        }
    	HashNode(const pair<K, V>& kv)
    		:_kv(kv)
    		, _state(EMPTY)
    	{
        }
    	pair<K, V> _kv;
    	enum state _state;
    };
    template <class K, class V, class Hash = BKDRHash<K>>
    class HashTable
    {
        
    public:
    	typedef HashNode<K, V> Node;
    	HashTable()
    		:_n(0)
    	{
        
    		_tables.resize(10);//需要给vector的size一个初始值，否则计算负载因子可能产生除0错误
    	}
    	………………省略
    private:
    	vector<Node> _tables;
    	size_t _n;//利用_n和_tables.size()去搞负载因子
    };

### 2.Insert() ###

1.  
闭散列的解决方式即为通过哈希函数求出key对应的映射位置后，如果自己的映射位置已存在元素，则线性探测向后寻找空的位置进行插入，比如下面的21的映射位置应该是1，但是1号位有元素1了，那21只能向后探测为空的位置进行插入，此时就会引发一个问题，21占了别的元素的映射位置，如果此时插入一个元素2，则2的映射位置也被抢了，那2就只能向后探测为空的位置了。  
所以闭散列的解决方法说白了就是你抢我的位置，那我就会去抢别人的位置。

2.  
我们不希望哈希表的所有空间都被占用，这样在查找的时候，哈希表的效率会非常的低，因为需要遍历，所以在哈希表中存储元素到达一定程度后，要对哈希表进行扩容，重新建立映射关系，缓解哈希冲突。  
![在这里插入图片描述][2b39ac2497f741358a1e2214af4b0180.png]  
3.  
**在实现扩容时，可以新建立一个vector**，然后遍历原来的vector的每一个元素，重新计算每一个元素在新vector的映射关系，然后将每一个元素进行插入，交换两个vector，则哈希表的扩容就完成了，但是这样的写法代码有点冗余，因为重新计算哈希映射位置的过程还需要重写一份。  
**所以另一种写法就是代码复用**，我们不再新建立vector，而是新建立一个哈希表，对新哈希表中的vector进行扩容，然后调用哈希表的Insert函数，将原vector中的键值对的关键码插入到新哈希表当中，这样就不需要自己在写代码，进行代码复用即可。最后将新哈希表中的vector和原哈希表的vector进行swap即可，这样就完成了原有数据到新表中的挪动，然后再插入要插入的kv即可。  
**在函数调用结束之后，临时对象newHT会被销毁，那我们还需要写哈希表的析构函数吗**？其实是不需要的，哈希表类默认生成的析构函数对内置类型\_n不处理，对自定义类型vector调用其析构函数，vector存储内容都可以看作是内置类型，因为键值对说到底也就是单一的结构体，所以vector的析构函数直接将vector所占用的一大块空间全部还给操作系统即可。那么我们就不需要自己写哈希表的析构函数，vector会帮我们做析构处理，并且内置类型\_n成员还不用处理。

bool Insert(const pair<K, V>& kv)
    {
        
    	if (Find(kv.first))
    			return false;
    	
    	//大于标定的负载因子，进行扩容，降低哈希冲突的概率
    	if (_n * 10 / _tables.size() > 7)//可能会出现除0错误
    	{
        
    		//旧表数据，重新计算，映射到新表
    		/*vector<Node> newtables;
    		newtables.resize(2 * _tables.size());	*/
    
    		HashTable<K, V, BKDRHash<K>> newHT;
    		newHT._tables.resize(2 * _tables.size());
    		for (auto& e : _tables)
    		{
        
    			if (e._state == EXIST)
    			{
        
    				newHT.Insert(e._kv);
    				//取原表中的数据插入到新表的vector里面，键值对之间发生赋值重载。因为newHT是新开的初始化好的哈希表
    				//递归通常是自己调用自己，这里不是递归，仅仅是代码复用而已。
    			}
    		}
    
    		_tables.swap(newHT._tables);
    	}
    
    	size_t hashi = Hash()(kv.first) % _tables.size();//这里不能%capacity，某些位置不是可用的，vector[]会对下标检查
    	while (_tables[hashi]._state == EXIST)
    	{
        
    		//线性探测
    		++hashi;
    		//二次探测
    		//hashi = hashi + i * i;//降低冲突概率，但还是有可能会冲突，占其他位置
    
    		hashi %= _tables.size();
    	}
    
    	/*_tables[hashi] = Node(kv);
    	_tables[hashi]._state = EXIST;*/
    	//在构造新表对象时，默认构造已经初始化好哈希表里面的结点空间了，你再开空间拷贝数据浪费。
    	_tables[hashi]._kv = kv;
    	_tables[hashi]._state = EXIST;
    	++_n;
    
    	return true;
    }

### 3.Erase()（标记的伪删除法） ###

1.  
大部分数据结构容器的删除其实都是伪删除或者叫做惰性删除，因为我们无法做到释放一大块空间的某一部分空间，所以在数据结构这里的删除基本都是用标记的伪删除，另一种常见的方式就是，堆排序的删除，我们当时用的也是size标识可用空间大小的方式，实际空间并没有改变，我们只是改变了自己的访问逻辑，不去访问array的size下标空间，但空间其实还原封不动的在那里。

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

2.  
哈希表的删除也一样，我们在每个结点里面增加一个状态标记，用状态来标记当前结点是否被删除。如果删除结点不存在，则返回false。

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

bool Erase(const K& key)
    {
        
    	Node* ret = Find(key);
    	if (ret == nullptr)
    		return false;
    
    	ret->_state = DELETE;
    	--_n;
    	return true;
    }

### 4.Find() ###

1.  
查找的代码其实比较简单，只需要先利用要查找的key值求出映射的哈希地址，如果映射地址对应的key值不是我们要查找的key值，则说明发生了哈希冲突，那就需要映射的哈希地址向后线性探测寻找要查找的键值对，找到后返回对应键值对的地址。

2.  
那什么时候查找结束呢？或者说向后循环查找的条件是什么呢？一般来说，如果映射位置的key和要查找的key不匹配，则一定说明要查找的key是冲突元素，如果这个冲突元素在哈希表里面，就比如31和21，则从1位置向后找，一定能够找到他们。如果这个冲突元素不在哈希表里面，比如27，那从7位置开始找，7后面是空，此时就不用在向后继续查找了，因为只要27存在，那7和27之间一定是连续的，所以如果从映射位置向后找，遇到empty状态的结点，就不用查找了，你要查找的哈希冲突元素一定不在哈希表里面。

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

3.  
在线性探测中，如果查找到尾部了，则让hashi%=vector的size即可，让hashi回到开头的位置。但有一种极端特殊情况，就是边插入边删除，这样整个哈希表中的结点状态有可能都是delete或exist，则在线性探测中不会遇到empty，while会陷入死循环，所以在while里面多加一层判断，如果start等于hashi，说明在哈希表中已经线性探测一圈了，那此时就返回，因为找了一圈都没找到key，那就说明key不在哈希表里面。

4.  
上面所说的是一种解决方式，但还有另外一种解决方式，由于delete和exist的存在，不是找不到empty吗？而且delete的作用和empty的作用是一致的，那我们可以直接摒弃掉原来的枚举值，将枚举值缩减为empty和exist，去掉delete，在erase之后，将结点状态设置为empty，这样哈希表中的结点状态只有空和存在，那就不会发生下面这样没有empty的情况，其实在枚举的设计上确实有点问题，empty和exist已经足够了，完全不需要delete。**（兄弟们，这样的解决方式是错误的，因为如果这么干了，比如一片哈希冲突，删除中间的某个元素之后，后面的冲突元素就找不到了，因为我们认为的是冲突元素之间一定是连续的，不能出现empty，delete状态的出现就是为了应对这样的情况的）**

Node* Find(const K& key)
    {
        
    	size_t hashi = Hash()(key) % _tables.size();
    	size_t start = hashi;
    	while (_tables[hashi]._state != EMPTY)
    	{
        
    		if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
    		{
        
    			return &_tables[hashi];
    		}
    
    		++hashi;
    		hashi %= _tables.size();//防止越界
    		if (start == hashi)
    			break;
    	}
    	return nullptr;
    }

5.  
上面闭散列的哈希表是不用写拷贝，赋值，析构的，因为默认生成的拷贝对vector会调用他的拷贝，pair也有自己的拷贝，析构也不用，直接释放vector的空间即可。

### 5.哈希表key值不能取模无法映射的解决方法（BKDRHash） ###

1.  
上面举例子时，键值对的key值都是整型，整型当然可以完成映射，那如果是自定义类型string呢？string如何对vector的size取模呢？此时就需要仿函数来完成自定义类型转换为整型的操作了，只有转换为整型，我们才能取模，进而才能完成哈希映射的工作。  
**对于其他类型，比如int，char，short，double等，我们直接强转为size\_t，这样就可以完成哈希映射**。

2.  
**哈希和红黑树都有key，两者的key各自都有什么要求呢？红黑树要求key能比较大小，因为他要让大的key到右面，小的key到左面。哈希要求key能够取模，也就是要求key能转成整型，因为他要完成哈希映射**。

3.  
字符串转换为整型的场景还是比较常见的，所以有人整理了一篇字符串哈希算法，思路就是将每一个字符对应的ascll码分别拆下来，每次的hash值都为上一次的hash值×131后再加上字符的ascll码值，遍历完字符串后，最后的hash为字符串转成整型的结果，这样每个字符串转换后的整型是极大概率不重复的，是一个非常不错的哈希算法，被人们称为BKDRHash。

[字符串哈希算法][Link 1]

template <class K>
    struct BKDRHash
    {
        
    	size_t operator()(const K& key)
    	{
        
    		return (size_t)key;//只要这个地方能转成整型，那就可以映射，指针浮点数负数都可以，但string不行
    	}
    };
    template <>
    struct BKDRHash<string>
    {
        
    	size_t operator()(const string& key)
    	{
        
    		//return key[0];//字符串第一个字符是整型，那就可以整型提升，只要是个整型能进行%模运算，完成映射即可。
    
    		size_t hash = 0;
    		for (auto ch : key)
    		{
        
    			hash = hash * 131 + ch;
    		}
    		return hash;
    	}
    };

## 四、开散列（挂哈希桶的方式） ##

### 1.哈希表结构 && 构造和析构函数 ###

1.  
开散列的哈希表是最常用的方式，库里面的unordered\_map和unordered\_set用的也是哈希桶的方式实现的，我们模拟实现的哈希桶也仿照库实现，哈希结点node里面存储键值对和下一个结点指针。  
在哈希表的模板参数中，也多加了一个缺省仿函数类的参数，也就是Hash，因为我们需要Hash的仿函数对象或匿名构造，将key转成整型。

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

template <class K, class V>
    struct hashNode
    {
        
    	hashNode(const pair<K,V>& kv)
    		:_kv(kv)
    		,_next(nullptr)
    	{
        }
    
    	pair<K, V> _kv;
    	hashNode<K, V>* _next;
    };
    template <class K, class V, class Hash = BKDRHash<K>>
    class hashTable
    {
        
    public:
    	typedef hashNode<K, V> Node;
    
    	…………省略
    private:
    	vector<Node*> _table;
    	size_t _n;
    };

2.  
对于哈希桶，我们必须写出析构函数，因为编译器默认生成的析构函数会调用vector的析构，而vector的析构仅仅只能将自己的空间还给操作系统，如果某些节点指针指向了具体的节点，则只归还vector的空间是不够的，还需要归还那些申请的节点空间。  
所以需要遍历每一个哈希桶，将每一个桶里面的节点都还给操作系统，这里就用到单链表的节点删除的知识了，在删除前需要保留下一个位置，要不然delete归还空间之后就找不到下一个节点的位置了。

hashTable()
    	:_n(0)
    {
        
    	_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;
    		}
    		_table[i] = nullptr;
    	}
    }

### 2.Insert()（单链表的头插） ###

1.  
我下面画的图只是想说明一下哈希桶的逻辑结构和扩容之后缓解哈希冲突的场景，但实际在插入节点时并不是像我下面画的那样对单链表进行尾插，因为尾插还需要找尾，那就需要遍历桶，这样的效率太低，并且桶中也不要求次序什么的，所以我们直接进行头插即可，头插的效率很高，因为映射找到哈希地址之后即可进行头插。

![在这里插入图片描述][c97ca0d1a81e4fb792d2874b0ffcb843.png]  
2.  
哈希桶的负载因子，官方默认值为1.0，那就是\_n和vector.size()相等的时候进行扩容，扩容的目的还是重新建立映射关系，缓解哈希冲突，因为如果某一个哈希桶的结点个数过多，在哈希映射之后还需要遍历哈希桶寻找结点，会降低哈希查找的效率，所以扩容就是多增加哈希桶的个数，减少平均哈希桶中结点的个数，提高哈希查找的效率。

![在这里插入图片描述][94547f05b59a420c9d75e6c742cadb63.png]  
3.  
扩容这里的思路和闭散列的哈希表比较相似，如果我们遍历原有结点的数据，将每个结点的数据重新new一个结点出来，然后插入到新的vector里面，或者是代码复用的方式进行插入，这两种都可以，但是效率太低了，上面所说的两种代码写法都是新new结点插入到新表的，如果有1w个结点呢？我们平白无故的拷贝出来1w个结点，然后临时对象销毁的时候又析构1w个结点？这不是冤大头么。为什么不将原来的结点链接到新的vector上面呢？

4.  
所以另一种写法就是遍历原表的每个结点指针，将每个指针指向结点的key重新计算哈希映射关系，头插到新的vector里面，在每完成一个桶的重新映射关系后，将原vector中的桶位置的指针置为空，否则析构的时候，结点会被析构两遍。等到原表的所有结点遍历完之后，将新的vector和原来的vector一交换即可，临时对象\_newtable在离开函数栈帧时会被销毁，调用vector的默认析构完成空间的归还即可。

5.  
研究表明，每次除留余数法最好模一个素数，这会大概率降低哈希冲突的可能性。所以我们下面的扩容大小每次挑选小于2倍的最大素数作为扩容后的vector大小，这里复用了一下stl库里面的素数表。

inline unsigned long __stl_next_prime(unsigned long n)
    {
        
    	static const int __stl_num_primes = 28;
    	static const unsigned long __stl_prime_list[__stl_num_primes] =
    	{
        
    	  53,         97,         193,       389,       769,
    	  1543,       3079,       6151,      12289,     24593,
    	  49157,      98317,      196613,    393241,    786433,
    	  1572869,    3145739,    6291469,   12582917,  25165843,
    	  50331653,   100663319,  201326611, 402653189, 805306457,
    	  1610612741, 3221225473, 4294967291
    	};
    
    	for (size_t i = 0; i < __stl_num_primes; i++)
    	{
        
    		if (__stl_prime_list[i] > n)
    		{
        
    			return __stl_prime_list[i];
    		}
    	}
    
    	return __stl_prime_list[__stl_num_primes - 1];
    }
    bool Insert(const pair<K, V>& kv)
    {
        
    	if (Find(kv.first))//不允许重复元素
    		return false;
    
    	//负载因子控制在1，超过就扩容
    	if (_n == _table.size())
    	{
        
    		/*hashTable<K, V, Hash> _newHT;
    		_newHT._table.resize(2 * _table.size());*/
    
    		//for (int hashi = 0; hashi < _table.size(); hashi++)
    		//{
        
    		//	Node* cur = _table[hashi];
    		//	while (cur)
    		//	{
        
    		//		_newtable.Insert(cur);//需要重新改变映射关系
    		//		cur = cur->_next;
    		//	}
    		//}
    		//_table.swap(_newHT._table);
    		
    		//上面是冤大头的做法，下面是正常的做法。
    		vector<Node*> _newtable;
    		_newtable.resize(__stl_next_prime(_table.size()), nullptr);//resize开空间后，默认值为Node*()的构造，我们也可以自己写
    		for (int i = 0; i < _table.size(); i++)
    		{
        
    			Node* cur = _table[i];
    			while (cur)
    			{
        
    				Node* next = cur->_next;
    				size_t hashi = Hash()(cur->_kv.first) % _newtable.size();
    				cur->_next = _newtable[hashi];
    				_newtable[hashi] = cur;
    
    				cur = next;
    			}
    
    			_table[i] = nullptr;
    		}
    		_table.swap(_newtable);
    	}
    
    	size_t hashi = Hash()(kv.first) % _table.size();
    	Node* newnode = new Node(kv);
    	newnode->_next = _table[hashi];//newnode的next指向当前表哈希映射位置的结点地址
    	_table[hashi] = newnode;//让newnode做头
    
    	++_n;
    	return true;
    }

### 3.Erase()（归还结点空间的使用权） ###

1.  
哈希桶的erase其实就是单链表结点的删除，如果是头删，那就是下一个指针作头，如果是中间删除，则记录前一个结点位置，让前一个结点的next指向删除结点的next。  
然后归还结点空间的使用权，即为delete结点指针。

bool Erase(const K& key)
    {
        
    	Node* ret = Find(key);
    	if (!ret)
    		return false;
    
    	size_t hashi = Hash()(key) % _table.size();
    	Node* cur = _table[hashi];
    	if (cur->_kv.first == key)//头删
    	{
        
    		_table[hashi] = cur->_next;
    		delete cur;
    		cur = nullptr;
    	}
    	else//中间删除
    	{
        
    		while (cur)
    		{
        
    			Node* prev = cur;
    			cur = cur->_next;
    			if (cur->_kv.first == key)
    			{
        
    				prev->_next = cur->_next;
    				delete cur;
    				cur = nullptr;
    			}
    		}
    	}
    	--_n;
    	return true;
    }

### 4.Find() ###

1.  
哈希桶的查找和闭散列的哈希表很相似，先通过key找到映射的哈希桶，然后去对应的哈希桶里面找查找的结点即可，找到返回结点地址，未找到返回nullptr即可。

Node* Find(const K& key)
    {
        
    	size_t hashi = Hash()(key) % _table.size();
    	Node* cur = _table[hashi];
    	while (cur)
    	{
        
    		if (cur->_kv.first == key)
    			return cur;
    		cur = cur->_next;
    	}
    	return nullptr;
    }

## 五、封装实现unordered系列容器（不一样的const迭代器） ##

### 1.普通迭代器（单向迭代器） ###

1.  
封装实现unordered系列容器的insert，find，erase等接口并不是什么难事，直接调用开散列哈希表的接口即可，而封装的主要关键点其实是实现容器的迭代器操作，只要实现了迭代器的操作，那我们自己封装的unordered系列容器基本上就能跑起来了。

2.  
如果要实现迭代器++的操作，如果我们只有结点的指针是无法完成迭代器++的，因为如果要遍历所有的哈希桶的结点，则必须需要哈希表本身，只有这样才能确定下一个哈希桶的位置，所以开散列哈希表的迭代器需要多封装一个哈希表指针，通过哈希表指针和哈希结点的指针，就可以访问整个表里面所有的结点了。

3.  
迭代器的++就是看当前指针的下一个是否为空，如果为空说明当前哈希桶里面只有他一个结点，那就需要寻找下一个哈希桶，将结点指针的指向移动到下一个哈希桶的结点指针处，如果向后找的过程中结点指针都是nullptr，那就是没有哈希桶，我们将\_node置为空即可，说明此时迭代器已经到end()的位置了，不能继续遍历下去了。

需要额外多说一点的是，由于迭代器内部用了哈希表指针，所以需要在迭代器的前面加上哈希表的模板声明。而且在迭代器内部还访问了哈希表的私有成员\_table，则需要在哈希表里面进行友元声明，将迭代器模板声明为哈希表的友元。  
![在这里插入图片描述][9ce25c545bad4ff687f6c55d7c2174cb.png]

//前置声明
    template <class K, class T, class Hash, class KeyOfT>
    class hashTable;
    
    template <class K, class T, class Hash, class KeyOfT>
    struct __HTIterator
    {
        
    	typedef hashNode<T> Node;
    	typedef hashTable<K, T, Hash, KeyOfT> HT;
    	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
    	Node* _node;
    	HT* _ht;
    
    	__HTIterator(Node* node, HT* ht)
    		:_node(node)
    		,_ht(ht)
    	{
        }
    
    	Self& operator++()
    	{
        
    		if (_node->_next)
    		{
        
    			_node = _node->_next;
    		}
    		else
    		{
        
    			//当前桶走完了，要去哈希表里面找下一个桶
    			size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_table.size();
    			hashi++;
    
    			while (hashi != _ht->_table.size() && _ht->_table[hashi] == nullptr)
    			{
        
    				hashi++;
    			}
    
    			if (hashi == _ht->_table.size())
    				_node = nullptr;
    			else
    				_node = _ht->_table[hashi];
    		}
    
    		return *this;
    	}
    
    	T& operator->()
    	{
        
    		return &_node->_data;
    	}
    	T* operator*()
    	{
        
    		return _node->_data;
    	}
    
    	bool operator!=(const Self& it)const
    	{
        
    		return _node != it._node;
    	}
    	bool operator==(const Self& it)const
    	{
        
    		return _node == it._node;
    	}
    };

### 2.为什么hashTable的const迭代器要重新写一个类？ ###

#### 2.1 库里面是怎么做的？ ####

1.  
我们可以先来看一下常规的迭代器操作，比如红黑树的迭代器，他的const迭代器并没有重写一个类，而是直接增加模板参数Ref和Ptr来完成对应普通引用和常引用的值的返回。  
并且支持普通迭代器构造const迭代器的操作，实际上STL的所有容器在实现迭代器的时候，都会用下面的方式来支持普通迭代器构造const迭代器，如果是普通迭代器调用，那这里就是普通和普通之间的拷贝，没啥用因为编译器也支持这样的操作，**但下面那段代码目的不是支持普通迭代器之间的拷贝，而是支持普通到const迭代器的构造操作**。

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

2.  
但是哈希表的迭代器却没有通过增加模板参数来解决，而是重写了一个struct \_\_hashtable\_const\_iterator \{ \}类，以这样的方式来实现unordered\_map和unordered\_set的const迭代器操作。  
![在这里插入图片描述][ab72a316bb874325bbbb94aabb71b065.png]

#### 2.2 不能通过增加模板参数解决吗？（权限不能放大） ####

1.  
其实能否通过增加模板参数解决const迭代器主要取决于迭代器类中的构造函数，之前能通过增加模板参数解决是因为无论是构造const迭代器还是构造普通迭代器，我们传给构造函数的指针都是普通指针，当然可以构造出普通迭代器和const迭代器了，因为两个迭代器的差别主要是\*和→重载的返回值是可修改的还是不可修改的，这个并不难解决。

2.  
而现在不一样了，哈希迭代器传的指针不是普通指针了，而是const指针，当调用begin()或end()函数的对象是const对象时，this指针指向的内容是不可修改的，并且由于对象是const对象，vector的\[ \]返回的也是const引用，而vector存储的是指针，那就说明哈希node结点指针指向的内容也是不可修改的。  
如果我们此时用这两个指针去构造const迭代器，而哈希迭代器类成员变量是两个普通指针，那在构造函数处就会发生const指针拷贝给普通指针的情况，此时权限会放大，所以如果你用增加模板参数来实现const迭代器，则编译器一定会报错，因为指针和引用在赋值时，权限只能平移和缩小，不能放大。

3.  
所以唯一的解决方式就是重写const迭代器类，将const迭代器类的私有成员变量改为两个const指针，这样在构造函数处构造const迭代器时，就不会出现权限的放大了，只是发生权限的平移。

template <class K, class T, class Hash, class KeyOfT>
    class hashTable
    {
        
    public:
    	friend struct __HTIterator<K, T, Hash, KeyOfT>;
    
    	typedef hashNode<T> Node;
    	typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
    
    	iterator begin()
    	{
        
    		for (size_t i = 0; i < _table.size(); i++)
    		{
        
    			if (_table[i])
    			{
        
    				return iterator(_table[i], this);//如果是const对象，这里返回const指针
    			}
    		}
    
    		return iterator(nullptr, this);//如果哈希表是空的或者没有桶，则构造空迭代器。
    	}
    	iterator end()
    	{
        
    		return iterator(nullptr, this);
    	}

#### 2.3 哈希表和其他STL容器 支持普通迭代器构造const迭代器的本质是什么？（权限的缩小和平移） ####

1.  
哈希表的迭代器是个特殊的存在，因为他的const和非const迭代器是两个类模板，而STL的其他容器的const和非const迭代器都是出自一个类模板。

2.  
本质还是因为哈希表的const迭代器的私有成员变量得是const指针，而其他容器的const迭代器的私有成员变量只是普通指针。**所以哈希表的普通迭代器构造const迭代器其实是权限的缩小，由普通指针赋值到const指针。而其他容器的普通迭代器构造const迭代器其实是权限的平移，因为无论是普通迭代器还是const迭代器，他们的成员变量都是普通指针**。

### 3.unordered\_map的\[ \]操作 ###

1.  
支持map的\[ \]操作并不困难，因为他的\[ \]操作其实就是通过insert返回迭代器和bool的键值对来实现的。当\[ \]内的key不存在，则调用哈希表的Inset完成key和V()构造的键值对的插入，并返回插入键值对的迭代器和true的bool值构造的键值对。当\[ \]内的key在哈希表中存在时，则哈希表的Insert也会返回指向key和value键值对的迭代器以及false的bool值构造的键值对。

2.  
所以实现\[ \]的重担主要是在Insert上面，只要Insert返回迭代器，那就能通过迭代器拿到键值对的value值，再通过返回value值的引用就可以修改哈希表中某一键值对的value值了。

下面是\[ \]函数和哈希表底层的Insert函数，Insert的逻辑没有变，只是将他的返回值从bool改为了键值对而已。

V& operator[](const K& key)
    {
        
    	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
    
    	return ret.first->second;
    }
    
    pair<iterator,bool> Insert(const T& data)
    {
        
    	KeyOfT kot;
    	iterator it = Find(kot(data));
    	if (it != end())
    		return make_pair(it, false);//如果插入的值已经存在那就不再进行插入，返回对应位置迭代器即可。
    
    	if (_n == _table.size())
    	{
        
    
    		vector<Node*> _newtable;
    		_newtable.resize(__stl_next_prime(_table.size()), nullptr);
    		for (int i = 0; i < _table.size(); i++)
    		{
        
    			Node* cur = _table[i];
    			while (cur)
    			{
        
    				Node* next = cur->_next;
    				size_t hashi = Hash()(kot(cur->_data)) % _newtable.size();
    				cur->_next = _newtable[hashi];
    				_newtable[hashi] = cur;
    
    				cur = next;
    			}
    
    			_table[i] = nullptr;
    		}
    		_table.swap(_newtable);
    	}
    
    	size_t hashi = Hash()(kot(data)) % _table.size();
    	Node* newnode = new Node(data);
    	newnode->_next = _table[hashi];
    	_table[hashi] = newnode;
    
    	++_n;
    	return make_pair(iterator(newnode, this), true);
    }
    
    void test_unordered_map()
    {
        
    	string arr[] = {
         "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜",
    		"苹果", "香蕉", "苹果", "香蕉" , "蓝莓" ,"草莓" };
    
    	unordered_map<string, int> countMap;
    	for (auto& e : arr)
    	{
        
    		countMap[e]++;
    	}
    	unordered_map<string, int>::iterator it = countMap.begin();
    	//1.不用语法糖，一点一点遍历也可以
    	while (it != countMap.end())
    	{
        
    		cout << it->first << ":" << it->second << endl;
    		++it;
    	}
    	//2.我们实现了迭代器，直接用语法糖也可以。
    	for (const auto& kv : countMap)//将解引用后的迭代器赋值给kv
    	{
        
    		cout << kv.first << ":" << kv.second << endl;
    	}
    }

[322a15bb58944208ac67d852c44089c8.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/ddb52409423c48c3ba3ab0225148a3f9.jpeg
[592669665a5348d598319e2039a108cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/3978fb3e32f14accb1e20a9588ca351a.png
[eb8a8e60933b4a4ba73e4995ffbddaab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/37cd950cf225467ea19471de66aa9bd1.png
[faadb2bd266f41dfb94f2dc66056ac2e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/cc5e92330ab04fecab64542d0e4c1448.png
[2b39ac2497f741358a1e2214af4b0180.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/8e7a2b54ff7349c4a86a033c819c189b.png
[1c757bddb0dd4e55a60639593cd56b3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/74de988476c142c990cc69d17d8ee05b.png
[e5d55c4e64f84d34a43c7443e8492971.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/3ae854af6e6f476eb713c668f53077ea.png
[edb4772f28974357b392a31725fe08d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/bdd9d64efc4e4b75ad59adf29b18862d.png
[Link 1]: https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
[10dd716a02ce497e854777a85901c82d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/7ee13f0db06d4604930190023e0f131f.png
[c97ca0d1a81e4fb792d2874b0ffcb843.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/121bc48d94f944ab8a23418d62c9f00b.png
[94547f05b59a420c9d75e6c742cadb63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/11ebe077ad7b471b9621d8926ce1d96b.png
[9ce25c545bad4ff687f6c55d7c2174cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/78fffddd398b4632b624a4a655a21d8e.png
[bc9994caa40a4aa79b02987d6da1a60a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/5f1ed05fbbda442b99c646e56e888de4.png
[ab72a316bb874325bbbb94aabb71b065.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/d1ccf6f88e244fa3b7203837dff4c7b8.png