哈希表——unordered_set和unordered_map的封装

 个人主页：敲上瘾-CSDN博客

个人专栏：游戏、数据结构、c语言基础、c++学习、算法

        在本章关于哈希表的设计在这里就随便提一点不再过多的讲解，而把重点放在封装部分。

目录

一、哈希表的设计

1.模板参数的设计 

二、迭代器封装

1.迭代器简单功能

2.迭代器++

三、HashTable内部设计

四、外层的封装

1.My_unordered_map.h的封装

2.My_unordered_set.h的封装

五、源码

1.Hash.h

2.My_unordered_map.h

3. My_unordered_set.h

一、哈希表的设计

        哈希函数：就是让数据与储存位置建立一种映射关系，通过这种映射关系就能够快速找到某个数据储存的位置。

        哈希冲突：不同的数据可能会映射到同一块区域，那么先储存的数据存到了该位置，后储存的数据的位置就被占用了，这两个数据产生哈希冲突。

        在哈希表的设计中哈希函数的设计和哈希冲突的处理是非常重要的，它们两个的设计会直接影响到哈希表的效率，哈希函数的设计有很多的方式，如：除法散列法、乘法散列法、全域散列法。哈希冲突的处理有：开发定址法（包括：线性探测、二次探测、双重散列）、链地址法。

在本章中选用的是除法散列法和链址法。

说明1：

注1：为方便读者阅读并理解，以下所展示的模板参数部分均已省略

struct HashNode//哈希节点
{
	T _data;
	HashNode<T>* _next;
	//......
};
struct HashFun//哈希函数
struct HTIterator//迭代器
{
	//......
	Node* _it;
	HT* _ht;
};
class HashTable//哈希表
{
public:
	//......
private:
	vector<Node*> _tables; 
	size_t _n = 0;			// 数据个数
};

说明2：

b04a5ca8e5f04daca1af3502ef997e1b.png

1.模板参数的设计 

        哈希函数用的是除法散列法，也就是对一个数据的key与数组的长度取余，这个余数就是这个数据需要储存的对应下标位置。

要点：要能取余这个数必须是整数，又因为要把余数作为下标，那么这个余数必须是非负整数。

        因为我们做的是模板要兼容各种内置类型和外置类型，所以有必要设计一个哈希函数，把这数据转换成size_t类型。

        又考虑这个数据可能是pair<key,val>类型或其他结构体类型等，所以需要设计一个函数来确定key是谁。

f574e2b16fed43c29f424a02545ae999.png所以在哈希表的设计中作一个这样的模板声明。

  • K：传入的数据中key的类型，因为在查找和删除时是依据key来完成的，所以必须单独知道key的类型。
  • T： 数据的类型
  • KeyOfT：通过仿函数来取到key值
  • Hash：通过仿函数把key值转化为size_t类型

        为了兼容多种类型，在哈希桶的内部实现中，映射时都需要用KeyOfT和Hash，具体实现请参照下面的源码，就不再做详细讲解。 

二、迭代器封装

        哈希表的迭代器实现和list的迭代器类似，还是比较复杂的所以我们把它单独封装成一个类模板，那么迭代器的成员变量必然就是哈希节点，但是考虑到当一个哈希节点走到当前哈希桶的空时，无法找到下一个哈希桶的起始位置，所以迭代器的成员变量还需要添加一个哈希表，这个问题就可以解决。

        为了兼容const迭代器，有一个很实用的小技巧，在迭代器模板参数里添加Ref和Ptr，给Ref和Ptr传入T&和T*就能实现普通迭代器，传入const T&和const T*就能实现const迭代器      

所以模板参数如下：

e76589c155f94782bd7cb68b68e97b1f.png

        因为迭代器中成员变量存了哈希表所以模板参数必须有K，T，KeyOfT，Hash。考虑需要兼容const迭代器所以增加Ref和Ptr模板参数。

准备工作如下：

12d7526a27b2408bae741f882f44e0f1.png

1.迭代器简单功能

Ref operator*()
{
	return _it->_data;
}
Ptr operator->()
{
	return &_it->_data;
}
bool operator!=(Self it)
{
	return it._it != _it;
}

2.迭代器++

        对于哈希桶结构它实际就是一个链表数组，上文已经提过，为了使迭代器走到一个链表结尾时方便找到另一个链表的开头，所以迭代器模板中引入了一个哈希表的成员。

