您现在的位置是：首页 >学无止境 >【C++】STL——用一个哈希表封装出unordered_map和unordered_set网站首页学无止境

【C++】STL——用一个哈希表封装出unordered_map和unordered_set

beyond->myself 2023-05-19 04:00:04
简介【C++】STL——用一个哈希表封装出unordered_map和unordered_set

用一个哈希表(桶)封装出unordered_map和unordered_set

在这里插入图片描述

文章目录

一、哈希表源码

根据先前对unordered_map和unordered_set的学习，我们得知其底层是借助哈希表来实现的，接下来我们会使用上篇博客实现的开散列哈希表来模拟实现unordered_map和unordered_set，哈希表源代码链接：

Hash/Hash/HashBucket.h · wei/cplusplus - 码云 - 开源中国 (gitee.com)

下面我们对哈希表进行改造，使其能够很好的封装unordered_map与unordered_set。

二、哈希函数模板参数的控制

我们都清楚unorderded_map是KV模型，而unordered_set是K模型，而先前实现的哈希表(桶)是pair键值对的KV模型，很显然不适用unordered_set的K模型，因此要实现一个泛型，这就需要我们对哈希表的模板参数进行控制。

更改哈希节点的模板参数：

  • 为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数设为T，如果后续传入节点的类型为K模型，则T为K模型，若为pair键值对KV模型，则为KV模型

image-20230414200938920

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	//构造函数
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

更改哈希表的模板参数：

  • 这里我们把第二个模板参数设为T，便于识别后续传入的数据类型
//unordered_map -> HashTable<K, pair<K, V>> _ht;
//unordered_set -> HashTable<K, K> _ht;
template<class K, class T, class Hash = HashFunc<K>>

unordered_set的参数控制：

  • 如果上层使用的是unordered_set容器，那么哈希表的参数对应的就是K，K类型。
template<class K>
class unordered_set
{
private:
	HashBucket_realize::HashBucket<K, K, Hash, SetKeyOfT> _hb;
};

unordered_map的参数控制：

  • 如果上层使用的是unordered_map容器，那么哈希表的参数对应的就是K，pair<K, V>类型。
template<class K, class V>
class unordered_map
{
private:
	HashBucket_realize::HashBucket<K, pair<const K, V>, Hash, MapKeyOfT> _hb;
};

三、对上层容器构建仿函数便于后续映射

在哈希映射的过程中，我们需要获得元素的键值，然后通过对应的哈希函数计算获得映射的地址，上一步为了适配unordered_set和unordered_map，我们对模板参数进行了整改，现在哈希节点存储的数据类型是T，T可能是一个键值，也可能是一个键值对，底层的哈希并不知道传入的数据是啥类型，因此我们需要对上层容器套一层仿函数来告诉底层哈希。

unordered_set的仿函数：

  • 针对于unordered_set这种K类型的容器，我们直接返回key即可。
template<class K>
class unordered_set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	HashBucket_realize::HashBucket<K, K, Hash, SetKeyOfT> _hb;
};

注意：

虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。

unordered_map的仿函数：

  • unordered_map的数据类型是pair键值对，我们只需要取出其键值对中的第一个数据key然后返回即可。
template<class K, class V>
class unordered_map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	HashBucket_realize::HashBucket<K, pair<const K, V>, Hash, MapKeyOfT> _hb;
};

注意：

现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

更改底层哈希的模板参数：

  • 上层容器的仿函数已经套好，下面需要整改下底层哈希的模板参数来接收上层容器的数据类型。
template<class K, class T, class Hash, class KeyOfT>
class HashBucket

  • 第一个参数K：key的类型就是K。查找函数是根据key来查找的，所以需要K。

  • 第二个参数T：哈希表结点存储的数据类型。比如int，double，pair,string等。

  • 第三个参数KeyOfT：拿到T类型(结点数据类型)的key。

  • 第四个参数Hash：表示使用的哈希函数

四、string类型无法取模问题

  • 字符串无法取模，是哈希问题中最常见的问题。

经过上面的分析后，我们让哈希表增加了一个模板参数，此时无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值。

但是在我们日常编写的代码中，用字符串去做键值key是非常常见的事，比如我们用unordered_map容器统计水果出现的次数时，就需要用各个水果的名字作为键值。

而字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。

但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。

鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法。

因此，现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型。

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashBucket

若是上层没有传入该仿函数，我们则使用默认的仿函数，该默认仿函数直接返回键值key即可，但是用字符串作为键值key是比较常见的，因此我们可以针对string类型写一个类模板的特化，此时当键值key为string类型时，该仿函数就会根据BKDRHash算法返回一个对应的整型。

template<class K>
struct Hash
{
	size_t operator()(const K& key) //返回键值key
	{
		return key;
	}
};
//string类型的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

五、哈希表默认成员函数实现

1.构造函数

哈希表中有两个成员变量，当我们实例化一个对象时：

  • _table会自动调用vector的默认构造函数进行初始化。
  • _n会根据我们所给的缺省值被设置为0。
vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数

我们写一个构造函数，并且用素数表的第一个数据初始化相应的空间。

