【C++进阶】哈希表开散列和闭散列的模拟实现(附源码)

这篇具有很好参考价值的文章主要介绍了【C++进阶】哈希表开散列和闭散列的模拟实现(附源码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这里的闭散列和开散列解决哈希冲突的方法都是除留余数法

一些哈希函数:字符串哈希算法

一.闭散列

概念

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

如何找到下一个位置?

线性探测

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

  • 线性探测优点:实现非常简单。
  • 线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。

模拟实现

闭散列是用一个数组实现的,每一个位置都有三种状态

  1. EMPTY :表示此位置为空
  2. EXIST:表示此位置存在数据
  3. DELETE:表示此位置处于删除状态

当我们去查找数据时,直到找到空才停止,如果哈希冲突非常多,那么很可能数组里的空位置非常少,此时查找效率大幅下降,还有可能把数组填满了,没有空位置,就陷入了死循环,所以需要扩容。

那么何时扩容?扩容的时机不合适可能导致空间浪费或是效率降低。

我们可以加一个负载因子,负载因子表示有效数据的个数,当 负载因子/数组容量  大于等于 0.7 时,此时是扩容的最佳时机

插入

  • 利用哈希函数,获取需要插入的位置
  • 如果该位置状态为 EXIST, 那么继续向后探测,直到找到状态为空的位置
  • 【C++进阶】哈希表开散列和闭散列的模拟实现(附源码),C++进阶,散列表,哈希算法,数据结构,c++,开发语言

已经知道扩容时机了,那么具体该如何扩容?

采用旧表映射到新表的方式,最后再把旧表和新表交换一下即可。

  • 首先创建一个新表
  • 遍历旧表,调用新表的 Insert 把旧表的有效数据插入到新表中
  • 交换旧表与新表 

删除

闭散列的删除不能直接删,而是采用伪删除的方式,即把给位置的1状态置为DELETE 

源码

//哈希表闭散列线性探测实现
namespace Close_Hash
{
    //哈希函数
	template<class K>
	class HashFunc
	{
	public:
		size_t operator()(const K& val)
		{
			return val;
		}
	};

	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& s)
		{
			const char* str = s.c_str();
			unsigned int seed = 131; // 31 131 1313 13131 131313
			unsigned int hash = 0;
			while (*str)
			{
				hash = hash * seed + (*str++);
			}

			return hash;
		}
	};
    //枚举变量,表示状态信息
	enum State 
	{ 
		EMPTY, 
		EXIST, 
		DELETE 
	};

	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		State _state=EMPTY;  //初始状态下,每个位置都是空
	};

	template<class K,class V,class HF=HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(5);  //初始化数组
		}

		//查找
		bool Find(const K& key)
		{
			HF hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._kv.first == key)
					return true;
				hashi++;
			}
			return false;
		}

		//插入
		bool Insert(const pair<K, V>& kv)
		{
			HF hf;
			if (Find(kv.first) == true)
				return false;
			if (_n * 10 / _table.size() >= 7)  //判断是否需要增容
			{
				size_t newsize = 2 * _table.size();
				// 遍历旧表,重新映射到新表
				HashTable<K, V, HF> newTable;    //创建新表
				newTable._table.resize(newsize);   //初始化新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newTable.Insert(_table[i]._kv);
					}
				}
			
				_table.swap(newTable._table);   //交换新旧表
			}
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._state ==EXIST)
			{
				hashi++;
				hashi = hashi % _table.size();
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			_n++;

			return true;

		}

		// 删除
		bool Erase(const K& key)
		{
			if (Find(key) == false)
				return false;
			HF hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY&&hashi<_table.size())
			{
				if (_table[hashi]._kv.first == key)
				{
					_table[hashi]._state = DELETE;  //删除只需要把该位置的状态置为DELETE
					return true;
				}
				hashi++;
			}
			return false;
		}

		size_t Size()const
		{
			return _n;
		}

		bool Empty() const
		{
			return _n == 0;
		}

		void Swap(HashTable<K, V>& ht)
		{
			swap(_n, ht._n);
			ht._table.swap(_table);
		}

	private:
		vector<Node> _table;
		size_t _n;   //负载因子
	};
}