对于迭代器++我们分两种情况考虑：        

  • 该迭代器不是链表的尾节点：直接让迭代器移动到该链表的下一个节点即可，
  • 该迭代器是链表的尾节点：可以通过哈希映射找到当前迭代器所在的哈希桶，然后从这个哈希桶开始往后找，直到找到头结点不为空的节点为止，该节点即为迭代器++后的结果。

解释：链表的尾节点——next为空的那个节点

代码演示：

Self& operator++()
{
	if (_it->_next)
	{
		_it = _it->_next;
		return *this;
	}
	KeyOfT kot;
	Hash hash;
	size_t index = hash(kot(_it->_data)) % _ht->_tables.size();
	index++;
	while (index < _ht->_tables.size() && !_ht->_tables[index]) index++;
	if (index == _ht->_tables.size()) _it = nullptr;
	else _it = _ht->_tables[index];
    return *this;
}

注意：以上操作访问了哈希表的成员，如果该成员是私有需要在哈希表内把HashIterator做一个友元声明。

三、HashTable内部设计

关于迭代器我们通常都会有普通迭代器和const迭代器，所以有一下设计：

1e3335d7e97d436f8cb258b3adb8cd39.png

  • 迭代器begin：第一个非空的哈希桶的头
  • 迭代器end：使用nullptr充当

如下：

//普通迭代器
Iterator Begin()
{
	for (int i = 0; i < _tables.size(); i++)
		if (_tables[i] != nullptr) return Iterator(_tables[i], this);
	return Iterator(nullptr, this);
}
Iterator End()
{
	return Iterator(nullptr, this);
}
//const迭代器
ConstIterator Begin() const
{
    for (int i = 0; i < _tables.size(); i++)
	    if (_tables[i] != nullptr) return Iterator(_tables[i], this);
	return Iterator(nullptr, this);
}
ConstIterator End() const
{
	return Iterator(nullptr, this);
}

四、外层的封装

1.My_unordered_map.h的封装

e66aa6be520749e48faf048dc6f86a86.png

        如上为了后续方便操作，我们再次对迭代器重命名，但要注意加typename表明是成员变量，而不是成员函数。 My_unordered_map的成员变量只要一个哈希表就行。

        有了上面的铺垫后My_unordered_map的基本功能和迭代器实现就显得十分简单在这里就不再细讲，我会在文尾分享源码。

注：以上Hash.h中的各种类模板均已放置到 hash_bucket 命名空间中。

2.My_unordered_set.h的封装

0950152382064c6680117e6dbfedcc9a.png

关于My_unordered_set的封装逻辑和My_unordered_map是一模一样的就不细讲。

非常感谢您能耐心读完这篇文章。倘若您从中有所收获，还望多多支持呀！74c0781738354c71be3d62e05688fecc.png

五、源码

