哈希桶的模拟实现【C++】

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

哈希冲突解决

闭散列 (开放定址法)

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

如何寻找“下一个位置”
1、线性探测
发生哈希冲突时,从发生冲突的位置开始,依次向后探测,直到找到下一个空位置为止

Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . )

H0:通过哈希函数对元素的关键码进行计算得到的位置。
Hi:冲突元素通过线性探测后得到的存放位置
m:表的大小。

举例:
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中,当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入,插入过程如下:

使用除留余数法
1%10 =1 ,111 %10 =1
即111和1发生了哈希冲突 ,所以111找到1的下一个空位置插入
哈希桶的模拟实现【C++】,哈希算法,c++,散列表

将数据插入到有限的空间,那么空间中的元素越多,插入元素时产生冲突的概率也就越大,冲突多次后插入哈希表的元素,在查找时的效率必然也会降低。
介于此,哈希表当中引入了负载因子(载荷因子):

负载因子 = 表中有效数据个数 / 空间的大小
不难发现:
负载因子越大,产出冲突的概率越高,查找的效率越低
负载因子越小,产出冲突的概率越低,查找的效率越高

负载因子越小,也就意味着空间的利用率越低,此时大量的空间都被浪费了。对于闭散列(开放定址法)来说,负载因子是特别重要的因素,一般控制在0.7~0.8以下
采用开放定址法的hash库,如JAVA的系统库限制了负载因子为0.75,当超过该值时,会对哈希表进行增容

线性探测的缺点:一旦发生冲突,所有的冲突连在一起,容易产生数据“堆积”,即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要多次比较(踩踏效应),导致搜索效率降低
2、二次探测

二次探测为了避免该问题,找下一个空位置的方法为

Hi=(H0+i ^2 )%m ( i = 1 , 2 , 3 , . . . )

H0:通过哈希函数对元素的关键码进行计算得到的位置
Hi:冲突元素通过二次探测后得到的存放位置
m:表的大小

相比线性探测而言,二次探测i是平方,采用二次探测的哈希表中元素的分布会相对稀疏一些,不容易导致数据堆积

template <class K>
struct  DefaultHashFunc
{
	size_t operator() (const K& key)
	{
		return (size_t)key;
	}
};

template <>
struct DefaultHashFunc<string>
{
	size_t  operator() (const string& str)
	{
		//BKDR,将输入的字符串转换为哈希值
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

namespace open_address 
{
	enum  STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};


	struct StringHashFunc
	{
		size_t operator()(const string& str)
		{
			return str[0];
		}
	};

	//template<class K, class V>
	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);
		}
		bool insert(const pair<K, V> kv)
		{
			//扩容 
			if ((double)_n / (double)_table.size() >= 0.7)
			{
				HashTable<K, V>  newHT;
				size_t newSize = _table.size() * 2;
				newHT._table.resize(newSize);
				//遍历旧表的数据,将旧表的数据重新映射到新表中

				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.insert(_table[i]._kv);//插入的写成kv不行?
					}

				}
				_table.swap(newHT._table);
			}





			//线性探测

			HashFunc hf;

			size_t  hashi = hf(kv.first) % _table.size();

			//如果该位置没有元素,则直接插入元素 ,如果该位置有元素,找到下一个空位置,插入新元素
			while (_table[hashi]._state == EXIST)//不是EMPTY和DELETE这两种情况
			{
				++hashi;
				hashi %= _table.size();
			}
			//是EMPTY和DELETE这两种情况
			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<const K, V>* Find(const K& key)
		{
			HashFunc hf;
			//线性探测 
		//如果该位置没有元素,则直接插入元素 ,如果该位置有元素,找到下一个空位置,插入新元素
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY) //DELETE和EXIST
			{
				if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
				{
					return  (HashData<const K, V>*) & _table[hashi];
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			//先找到
			HashData<const K, V>* ret = Find(key);
			//再删除 
			if (ret != nullptr)
			{
				ret->_state = DELETE;
				_n--;
				return true;
			}
			//没找到 
			return false;
		}
	public:
		vector<HashData<K, V>> _table;
		size_t  _n = 0; //存储有效数据的个数

	};

}

闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷

开散列 (链地址法、哈希桶)

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

