C++哈希表模拟实现unordered_map 与unordered_set

哈希概念

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

顺序结构以及平衡树 中，元素关键码与其存储位置之间没有对应的关系，因此在 查找一个元素
时，必须要经过关键码的多次比较
理想的搜索方法：可以 不经过任何比较 ， 一次 直接从表中得到要搜索的元素
哈希/散列：关键值与存储位置，建立一个关联关系
哈希 ( 散列 ) 方法：通过某种函数(hashFunc) 使元素的存储位置与它的关键值之间能够建立
一一映射的关系，那么在查找时 通过该函数 可以 很快找到该元素
哈希方法中：使用的转换函数称作 哈希(散列)函数 ，构造出来的结构 称 为 哈希表 (Hash Table)(or 散列表 )
向该结构中：
插入元素： 根据待插入元素的 关键码 ，以此 函数计算出 该元素的 存储位置 并按此位置进行存放
搜索元素： 根据待插入元素的 关键码 ，以此 函数计算出 该元素的 存储位置， 在结构中按此位置取元素比较，若关键码相等，则搜索成功

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

如若再插入99，则会发生哈希冲突

哈希冲突 

不同关键字 通过相同哈希函数计算出 相同的哈希地址 ，该种现象称为哈希冲突 或哈希碰撞 。

 

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

常见哈希函数 

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为随机数函数 
通常应用于关键字长度不等时采用此法
总之，哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突解决

两种方法：闭散列和开散列

闭散列（开放定址法）

当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有 空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

寻找下一个空位置：hashi为元素使用哈希函数映射出的地址

1. 线性探测 hashi+i (i>=0)

2. 二次探测 hashi+i^2 (i>=0)

线性探测：

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

插入：通过哈希函数获取待插入元素在哈希表中的位置

           如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突

           则使用线性探测找到下一个空位置，插入新元素

删除 ：采用伪删除法

采用闭散列处理哈希冲突时， 不能随便物理删除 哈希表中已有的元素，若直接删除元素
会影响其他元素的搜索 。比如删除元素 4 ，如果直接删除掉，则下标为4的空间为空，当查找44时，直接就是找到了一个空位置，查找结束，找不到，但实际上元素44是应该要被搜索成功的
响。因此 线性探测采用标记的 伪删除法 来删除一个元素 。 
    enum Status//标记存储值的状态
	{
		EMPTY,//空
		EXIST,//存在
		DELETE//删除
	};

哈希表设计代码（开放定址法/闭散列解决哈希冲突）

哈希表的扩容问题：

负载因子：存储关键字个数/空间大小，当负载因子为0.7时就扩容

开散列（链地址法/开链法/拉链法)

首先对关键码集合用散列函数 计算散列地址 ，具有 相同地址的关键码归于 同一子集合，每一个子集合称为 一个桶 ，各个桶中的元素通过一个 单链表链接 起来

开散列中每个桶中放的都是发生哈希冲突的元素

哈希表（开散列解决哈希冲突）模拟实现unordered_map 与unordered_set

HashTable.h

#pragma once
#include<string>
#include<vector>
#include<iostream>
using namespace std;

template<class K>
struct  HashFunc  // 哈希函数采用除留余数法，被模的key必须要为整形才可以处理
{
	size_t operator()(const K& key)
	{
		 return (size_t)key;
	}
};

template<>
struct HashFunc<string>//将字符串映射成一个整型 （若key为字符串）
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};


namespace hash_bucket//开散列/拉链法
{
	template<class T>
	struct  HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

	// 前置声明
	template<class K, class T, class Hash, class KeyOfT>
	class HashTable;

	template<class K, class T, class Ref,class Ptr,class Hash, class KeyOfT>
	struct __HTIterator
	{
		typedef  HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
		Node* _node;
		const HashTable<K, T, Hash, KeyOfT>* _pht;//权限可以平移/缩小，不能放大
		size_t _hashi;

		__HTIterator(Node*node, HashTable<K, T, Hash, KeyOfT>* pht, size_t hashi)
			:_node(node)
			,_pht(pht)
			,_hashi(hashi)
		{}

		//有普通的this( HashTable的this)指针与const修饰的this指针，走更适配的
		__HTIterator(Node* node, const HashTable<K, T, Hash, KeyOfT>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}