1.Hash.h

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	template<class K>
	struct HashFun
	{
		size_t operator()(K key)
		{
			return (size_t)key;
		}
	};
	template<>
	struct HashFun<string>
	{
		size_t operator()(string key)
		{
			size_t hash = 0;
			for (auto val : key) hash += val * 131;
			return hash;
		}
	};
	//前置声明
	template<class K, class T, class KeyOfT, class Hash = HashFun<K>>
	class HashTable;
	template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
		typedef HTIterator<K, T, KeyOfT, Hash, Ref, Ptr> Self;
		HTIterator(Node* it,HT* ht)
			:_it(it)
			,_ht(ht)
		{}
		Ref operator*()
		{
			return _it->_data;
		}
		Ptr operator->()
		{
			return &_it->_data;
		}
		Self& operator++()
		{
			if (_it->_next)
			{
				_it = _it->_next;
				return *this;
			}
			KeyOfT kot;
			Hash hash;
			size_t index = hash(kot(_it->_data)) % _ht->_tables.size();
			index++;
			while (index < _ht->_tables.size() && !_ht->_tables[index]) index++;
			if (index == _ht->_tables.size()) _it = nullptr;
			else _it = _ht->_tables[index];
			return *this;
		}
		bool operator!=(Self it)
		{
			return it._it != _it;
		}

		Node* _it;
		HT* _ht;
	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
	public:
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, KeyOfT, Hash, T&, T*> Iterator;
		typedef HTIterator<K, T, KeyOfT, Hash, const T&, const T*> ConstIterator;
	 
		template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
		friend struct HTIterator;
		//friend Iterator;错误的友元声明
		//friend ConstIterator; 
		Iterator Begin()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i] != nullptr) return Iterator(_tables[i], this);
			}
			return Iterator(nullptr, this);
		}
		Iterator End()
		{
			return Iterator(nullptr, this);
		}
		ConstIterator Begin() const
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				if (_tables[i] != nullptr) return Iterator(_tables[i], this);
			}
			return Iterator(nullptr, this);
		}
		ConstIterator End() const
		{
			return Iterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(11, nullptr);
		}
		// 哈希桶的销毁
		~HashTable()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		// 插入值为data的元素，如果data存在则不插入
		pair<Iterator,bool> Insert(const T& data)
		{
			Hash hash;
			KeyOfT kot;
			pair<Iterator,bool> ret = Find(kot(data));
			if (ret.second == true)
			{
				ret.second = false;
				return ret;
			}
			size_t index = hash(kot(data)) % _tables.size();
			if (_n == _tables.size())
			{
				//扩容
				vector<Node*> newtable(_tables.size() * 2, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						size_t inx = hash(kot(cur->_data)) % newtable.size();
						Node* next = cur->_next;
						cur->_next = newtable[inx];
						newtable[inx] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtable);
			}
			Node* NewNode = new Node(data);
			NewNode->_next = _tables[index];
			_tables[index] = NewNode;
			return { Iterator(NewNode, this),true };
		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false
		pair<Iterator,bool> Find(const K& key)
		{
			Hash hash;
			KeyOfT kot;
			size_t index = hash(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur && kot(cur->_data) != key)
			{
				cur = cur->_next;
			}
			if (!cur) return { Iterator(nullptr, this),false };
			return { Iterator(cur, this),true };
		}

		// 哈希桶中删除key的元素，删除成功返回true，否则返回false
		bool Erase(const K& key)
		{
			if (!Find(key)) return false;
			Hash hash;
			size_t index = hash(key) % _tables.size();
			Node* cur = _tables[index], prev = nullptr;
			while (cur && kot(cur->_data) != key)
			{
				prev = cur;
				cur = cur->_next;
			}
			if (prev == nullptr) _tables[index] = prev; 
			else prev->_next = cur->_next;
			delete cur;
			return true;
		}

	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};
}

2.My_unordered_map.h

#pragma once
#include"Hash.h"
template<class K,class V>
struct MapKeyOfT
{
	K operator()(pair<K,V> data)
	{
		return data.first;
	}
};
template<class K,class V>
class My_unordered_map
{
public:
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT<K,V>, hash_bucket::HashFun<K>>::Iterator iterator;
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT<K,V>, hash_bucket::HashFun<K>>::ConstIterator const_iterator;
	pair<iterator, bool> insert(pair<K, V> kv)
	{
		return _ht.Insert(kv);
	}
	pair<iterator, bool> find(K key)
	{
		return _ht.Find(key);
	}
	bool erase(K key)
	{
		return _ht.Erase(key);
	}
	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}
	const_iterator begin() const
	{
		return _ht.Begin();
	}
	const_iterator end() const
	{
		return _ht.End();
	}
	V& operator[](K key)
	{
		pair<iterator, bool> ret = _ht.Insert({key, V()});
		return ret.first->second;
	}
private:
	hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT<K,V>, hash_bucket::HashFun<K>> _ht;
};

3. My_unordered_set.h