//构造函数
//HashBucket() = default; //显示指定生成默认构造函数
HashBucket()
	:_n(0)
{
	//_tables.resize(10);
	_tables.resize(__stl_next_prime(0));
}

注意：

如果我们不初始化空间，我们就不需要编写构造函数，使用默认生成的构造函数就足够了，但是由于我们后面需要编写拷贝构造函数，编写了拷贝构造函数后，默认的构造函数就不会生成了，此时我们需要使用default关键字显示指定生成默认构造函数。

2.拷贝构造函数

哈希表在拷贝时需要进行深拷贝，否则拷贝出来的哈希表和原哈希表中存储的都是同一批结点。

哈希表的拷贝构造函数实现逻辑如下：

  1. 将哈希表的大小调整为ht._table的大小。
  2. 将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中。
  3. 更改哈希表当中的有效数据个数。
//拷贝构造函数
HashBucket(const HashBucket& hb)
{
	//1、将哈希表的大小调整为hb._tables的大小
	_tables.resize(hb._tables.size());
	//2、将hb._tables每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝）
	for (size_t i = 0; i < hb._tables.size(); i++)
	{
		if (ht._tables[i]) //桶不为空
		{
			Node* cur = hb._tables[i];
			while (cur) //将该桶的结点取完为止
			{
				Node* copy = new Node(cur->_data); //创建拷贝结点
				//将拷贝结点头插到当前桶
				copy->_next = _tables[i];
				_tables[i] = copy;
				cur = cur->_next; //取下一个待拷贝结点
			}
		}
	}
	//3、更改哈希表当中的有效数据个数
	_n = hb._n;
}

3.赋值运算符重载函数

实现赋值运算符重载函数时，可以通过参数间接调用拷贝构造函数，之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可，当赋值运算符重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了。

//赋值运算符重载函数
HashBucket& operator=(HashBucket hb)
{
	//交换哈希表中两个成员变量的数据
	_table.swap(hb._table);
	swap(_n, hb._n);

	return *this; //支持连续赋值
}

4.析构函数

因为哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可。

//析构函数
~HashBucket()
{
	//将哈希表当中的结点一个个释放
	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; //将该哈希桶置空
	}
}

六、哈希表底层迭代器的实现

1.迭代器基本框架

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中除了存放节点指针外，还都应该存储一个哈希表的地址。最后写个构造函数，初始化_ node和_hb。

你会发现这样一个现象，迭代器里面用了哈希表，哈希表里用了迭代器，也即两个类互相引用

  • 如果迭代器写在哈希表前面，那么编译时编译器就会发现哈希表是无定义的（编译器只会往前/上找标识符）。

  • 如果哈希表写在迭代器前面，那么编译时编译器就会发现迭代器是无定义的。

这里我们的迭代器的位置放在了哈希表（HashBucket）的上面，而我迭代器内部又使用了HashBucket，因为编译器是向上寻找，按照此位置摆放，迭代器的类里是找不到HashBucket的，所以我们需要把HashBucket的类在迭代器前面进行声明。

// 哈希表前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashBucket;
//正向迭代器
template<class K, class T, class Hash, class KeyOfT>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希节点的类型
	typedef __HTIterator<K, T, Hash, KeyOfT> Self; //正向迭代器的类型
	typedef HashBucket<K, T, Hash, KeyOfT> HB; // 哈希表

	Node* _node; // 节点指针
	HB* _hb; // 哈希表地址
	// 构造函数
	__HTIterator(Node* node, HB* hb);
	// *运算符重载
	T& operator*();
	// ->运算符重载
	T* operator->();
	//==运算符重载
	bool operator==(const Self& s) const;
	//!=运算符重载
	bool operator!=(const Self& s) const;
	//++运算符重载
	Self& operator++();
    
    Self& operator++(int);
};

2.++运算符重载

假设此时的哈希表结构如图所示：

image-20230412001629135

注意这里是一个哈希桶结构，每一个桶都是一串单链表，在单个桶中，我们拿到头节点指针，可以挨个遍历++it走完这个链表，但是这是多串单链表，我们需要保证在一个桶走完后要到下一个桶去，因此在++运算符重载的设定上要按照如下规则：

  • 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
  • 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。
//++运算符重载
Self& operator++()
{
	if (_node->_next)
	{
		_node = _node->_next;
	}
	else//当前桶已经走完，需要到下一个不为空的桶
	{
		KeyOfT kot;//取出key数据
		Hash hash;//转换成整型
		size_t hashi = hash(kot(_node->_data)) % _hb->_tables.size();
        ++hashi;
		while(hashi < _hb->_tables.size())
        {
			if (_hb->_tables[hashi])//更新节点指针到非空的桶
			{
				_node = _hb->_tables[hashi];
				break;
			}
            else
            {
                hashi++;
            }
		}
		//没有找到不为空的桶，用nullptr去做end标识
		if (hashi == _hb->_tables.size())
		{
			_node = nullptr;
		}
	}
	return *this;
}

// 后置++
Self& operator++(int) 
{
	Self tmp = *this;
	operator++();
	return tmp;
	}