二.开散列

概念

开散列就是我们平时说的哈希桶。

开散列:又叫链地址法(开链法)

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

开散列的每一个位置挂着一个单链表,这个单链表称为桶,每个桶里放的都是冲突的数据。

【C++进阶】哈希表开散列和闭散列的模拟实现(附源码),C++进阶,散列表,哈希算法,数据结构,c++,开发语言

模拟实现

插入

  • 利用哈希函数,找到插入位置
  • 接下来就是单链表的插入,推荐使用头插,单链表的头插效率是 O(1)

同样需要扩容。

当哈希桶里的数据满了时,开始扩容,仍然使用旧表遍历到新表的方式。

源码

namespace OpenHash
{
    //哈希函数
	template<class T>
	class HashFunc
	{
	public:
		size_t operator()(const T& val)
		{
			return val;
		}
	};

	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& s)
		{
			const char* str = s.c_str();
			unsigned int seed = 131; // 31 131 1313 13131 131313
			unsigned int hash = 0;
			while (*str)
			{
				hash = hash * seed + (*str++);
			}

			return hash;
		}
	};

	template<class K>   //节点
	struct HashBucketNode
	{
		HashBucketNode<K>* _pNext;
		K _data;

		HashBucketNode(const K& data)
			: _pNext(nullptr)
			, _data(data)
		{}
	};

	// 本文所实现的哈希桶中key是唯一的
	template<class K,class HF = HashFunc<K>>
	class HashBucket
	{
		typedef HashBucketNode<K> Node;
		typedef HashBucket<K,HF> Self;
	public:

		HashBucket()
		{
			_table.resize(10, nullptr);
			_size = 0;
		}

		~HashBucket()
		{
			Clear();
		}

		// 哈希桶中的元素不能重复
		bool Insert(const K& data)
		{
			if(Find(data)!=nullptr)
                return false;
			HF hf;
			if (_size == _table.size())    //扩容
			{
				size_t newsize = 2 * _table.size();
				vector<Node*> newtable(newsize, nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_pNext;
						size_t hashi = hf(data) % newsize;
						Node* newnode = new Node(cur->_data);
						if (newtable[hashi] == nullptr)
							newtable[hashi] = newnode;
						else
						{
							newnode->_pNext = newtable[hashi]->_pNext;
							newtable[hashi]->_pNext = newnode;
						}
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
			}
			Node* newnode = new Node(data);
			size_t hashi = hf(data) % _table.size();
			if (_table[hashi] == nullptr)
				_table[hashi] = newnode;
			else
			{
				newnode->_pNext = _table[hashi]->_pNext;
				_table[hashi]->_pNext = newnode;
			}
			_size++;
			return true;
		}

		 //删除哈希桶中为data的元素(data不会重复)
		bool Erase(const K& data)
        {
	        HF hf;
	        size_t hashi = hf(data) % _table.size();
	        Node* cur = _table[hashi];
	        Node* prev = nullptr;
	        if (cur->_data == data)
	        {
		        delete  _table[hashi];
		        _table[hashi] = cur->_pNext;
		        return true;
	        }
	        while (cur)
	        {
		        if (cur->_data == data)
		        {
			        prev->_pNext = cur->_pNext;
			        delete cur;
			        cur = nullptr;
			        return true;
		        }
		        prev = cur;
		        cur = cur->_pNext;
	        }
	        return false;
        }

		bool Find(const K& data)
		{
			HF hf;
			size_t hashi = hf(data) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_data == data)
					return true;
				else
					cur = cur->_pNext;
			}
			return false;
		}

		size_t Count(const K& data) const
		{
			HF hf;
			size_t hashi = hf(data) % _table.size();
			Node* cur = _table[hashi];
			size_t ret = 0;
			while (cur)
			{
				if (cur->_data == data)
					ret++;
				cur = cur->_pNext;
			}
			return ret;
		}

		size_t size()const
		{
			return _size;
		}

		bool empty()const
		{
			return 0 == _size;
		}

		void Clear()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_pNext;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}

			_table.resize(0);
		}

		size_t BucketCount()const
		{
			return _table.capacity();
		}

		size_t BucketSize() const
		{
			return _table.size();
		}

		void Swap(Self& ht)
		{
			_table.swap(ht._table);
			swap(_size, ht._size);
		}

	private:
		size_t HashFunc(const T& data)
		{
			return HF()(data) % _table.capacity();
		}
	private:
		vector<Node*> _table;
		size_t _size;      // 哈希表中有效元素的个数
	};
}