#pragma once
#include"Hash.h"
template<class K>//?????
struct SetKeyOfT
{
	K operator()(K key)
	{
		return key;
	}
};
template<class K>
class My_unordered_set
{
public:
	typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT<K>, hash_bucket::HashFun<K>>::Iterator iterator;
	typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT<K>, hash_bucket::HashFun<K>>::ConstIterator const_iterator;
	pair<iterator, bool> insert(K kv)
	{
		return _ht.Insert(kv);
	}
	pair<iterator, bool> find(K key)
	{
		return _ht.Find(key);
	}
	bool erase(K key)
	{
		return _ht.Erase(key);
	}
	iterator begin()
	{
		return _ht.Begin();
	}
	iterator end()
	{
		return _ht.End();
	}
	const_iterator begin() const
	{
		return _ht.Begin();
	}
	const_iterator end() const
	{
		return _ht.End();
	}
private:
	hash_bucket::HashTable<K, const K,SetKeyOfT<K>, hash_bucket::HashFun<K>> _ht;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/903236.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

理解计算机系统_异常控制流(一):异常

理解计算机系统_异常控制流(一):异常

前言 以<深入理解计算机系统>(以下称“本书”)内容为基础&#xff0c;对程序的整个过程进行梳理。本书内容对整个计算机系统做了系统性导引,每部分内容都是单独的一门课.学习深度根据自己需要来定 引入 异常控制流这章实际上是操作系统的一部分.操作系统简单的…
阅读更多...
驱动学习（三）符号导出

驱动学习（三）符号导出

1.什么是符号&#xff1f; 主要是指全局变量和函数 2.为什么要导出符号&#xff1f; ​ linux内核采用的是模块化的形式管理内核代码。内核中每个模块之间是相互独立的&#xff0c;也就是说A模块的全局变量和函数&#xff0c;B模块是无法访问的。若B模块想要使用A模块中的已有…
阅读更多...
python爬虫——Selenium的基本使用

python爬虫——Selenium的基本使用

目录 一、Selenium的介绍 二、环境准备 1.安装Selenium 2.安装WebDriver 三、元素定位 1.常用定位元素的方法 2. 通过指定方式定位元素 四、窗口操作 1.最大化浏览器窗口 2.设置浏览器窗口大小 3.切换窗口或标签页 切换回主窗口 4. 关闭窗口 关闭当前窗口 关闭所…
阅读更多...
java_方法重载、可变参数、作用域

java_方法重载、可变参数、作用域

方法重载 基本介绍 java 中允许同一个类中&#xff0c;多个同名方法的存在&#xff0c;但要求 形参列表不一致&#xff01; 比如&#xff1a;System.out.println(); out 是 PrintStream 类型 重载的好处 减轻了起名的麻烦减轻了记名的麻烦 案例 public class OverLoad01 …
阅读更多...
SCI一区级 | Matlab实现SSA-TCN-LSTM-Attention多变量时间序列预测

SCI一区级 | Matlab实现SSA-TCN-LSTM-Attention多变量时间序列预测

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.基于SSA-TCN-LSTM-Attention麻雀搜索算法优化时间卷积长短期记忆神经网络融合注意力机制多变量时间序列预测&#xff0c;要求Matlab2023版以上&#xff0c;自注意力机制&#xff0c;一键单头注意力机制替换成多头注…
阅读更多...
leetcode刷题(76-80)

leetcode刷题(76-80)

算法是码农的基本功&#xff0c;也是各个大厂必考察的重点&#xff0c;让我们一起坚持写题吧。 遇事不决&#xff0c;可问春风&#xff0c;春风不语&#xff0c;即是本心。 我们在我们能力范围内&#xff0c;做好我们该做的事&#xff0c;然后相信一切都事最好的安排就可以啦…
阅读更多...
深度生成模型 - 受限玻尔兹曼机（RBM）篇

深度生成模型 - 受限玻尔兹曼机（RBM）篇

前言 受限玻尔兹曼机&#xff08; Restricted Boltzmann Machine&#xff0c;RBM \text{Restricted Boltzmann Machine&#xff0c;RBM} Restricted Boltzmann Machine&#xff0c;RBM&#xff09;是深度学习领域中的一种重要模型&#xff0c;其起源于统计物理学&#xff0c;由…
阅读更多...
【再谈设计模式】单例模式~唯一性的守护者

【再谈设计模式】单例模式~唯一性的守护者

一、引言 在软件工程中&#xff0c;软件开发&#xff0c;设计模式是提高代码复用性和可维护性的有效工具。单例模式&#xff08;Singleton Pattern&#xff09;作为一种创建型设计模式&#xff0c;旨在确保一个类只有一个实例&#xff0c;并提供对该实例的全局访问。这一模式在…
阅读更多...
如何在 Elasticsearch Ruby 客户端中使用 ES|QL Helper

如何在 Elasticsearch Ruby 客户端中使用 ES|QL Helper

作者&#xff1a;来自 Elastic Fernando Briano 了解如何使用 Elasticsearch Ruby 客户端编写 ES|QL 查询并处理其结果。 简介 Elasticsearch Ruby 客户端可用于编写 EQ|QL 查询&#xff0c;使处理从 esql.query 返回的数据更加容易。ES|QL 允许开发人员通过查询过滤、转换和分…
阅读更多...
redis详细教程（3.ZSet，Bitmap，HyperLogLog）

redis详细教程（3.ZSet，Bitmap，HyperLogLog）

ZSet Redis 的 ZSet&#xff08;有序集合&#xff09;是一种特殊的数据类型&#xff0c;它允许存储一系列不重复的字符串元素&#xff0c;并为每个元素关联一个分数&#xff08;score&#xff09;。这个分数用于对集合中的元素进行排序。ZSet 的特点是&#xff1a; 唯一性&am…
阅读更多...
MYSQL-SQL-03-DQL（Data Query Language，数据查询语言）（单表查询）

MYSQL-SQL-03-DQL（Data Query Language，数据查询语言）（单表查询）

DQL&#xff08;数据查询语言&#xff09; DQL英文全称是Data Query Language(数据查询语言)&#xff0c;数据查询语言&#xff0c;用来查询数据库中表的记录。 查询关键字: SELECT 在一个正常的业务系统中&#xff0c;查询操作的频次是要远高于增删改的&#xff0c;当我们去访…
阅读更多...
Cisco Packet Tracer 8.0 路由器的基本配置和Telnet设置

Cisco Packet Tracer 8.0 路由器的基本配置和Telnet设置

文章目录 构建拓扑图配置IP地址配置路由器命令说明测试效果 构建拓扑图 1&#xff0c;添加2811路由器。 2&#xff0c;添加pc0。 3&#xff0c;使用交叉线连接路由器和pc&#xff08;注意线路端口&#xff09;。 4&#xff0c;使用配置线连接路由器和pc&#xff08;注意线路…
阅读更多...
优化网站结构提升用户体验的关键要素

优化网站结构提升用户体验的关键要素

内容概要 在数字时代&#xff0c;网站的架构和用户体验密切相关。一个合理的网站结构不仅能帮助用户快速找到所需信息&#xff0c;还能提升整体的访问满意度。为了达到这一目的&#xff0c;网站需要强调几个关键要素。 首先&#xff0c;清晰的导航设计至关重要。导航应当直观…
阅读更多...
Android Gradle

Android Gradle

#1024程序员节&#xff5c;征文# Gradle 是一款强大的自动化构建工具&#xff0c;广泛应用于 Android 应用开发。它通过灵活的配置和丰富的插件系统&#xff0c;为项目构建提供了极大的便利。本文只是简单的介绍 Gradle 在 Android 开发中的使用&#xff0c;包括其核心概念、构…
阅读更多...
微积分复习笔记 Calculus Volume 1 - 3.8 Implicit Differentiation

微积分复习笔记 Calculus Volume 1 - 3.8 Implicit Differentiation

3.8 Implicit Differentiation - Calculus Volume 1 | OpenStax
阅读更多...
Java——lambda表达式和StreamAPI

Java——lambda表达式和StreamAPI

一、lambda 1. lambda表达式 1.1 Lambda表达式的使用举例: (o1,02)->Integer.compare(o1,o2); 1.2 Lambda表达式的格式举例: Lambda形参列表->lambda 1.3 Lambda表达式的格式 lambda操作符或箭头操作符 的左边:lambda形参列表&#xff0c;对应着要重写的接口中的…
阅读更多...
django游戏门户系统

django游戏门户系统

想做毕业设计但还没有头绪&#xff1f;&#x1f64b;‍♂️django游戏门户系统了解一下&#xff01;这个系统不仅功能全面&#xff0c;还能轻松解决你的项目选题难题&#xff01; 我们这个基于Django开发的游戏门户系统提供了用户注册、登录、内容发布以及管理功能&#xff0c…
阅读更多...
大数据日志处理框架ELK方案

大数据日志处理框架ELK方案

介绍应用场景大数据ELK日志框架安装部署 一&#xff0c;介绍 大数据日志处理框架ELK&#xff08;Elasticsearch、Logstash、Kibana&#xff09;是一套完整的日志集中处理方案&#xff0c;以下是对其的详细介绍&#xff1a; 一、Elasticsearch&#xff08;ES&#xff09; 基本…
阅读更多...
【SQL实验】表的更新和简单查询

【SQL实验】表的更新和简单查询

完整代码在文章末尾 在上次实验创建的educ数据库基础上&#xff0c;用SQL语句为student表、course表和sc表中添加以下记录 【SQL实验】数据库、表、模式的SQL语句操作_创建一个名为educ数据库,要求如下: (下面三个表中属性的数据类型需要自己设计合适-CSDN博客在这篇博文中已经…
阅读更多...
LeetCode反转链表

LeetCode反转链表

题目描述 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#…
阅读更多...
最新文章

Copyright @ 2022~2023