举例:
用除留余数法将序列{1,111,4,7,15,25,44,9}插入到表长为10的哈希表中,当发生哈希冲突时我们采用开散列的方式进行插入,插入过程如下:
哈希桶的模拟实现【C++】,哈希算法,c++,散列表
将相同哈希地址的元素通过单链表链接起来,然后将链表的头结点存储在哈希表中的方式,不会影响与自己哈希地址不同的元素的增删查改的效率,因此开散列的负载因子相比闭散列而言,可以稍微大一点

闭散列的开放定址法,负载因子不能超过1,一般建议控制在[0.0, 0.7]

开散列的哈希桶,负载因子可以超过1,一般建议控制在[0.0, 1.0]

在实际中,开散列的哈希桶结构比闭散列更实用,主要原因有两点:
哈希桶的负载因子可以更大,空间利用率高
哈希桶在极端情况下还有可用的解决方案

开散列实现(哈希桶)

哈希表的结构
struct HashNode
	{
		pair<K, V>  _kv;
		HashNode<K,V>* _next;
		HashNode(  const pair<K, V> & kv)
			:_kv(kv)
			,_next(nullptr)
		{
			
		}
	};
Insert
	bool Insert(const pair<K,V> & kv)
		{
			
			size_t hashi = kv.first % _table.size();
			//负载因子到1就扩容 
			if (_n == _table.size())
			{
				size_t 	newsize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newsize, nullptr);

			
				//遍历旧表,将原哈希表当中的结点插入到新哈希表
				for (int i = 0; i <= _table.size(); i++)
				{
					Node* cur = _table[i];
					//插入到新哈希表
					while (cur != nullptr)
					{
						Node* next = cur->_next;
						// 重新分配hashi
						size_t hashi = cur->_kv.first % _table.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

				}
			}
	
			//头插 
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			return true;
		}

哈希桶的模拟实现【C++】,哈希算法,c++,散列表

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

哈希桶的模拟实现【C++】,哈希算法,c++,散列表

		bool Erase(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					  if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删
					  {
						_table[hashi] = cur->_next;
					  }
					  else//第一种情况 ,cur是头节点
					  {
						  prev->_next = cur->_next;
					  }
					  delete cur;
					return  true; 
				}
				prev = cur;
				cur = cur->_next;
			}
		

			//没找到 
			return false;
		}
namespace hash_bucket
{
	template <class K ,class V> 
	struct HashNode
	{
		pair<K, V>  _kv;
		HashNode<K,V>* _next;
		HashNode(  const pair<K, V> & kv)
			:_kv(kv)
			,_next(nullptr)
		{
			
		}
	};
	template<class K,class V> 
	class HashTable
	{
	public:
		typedef HashNode<K,V>  Node;

		//iterator begin()
		//{

		//}
		//iterator end()
		//{

		//}
		//const_iterator begin()
		//{

		//}
		//const_iterator end()
		//{

		//}
		//GetNextPrime()
		//{

		//}
		HashTable()
		{
			_table.resize(10, nullptr);
		}
		~HashTable()
		{

		}
		//bool Insert(const pair<K, V>  kv)
		//{
		//	//负载因子到1就扩容 
		//	if (_n == _table.size())
		//	{
		//		size_t 	newsize = _table.size() * 2;
		//		vector<Node*> newtable;
		//		newtable.resize(newsize, nullptr);
		//	}
		//	size_t hashi = kv.first % _table.size();
		//	//头插 
		//	Node* newnode = new Node(key);
		//	newnode->_next = _table[hashi];
		//	_table[hashi] = newnode;
		//	++_n;
		//	return true;
		//}
		bool Insert(const pair<K,V> & kv)
		{
			
			size_t hashi = kv.first % _table.size();
			//负载因子到1就扩容 
			if (_n == _table.size())
			{
				size_t 	newsize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newsize, nullptr);

			
				//遍历旧表,将原哈希表当中的结点插入到新哈希表
				for (int i = 0; i <= _table.size(); i++)
				{
					Node* cur = _table[i];
					//插入到新哈希表
					while (cur != nullptr)
					{
						Node* next = cur->_next;
						// 重新分配hashi
						size_t hashi = cur->_kv.first % _table.size();
						cur->_next = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

				}
			}
	
			//头插 
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			return true;
		}

		Node *   Find(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Erase(const K & key)
		{
			size_t hashi = key % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur != nullptr)
			{
				if (key == cur->_kv.first)
				{
					  if(prev==nullptr)//第二种情况 ,prev是nullptr ,就是头删
					  {
						_table[hashi] = cur->_next;
					  }
					  else//第一种情况 ,cur是头节点
					  {
						  prev->_next = cur->_next;
					  }
					  delete cur;
					return  true; 
				}
				prev = cur;
				cur = cur->_next;
			}
		

			//没找到 
			return false;
		}
		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur != nullptr)
				{
				
					cout << cur->_kv.first << "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}
	private:
		vector<Node*> _table;//指针数组
		size_t  _n = 0;//存储有效数据

	};
}