		Self& operator++()
		{
			if (_node->_next)//当前桶没走完,还有节点,走到下一个节点
			{
				_node = _node->_next;
			}
			else//当前桶已走完，找下一个桶的起始节点
			{
				++_hashi;
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}
					++_hashi;
				}

				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}
			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}
	};

	// unordered_set -> Hashtable<K, K>
	// unordered_map -> Hashtable<K, pair<K, V>>
	template<class K,class T,class Hash,class KeyOfT>
	class HashTable
	{
		typedef HashNode<T> Node;

		template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>
		friend struct __HTIterator;

	public:

		typedef  __HTIterator<K, T, T&, T*, Hash, KeyOfT> iterator;
		typedef  __HTIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		iterator end()
		{
			return iterator(nullptr,this,-1);
		}

		const_iterator begin()const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}
			return end();
		}

		const_iterator end()const
		{
			return const_iterator(nullptr,this,-1);
		}

		HashTable()
		{
			_tables.resize(10);
		}

		~HashTable()
		{
			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;
			}
		}

		pair<iterator, bool> Insert(const T& data)
		{
			//检查是否已经存在
			Hash hf;//将关键字转成/映射成一个整型  （data可以为int，可以为string）
			KeyOfT kot;//取出data中的关键字，data若为Key则就是它本身，data若为pair，则取得pair的第一个元素

			iterator it = Find(kot(data));
			if (it != end())
				return make_pair(it, false);
			

			//检查是否需要扩容
			// 负载因子最大到1
			if (_n ==_tables.size())
			{
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				//遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					//挪动映射至新表
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hf(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}


			size_t hashi = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode,this,hashi), true);
		}

		iterator Find(const K& key)
		{
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this,hashi);
				}
				cur = cur->_next;
			}
			return end();
		}

		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)//第一个就是要找的
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

MyUnorderedMap.h

#pragma once
#include"HashTable.h"

namespace djx
{
	template<class K,class V,class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)//获取关键字
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>,  Hash, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

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

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

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

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		hash_bucket::HashTable<K, pair<const K, V>,  Hash, MapKeyOfT> _ht;
	};
}

MyUnorderedSet.h

#pragma once
#include"HashTable.h"