三.开散列与闭散列比较


应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。

事实上:
由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <=0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间


🐬🤖本篇文章到此就结束了, 若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻

😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩

😍😁谢谢你的阅读。😸😼文章来源地址https://www.toymoban.com/news/detail-715561.html

到了这里,关于【C++进阶】哈希表开散列和闭散列的模拟实现(附源码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】哈希——unordered系列容器|哈希冲突|闭散列|开散列

    在C++98中,STL提供了底层为 红黑树结构 的一系列关联式容器,在查询时效率可达到 log2N,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的

    2024年01月17日
    浏览(38)
  • C++王牌结构hash:哈希表开散列(哈希桶)的实现与应用

    目录 一、开散列的概念 1.1开散列与闭散列比较 二、开散列/哈希桶的实现 2.1开散列实现 哈希函数的模板构造 哈希表节点构造 开散列增容 插入数据 2.2代码实现 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集

    2024年04月17日
    浏览(35)
  • 【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]

    在现代计算机科学和数据结构中,哈希(Hash)是一项重要而广泛应用的技术。通过将输入数据映射为固定长度的哈希值,哈希函数能够快速高效地进行数据存储、搜索和比较。然而,由于输入数据的多样性和哈希值的有限长度,哈希冲突成为了一个不可避免的问题。本文将介

    2024年02月08日
    浏览(45)
  • 【C++杂货铺】一文带你走进哈希:哈希冲突 | 哈希函数 | 闭散列 | 开散列

    在 C++98 中,STL 提供了底层为红黑树结构的一些列关联式容器,在查询时效率可以达到 O ( l o g 2 N ) O(log2^N) O ( l o g 2 N ) ,即最差情况下需要比较红黑树高度次,当树中的结点非常多的时候,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在

    2024年02月08日
    浏览(50)
  • 【数据结构】哈希表——闭散列 | 开散列(哈希桶)

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希(Hash):是一种方法,将数据的key值和存储位置建立关系。 在之前学习过的顺序结构以及平衡树中,所有数据的key值和存储位置之间都没有对应的关系。所以在查找一个数据

    2023年04月24日
    浏览(45)
  • 【C++】开散列哈希表封装实现unordered_map和unordered_set

    在未达成目的之前,一切具有诱惑力的事物都显得那么不堪一击 1. 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。 最好的查询是

    2023年04月09日
    浏览(84)
  • C++利用开散列哈希表封装unordered_set,unordered_map

    1.之前我们已经实现了开散列的哈希表,今天我们来用它封装unordered_set,unordered_map 2.本文的封装比利用红黑树封装set和map更加复杂 建议大家先去看我的红黑树封装set和map再来看本文 因为有很多地方跟红黑树封装set和map时是同样的思路和方法,所以本文不会太去赘述一遍 因为un

    2024年03月24日
    浏览(55)
  • 【数据结构】万字一文手把手解读哈希————(开/闭散列)解决哈希冲突完整详解(6)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(127)
  • Learning C++ No.25【开散列封装unordered_set和unordered_map】

    北京时间:2023/5/29/7:05,上星期更文一篇,且该篇博客在周三就写完了,所以充分体现,咱这个星期摆烂充分,哈哈哈!现在的内心情感没有以前那么从容了,这次摆的时间是有点久了,但本质影响不大,因为我现在还在码字,三天不学习,或者说是没有踏实学习,目前给我

    2024年02月07日
    浏览(43)
  • 【C++】哈希/散列详细解析

    前言:上篇文章介绍了unordered_set和unordered_map序列关联式容器,它们之所以效率比较高,是因为其底层使用了哈希结构。,所以这篇文章我们就来详细讲解一下哈希表。有关unordered序列关联式容器的知识,请移步至这篇文章:unordered_map与unordered_set(系列关联式容器) 顺序结

    2024年02月06日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包