如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!
文章来源地址https://www.toymoban.com/news/detail-779263.html

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

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

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

相关文章

  • 【C++】哈希unordered系列容器的模拟实现

    开散列又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,即 key 映射的下标位置,具有相同地址的关键码 (哈希冲突) 归于同一子集合,每一个子集合称为一个桶 (哈希桶),各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中;也就

    2024年02月13日
    浏览(37)
  • 【C++进阶】哈希表开散列和闭散列的模拟实现(附源码)

    这里的闭散列和开散列解决哈希冲突的方法都是 除留余数法 。 一些哈希函数:字符串哈希算法 闭散列:也叫 开放定址法 ,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有 空位置,那么可以 把key存放到冲突位置中的“下一个” 空位置中去 。 如何找到

    2024年02月08日
    浏览(58)
  • 【C++】用哈希桶模拟实现unordered_set和unordered_map

    顺序结构中(数组)查找一个元素需要遍历整个数组,时间复杂度为O(N);树形结构中(二叉搜索树)查找一个元素,时间复杂度最多为树的高度次logN。理想的搜索方法: 可以不经过任何比较,一次直接从表中得到要搜索的元素。 构造一种存储结构, 通过某种函数使元素的

    2024年04月11日
    浏览(52)
  • 【数据结构(C++版)】哈希表(散列表)

    目录   1. 散列表的概念 2. 散列函数的构造方法 2.1 直接定址法 2.2 除留余数法 2.3 数字分析法 2.4 平方取中法 3. 处理冲突的方法 3.1 开放定址法 3.1.1 线性探测法 3.1.2 平方探测法 3.1.3 双散列法 3.1.4 伪随机序列法 3.2 拉链法(链接法) 4. 散列查找及性能分析 5. 哈希的应用 5.1 位

    2024年02月15日
    浏览(46)
  • HELLO算法笔记之散列表(哈希)

    一、哈希表 建立键  key  与值  value  之间的映射,实现高效的元素查询。输入一个key,以O(1)获取对应的value 遍历: 知识点1、哈希函数: 将一个较大的输入空间映射到一个较小的输出空间。在哈希表中,输入空间是所有  key  ,输出空间是所有桶(数组索引)。换句话

    2024年02月10日
    浏览(37)
  • 数据结构算法设计——哈希表(散列表)

            哈希表 又叫 散列表 ,他们两个是同一个东西,本文全文采用“散列表”的叫法。散列表的本质其实就是一个 数组 ,他的作用就像使用数组时一样,输入下标可以得到对应元素,散列表可以实现 输入一个的时候得到这个的地址信息 。 下面是百科给出

    2024年02月03日
    浏览(60)
  • 【数据结构与算法】04 哈希表 / 散列表 (哈希函数、哈希冲突、链地址法、开放地址法、SHA256)

    一种很好用,很高效,又一学就会的数据结构,你确定不看看? 莫慌,每个概念都很好理解。 哈希表( Hash Table ),也称为 散列表 ,是一种数据结构, 用于存储键值对(key-value pairs) 。 键值对是一种数据结构,用于将键(key)与对应的值(value)相关联。在键值对中,键

    2024年02月09日
    浏览(80)
  • 【LeetCode 算法】Walking Robot Simulation 模拟行走机器人 - 哈希

    机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands : -2 :向左转 90 度 -1 :向右转 90 度 1 = x = 9 1 = x = 9 1 = x = 9 :向前移动 x 个单位长度 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位

    2024年02月15日
    浏览(39)
  • 【哈希的模拟实现】

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( l o g 2 N log_2 N l o g 2 ​ N ),搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方

    2024年02月08日
    浏览(25)
  • 哈希表的简单模拟实现

    初识哈希 哈希表是一种查找效率及其高的算法,最理想的情况下查询的时间复杂度为O(1)。 unordered_map 容器通过 key 访问单个元素要比 map 快,但它通常在遍历元素子集的范围迭代方面效率 较低。 unordered 系列的关联式容器之所以效率更高,是因为底层采用了哈希的结构。 哈希

    2024年02月15日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包