namespace djx
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		// 对类模板取内嵌类型，加typename告诉编译器这里是类型
		typedef typename hash_bucket::HashTable<K, K, Hash, SetKeyOfT>::const_iterator  iterator;
		typedef typename hash_bucket::HashTable<K, K, Hash, SetKeyOfT>::const_iterator  const_iterator;

		const_iterator begin() const
		{
			return _ht.begin();
		}

		const_iterator end() const
		{
			return _ht.end();
		}

		pair<const_iterator, bool> insert(const K& key)
		{
			auto ret = _ht.Insert(key);
			return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
		}
		
		iterator find(const K& key)
		{
			auto ret = _ht.Find(key);
			return const_iterator(ret._node, ret._pht, ret._hashi);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

测试：

void test_set()
{
	djx::unordered_set<int> us;
	us.insert(4);
	us.insert(19);
	us.insert(62);
	us.insert(3);

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

	auto e = us.find(19);
	cout << *e << endl;

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

void test_map()
{
	djx::unordered_map<string, string> dict;
	dict.insert(make_pair("sort", ""));
	dict.insert(make_pair("string", ""));
	dict.insert(make_pair("insert", ""));
	for (auto& kv : dict)
	{
		//kv.first += 'x';不可以修改K
		kv.second += 'x';

		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

	string arr[] = { "苹果","葡萄","葡萄","甜瓜"};
	djx::unordered_map<string, int> count_map;
	for (auto& e : arr)
	{
		count_map[e]++;
	}

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

	count_map.erase("苹果");
}

一些代码设计的细节：

 

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

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

相关文章

php二次开发股票系统代码：腾讯股票数据接口地址、批量获取股票信息、转换为腾讯接口指定的股票格式

php二次开发股票系统代码：腾讯股票数据接口地址、批量获取股票信息、转换为腾讯接口指定的股票格式

1、腾讯股票数据控制器 <?php namespace app\index\controller;use think\Model; use think\Db;const BASE_URL http://aaaaaa.aaaaa.com; //腾讯数据地址class TencentStocks extends Home { //里面具体的方法 }2、请求接口返回内容 function juhecurl($url, $params f…
阅读更多...
Linux/Uinx 系统编程：进程管理（1）

Linux/Uinx 系统编程：进程管理（1）

Linux/Uinx 系统编程&#xff1a;进程管理&#xff08;1&#xff09; 文章目录 Linux/Uinx 系统编程&#xff1a;进程管理&#xff08;1&#xff09;什么是进程进程来源INIT 和 守护进程登录进程sh进程进程的执行模式进程管理的系统调用关于syscall中参数b&#xff0c;c&#x…
阅读更多...
HCIP 三层交换

HCIP 三层交换

拓扑图&IP划分如下&#xff1a; 第一步&#xff0c;配置IP 以R1为例&#xff0c;R2同理 LSW1&#xff0c;LSW2同理 第二步&#xff0c;聚合链路 LSW1&#xff0c;LSW2同理 修改串口 LSW1&#xff0c;LSW2同理 第三步&#xff0c;配置生成树 LSW1&#xff0c;LSW2同理 …
阅读更多...
听力下降为什么会影响到言语感知？

听力下降为什么会影响到言语感知？

一、听力障碍对阈值、听觉频率范围和分辨能力的影响 听力障碍使得听障者的听敏度降低&#xff0c;提高了阈值&#xff0c;不利于言语信号的接收。听障者听力阈值的变化在不同频率并不相同&#xff0c;一般而言&#xff0c;高频部分的听力损失往往大于低频部分&#xff0c;而言…
阅读更多...
代码随想录刷题笔记-Day11

代码随想录刷题笔记-Day11

1. 逆波兰表达式求值 150. 逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/ 给你一个字符串数组 tokens &#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意&a…
阅读更多...
区块链技术在教育领域的应用：Web3教育变革

区块链技术在教育领域的应用：Web3教育变革

随着Web3时代的来临&#xff0c;区块链技术在各个领域都展现出了巨大的潜力&#xff0c;而在教育领域&#xff0c;区块链的应用正引领着一场教育变革。本文将深入探讨区块链技术在教育领域的创新应用&#xff0c;以及这一应用如何推动Web3时代的教育变革。 1. 学历和成绩的去中…
阅读更多...
Shell脚本⑤函数与数组

Shell脚本⑤函数与数组

一.函数 封装的可重复利用的具有特定功能的代码 格式&#xff1a; 方法一&#xff1a; [function] 函数名 (){ 命令序列 [return x] #使用return或者exit可以显式的结束函数 } 方法二&#xff1a; 函数名(){ 命令序列 } 1.函数的调用方法 &#xff08;1&…
阅读更多...
【K8S 云原生】K8S的安全机制

【K8S 云原生】K8S的安全机制

目录 一、K8S安全机制概述 1、概念 2、请求apiserver资源的三个步骤&#xff1a; 一、认证&#xff1a;Anthentcation 1、认证的方式&#xff1a; 1、HTTP TOKEN&#xff1a; 2、http base&#xff1a; 3、http证书&#xff1a; 2、认证的访问类型&#xff1a; 3、签发…
阅读更多...
【Power Platform】实现让审批人可以修改其他人提交的表单中的部分字段

【Power Platform】实现让审批人可以修改其他人提交的表单中的部分字段

之前我们分享的案例里&#xff0c;我提了一嘴我们的客户有一个需求&#xff0c;就是审批人要有能力修改其他人表单中的部分字段。 今天我们就来分享一下如何实现这个功能。 要实现这个效果&#xff0c;我们需要判断三个值——当前审批人是不是当前登录人、当前审批节点可以修…
阅读更多...
基于python京东商品数据采集与可视化分析大屏设计与实现

基于python京东商品数据采集与可视化分析大屏设计与实现

随着电子商务行业的快速发展&#xff0c;京东作为中国最大的综合性电商平台之一&#xff0c;拥有海量的商品数据。对这些数据进行采集与分析&#xff0c;能够帮助企业了解市场趋势、消费者需求以及产品销售情况&#xff0c;为决策提供科学依据。 本文旨在基于京东商品数据的采…
阅读更多...
Linux设备树中的 gpio 信息

Linux设备树中的 gpio 信息

一. 简介 前面几篇文章讲解了 pinctrl 子系统&#xff0c; pinctrl 子系统重点是设置 PIN( 有的 SOC 叫做 PAD) 的复用 和电气属性。 注意&#xff1a;如果 pinctrl 子系统将一个 PIN 复用为 GPIO 的话&#xff0c;那么接下来就要用到 gpio 子系统了。如果 PIN用作其他…
阅读更多...
若依微服务框架 上传文件（文件表）

若依微服务框架 上传文件（文件表）

若依微服务得上传文件只有在头像那里才有&#xff0c;而且存储得是地址。 如果想要进行文件表存储&#xff0c;只能自己进行封装。 若依微服务框架 上传文件&#xff08;文件表&#xff09; 一、问题二、代码1.组件代码2、调用 一、问题 若依在上传文件这里使用了watch监听&a…
阅读更多...
Webpack5 基本使用 - 1

Webpack5 基本使用 - 1

Webpack 是什么 webpack 的核心目的是打包&#xff0c;即把源代码一个一个的 js 文件&#xff0c;打包汇总为一个总文件 bundle.js。 基本配置包括mode指定打包模式&#xff0c;entry指定打包入口&#xff0c;output指定打包输出目录。 另外&#xff0c;由于 webpack默认只能打…
阅读更多...
R语言批量把数值变量和因子变量的互转

R语言批量把数值变量和因子变量的互转

#我们以rms包的lung数据集为例 library(rms) data<-lung #这里有两种方法&#xff0c; #第1是知道需要转化的变量在哪几列&#xff1b; #第2知道需要转化的变量名 str(data) #假设我们想转化inst/status/sex/三个变量的类型 #图1先看看变量类型和处于第几列 str(dat…
阅读更多...
【C++11并发】mutex 笔记

【C++11并发】mutex 笔记

简介 在多线程中往往需要访问临界资源&#xff0c;C11为我们提供了mutex等相关类来保护临界资源&#xff0c;保证某一时刻只有一个线程可以访问临界资源。主要包括各种mutex&#xff0c;他们的命名大都是xx_mutex。以及RAII风格的wrapper类&#xff0c;RAII就是一般在构造的时…
阅读更多...
VRRP6协议--负载均衡配置

VRRP6协议--负载均衡配置

VRRP6负载均衡 VRRP6负载均衡指的是创建多个备份组，多个备份组同时承担数据转发的任务，对于每一个备份组，都有自己的Master和若干Backup设备。 VRRP6负载分担与VRRP6主备备份的基本原理和报文协商过程都是相同的。同样对于每一个VRRP6备份组，都包含一个Master设备和若干Ba…
阅读更多...
蓝桥杯备战——7.DS18B20温度传感器

蓝桥杯备战——7.DS18B20温度传感器

1.分析原理图 通过上图我们可以看到DS18B20通过单总线接到了单片机的P14上。 2.查阅DS18B20使用手册 比赛的时候是会提供DS18B20单总线通讯协议的代码&#xff0c;但是没有提供读取温度数据的代码&#xff0c;所以还是需要我们去查看手册&#xff0c;我只把重要部分截下来了 …
阅读更多...
幻兽帕鲁搭建私服，一键更新方法

幻兽帕鲁搭建私服，一键更新方法

看着帕鲁这么火&#xff0c;估计更新会变为常态了&#xff0c;如果有自己搭建私服的话&#xff0c;跟着我下面的方法去进行更新吧&#xff01; 如果你还没有自己的私服&#xff0c;快去三五十搞一个吧&#xff0c;只需三五分钟&#xff0c;叫上你的小伙伴一起去搞起来吧 只需3分…
阅读更多...
计算机网络体系架构认知--网络协议栈

计算机网络体系架构认知--网络协议栈

文章目录 一.计算机网络分层架构各协议层和计算机系统的联系从整体上理解计算机网络通信计算机网络通信的本质 二.Mac地址,IP地址和进程端口号三.局域网通信与跨局域网通信局域网通信跨局域网通信全球互联的通信脉络 四.网络编程概述 一.计算机网络分层架构 实现计算机长距离网…
阅读更多...
25考研每日的时间安排

25考研每日的时间安排

今天要给大家分享一下25考研每日的时间安排。 没有完美的计划&#xff0c;只有合适的计划。 仅供参考 很多人说复习不要只看时长而是要看效率&#xff0c;所以学多长时间不重要&#xff0c;重要的高效率完成任务。 完美的计划 这个计划看起来很完美&#xff0c;从早到晚有学习…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站