由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_ tables，而 _tables成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
	//把迭代器设为HashTable的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend class __HTIterator;

	typedef HashNode<T> Node;//哈希结点类型
public:
	//……
}

注意：哈希表的迭代器是单向迭代器，没有–运算符重载。

3.== 和 != 运算符重载

比较两迭代器是否相等，只需要判断两迭代器所封装的节点是否是同一个即可。

//!=运算符重载
bool operator!=(const Self& s) const
{
	return _node != s._node;
}
//==运算符重载
bool operator==(const Self& s) const
{
	return _node == s._node;
}

4.* 和 -> 运算符重载

  • *运算符返回的是哈希节点数据的引用
  • ->运算符返回的是哈希节点数据的地址
//*运算符重载
T& operator*()
{
	return _node->_data;//返回哈希节点中数据的引用
}
//->运算符重载
T* operator->()
{
	return &(_node->_data);//返回哈希节点中数据的地址
}

七、哈希表的begin和end

这里我们需要进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。typedef之后，就可以实现begin()和end()的函数了。

template<class K, class T, class KeyOfT, class Hash>
class HashBucket
{
 //把迭代器设为HashTable的友元
	template<class K, class T, class KeyOfT, class Hash>
	friend class __HTIterator;

	typedef HashNode<T> Node;//哈希结点类型
public:
	typedef __HTIterator<K, T, KeyOfT, Hash> iterator;//正向迭代器的类型
}

begin()：

  1. 遍历哈希表，返回第一个不为空的桶的第一个节点的迭代器位置，借助正向迭代器的构造函数完成，还得传this指针（哈希表的指针）
  2. 若遍历结束没找到，说明哈希表里没有一个是空，直接返回end()尾部的迭代器位置。
//begin
iterator begin()
{
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		//找到第一个不为空的桶的节点位置
		if (cur)
		{
			return iterator(cur, this);
		}
	}
	return end();
}

end()：

  • 哈希表的end()直接返回迭代器的构造函数（节点指针为空，哈希表指针为this）即可。
//end()
iterator end()
{
	return iterator(nullptr, this);
}

八、哈希表的优化（素数表）

在除留余数法时，最好模一个素数，这样模完后不会那么容易出现哈希冲突的问题，因此我们可以专门写一个素数表来解决。

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] =
	{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
	};
    
	// 获取比prime大那一个素数
	for (int 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];
}

九、插入操作和[ ]运算符重载

  • unordered_map的数据类型是KV模型，其插入的是一个pair键值对，这里要区别于unordered_set，实现方式也有所区别。

image-20230412135747114

unordered_set插入的是key值，我们这里要对它们insert的返回值做出修改：

image-20230412141428667

image-20230412141713301

因为unordered_set没有[]运算符重载，所以不必提供该函数，只有在 unordered_map 中提供此函数。

  1. 首先调用insert函数插入键值对返回迭代器ret
  2. 通过返回的迭代器ret调用元素值value

注意：键值对的第一个参数为用户传入的 key 值，第二个参数是用户声明的第二个模板参数的默认构造函数。

//[]运算符重载
V& operator[](const K& key)
{
	pair<iterator, bool> ret = insert(make_pair(key, V()));
	return ret.first->second;
}

接下来我们要对哈希表的 Insert 的返回值进行改动，进而契合 unordered_map 的 pair 数据类型。改动有两处，如下：

image-20230412142818310

十、哈希表(修改版)源码链接

修改完善后的哈希表源代码链接：
HashBucket.h · wei/cplusplus - 码云 - 开源中国 (gitee.com)

十一、unordered_set、unordered_map的模拟实现代码

1.unordered_set的代码

#pragma once
#include "HashBucket.h"

namespace unordered_set_realize
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename HashBucket_realize::HashBucket<K, K, Hash, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _hb.begin();
		}

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

		pair<iterator, bool> insert(const K& key)
		{
			return _hb.Insert(key);
		}

	private:
		HashBucket_realize::HashBucket<K, K, Hash, SetKeyOfT> _hb;
	};

	void test_unordered_set()
	{
		unordered_set<int> us;
		us.insert(13);
		us.insert(3);
		us.insert(23);
		us.insert(5);
		us.insert(5);
		us.insert(6);
		us.insert(15);
		us.insert(223342);
		us.insert(22);

		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : us)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

2.unordered_map的代码

#pragma once
#include "HashBucket.h"

namespace unordered_map_realize
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename HashBucket_realize::HashBucket< K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
	
		iterator begin()
		{
			return _hb.begin();
		}

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

		pair<iterator, bool> insert(const pair<K, V>& data)
		{
			return _hb.Insert(data);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _hb.Insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		HashBucket_realize::HashBucket<K, pair<const K, V>, Hash, MapKeyOfT> _hb;
	};

	void test_unordered_map()
	{
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜",
			"苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

		unordered_map<string, int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}

		for (const auto& kv : countMap)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
	}
}

参考博客：

1、STL详解（十三）—— 用一个哈希表同时封装出unordered_map和unordered_set_2021 dragon

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