【数据结构】哈希表的开散列和闭散列模拟

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

哈希思想


在顺序和树状结构中,元素的存储与其存储位置之间是没有对应关系,因此在查找一个元素时,必须要经过多次的比较。

顺序查找的时间复杂度为0(N),树的查找时间复杂度为log(N)。

我们最希望的搜索方式:通过元素的特性,不需要对比查找,而是直接找到某个元素。

这一个通过key与存储位置建立一一的思想就是hash思想。

哈希表就是基于哈希思想的一种具体实现。哈希表也叫散列表,是一种数据结构。无论有多少条数据,插入和查找的时间复杂度都是O(1),因此由于其极高的效率,被广泛使用。

建立映射关系:
例如集合{8,5,6,3,7,2,1,0}

key为每个元素的值,capaticy为哈希表元素的容量。

【数据结构】哈希表的开散列和闭散列模拟,数据结构,散列表,数据结构,哈希算法

映射过程:
元素8   key=8  8%10=8 映射在数组下标为第8的位置上

元素7   映射在下标为7的位置上

  1. 直接定值法:(关键数范围集中,量不大的时候)关键字和存储位置是一一对应,不存在哈希冲突
  2. 除留余数法:(关键字很分散,量很大)关键字和存储位置是一对多的关系,存在哈希冲突

哈希冲突

对于两个数据元素的关键字  和  (i != j),有  !=  ,但有:Hash() == Hash(),即:不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞

例如上述的举例:
key的值为 18  15的时候

hashi计算的方法得出 需要映射到8 和5的位置上,但是8 和5的位置已经存在其它值。这就产生了冲突


哈希冲突的解决

1.开放定址法(闭散列)

a:线性探测

        如果发生冲突,就往后一次一步寻找为空的位置。

b:二次探测

        发生冲突,每次往后走俩步,寻找没有冲突的位置。

线性探测的缺点:容易产生成片的冲突

二次探测的缺点:虽然解决了容易产生成片冲突,但是空间利用率也不高

2.开散列

又称开链法、哈希桶,计算如果产生了哈希冲突,就以链表的形式将冲突的值链接起来。

【数据结构】哈希表的开散列和闭散列模拟,数据结构,散列表,数据结构,哈希算法


哈希表的闭散列实现

闭散列哈希中的,每个位置不仅需要存储数据,还需要标注状态,方便查找删除。

enum State { EMPTY, EXIST, DELETE };


标记状态的意义?

在一个哈希表中,如果需要存放,我们会计算出key映射位置。如果key映射位置被占走,会往后继续寻找到删除/空的位置放置。

在查找时,在映射位置找不到时,需要往后寻找,我们不可能一直往后寻找O(N).,那就失去哈希表的价值,当我们遇到存在/删除位置时继续往后寻找,直到找到空位置,说明没有该元素。

因此在存储时,每个位置都必须有状态和数据

		struct Elem
		{
			pair<K, V> _val;
			State _state;
		};

框架

希表还需要维持容量的问题。因此需要_size表示实际存放,来维持负载因子

template<class K,class V> //k—v结构
class HashTable	
{
public:
//...
private:
	vector<Elem> _ht;
	size_t _size;		//实际存储
	size_t _totalSize;  // 哈希表中的所有元素:有效和已删除, 扩容时候要用到
};

哈希表的插入

  1. 根据K查找是为空,是则返回false
  2. 计算负载因子,是否需要扩容
  3. 插入新元素
  4. 更新位置状态,有效数目增加

扩容的方法

  • 开新的哈希表(默认空间为原来的2倍)
  • 遍历旧表,调用哈希表的插入。
  • 交换俩个表。

【数据结构】哈希表的开散列和闭散列模拟,数据结构,散列表,数据结构,哈希算法

		// 插入
		bool Insert(const pair<K, V>& val)
		{
			if (Find(val.first) != -1)
				return false;
 
			//负载因子为7时,扩容
			if ((_size * 10) / _ht.size() == 7)
			{
				size_t newsize = _ht.size() * 2;
				HashTable<K, V>newht;
				newht._ht.resize(newsize);
				//遍历旧表
				for (size_t i = 0; i < _ht.size(); i++)
				{
					if (_ht[i]._state == EXIST)
						newht.Insert(_ht[i]._val);
				}
				_ht.swap(newht._ht);
			}
 
			//出入新元素
			size_t hashi = HashFunc(val.first);
			while (_ht[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _ht.size();
			}
			_ht[hashi]._val = val;
			_ht[hashi]._state = EXIST;
 
			++_size;
			++_totalSize;
 
			return true;
		}

哈希表的查找

通过hash函数映射到hashi,往后一直比对,遇到存在比对,不是要找的val就往后需要,遇到删除也往后对比。直到遇到空返回。

		// 查找
		size_t Find(const K& key)
		{
			size_t hashi = HashFunc(key);
			while (_ht[hashi]._state != EMPTY)
			{
				if (_ht[hashi]._state == EXIST
					&& _ht[hashi]._val.first == key)
				{
					return hashi;
				}
				++hashi;
				hashi %= _ht.size();
			}
			return -1;
		}

哈希表的删除

删除是比较简单,是一种伪删除,不需要对数据清楚,只需要修改状态为删除,减少有效个数

  1. 调用find,没有则返回flase
  2. 修改为状态
  3. 减少个数
		bool Erase(const K& key)
		{
			int hashi = Find(key);
			if (hashi == -1)	return false;
 
			_ht[hashi]._state = DELETE;
			--_size;
			return true;
		}

这三部分就是闭散列的主体结构。需要维持负载因子和状态。

Gitee: 闭散列哈希代码


哈希桶


开散列哈希表就不要需要状态的使用,是由一个链表的数组构成。

就是一排一排的桶。想要查找数据,只需要映射位置,在桶中寻找,是O(1)的放法.

特别极端情况下可能达到O(N)。

框架


底层可以依赖单链表,只需要简单的头插即可。

链表的结点:需要包含下一个位置的指针,需要包含pair键值对

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

同样需要记录表中有效元素的个数,但是一般情况下,负载因子在80%-90%效率最大

我们为了简单实现,在100%时才扩容。 

template<class K, class V>
class HashTable
{
public:
	//...
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数
};

哈希桶的插入

  1. 检查是否为已经存在的Key
  2. 检查负载因子,为1就扩容
  3. 往hashi位置头插插入
  4. 修改个数

扩容的方法

  1. rasize一个二倍数量的原表
  2. 遍历旧表,将一个元素从链表的头取下,插入到新表中的hashi位置上。注意保存下一个位置!
  3. 交换俩张表

【数据结构】哈希表的开散列和闭散列模拟,数据结构,散列表,数据结构,哈希算法

		bool Inset(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}
 
			hash hf;
 
			//扩容
			if (_tables.size() == _n)
			{
				size_t newsize = _tables.size() * 2;
				vector<Node*> newtable;
				newtable.resize(newsize, nullptr);
				for (size_t i = 0; i < (_tables.size()); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hf(cur->_kv.first % newtable.size());
						
						//头插
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;
 
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtable);
			}
 
			size_t hashi = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return true;
		}

哈希桶的查找

  • 计算hashi
  • 遍历单链表
  • 为空则返回flase
		Node* Find(const K& key)
		{
			hash fc;
			size_t hashi = fc(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur=cur->_next;
			}
			return nullptr;
		}

哈希桶的删除

删除需要主要是删除的中间结点还是首结点

需要保存父亲结点

和单链表的删除基本一致

		bool Erase(const K& key)
		{
			hash fc;
			size_t hashi = fc(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				//找到了
				if (cur->_kv.first == key)
				{
					//头删
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
 
				}
			}
			return false;
		}

 Gitee: 开散列哈希桶代码


关于仿函数HashFunc

仿函数是一种回调,可以定义出函数对象。

是对不同类型转化为key,之前在位图就已经介绍,本文用的是BDK算法

对于string字符串类型会有存在冲突,但是可以通过不同的算法映射到不到的位置上,通过几个值的比对能减少失误的概率。

template<class K>
struct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
 
//特化 针对字符串
template<>
struct DefaultHash<string>
{
	size_t operator()(const string& key)
	{
		//BKDR
		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};

 文章来源地址https://www.toymoban.com/news/detail-834565.html

 

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

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

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

相关文章

  • C++王牌结构hash:哈希表开散列(哈希桶)的实现与应用

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

    2024年04月17日
    浏览(35)
  • 数据结构哈希表(散列) 之Hash

    声明: 此文章仅限于记录学习之用 , 受限于自身水平和理解能力 , 因此结论可能是不正确的. 如果您需要学习,建议参考其他文章 看了下网上一些大佬的教程, 写的云山雾绕的. 简单总结下吧. 以言简意赅为主. hash 就是把任意输入通过算法生成一个int值. 这个值就是放数据的地址

    2024年02月21日
    浏览(46)
  • 【C++】哈希——unordered系列容器|哈希冲突|闭散列|开散列

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

    2024年01月17日
    浏览(38)
  • 【C++】哈希表:开散列和闭散列

    📝 个人主页 :超人不会飞) 📑 本文收录专栏 :《C++的修行之路》 💭 如果本文对您有帮助,不妨 点赞、收藏、关注 支持博主,我们一起进步,共同成长! 在前面的文章中,我们学习了红黑树,其查找数据的效率很高,查找的次数最差是树的高度logN次,并且要进行多次比

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

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

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

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

    2024年02月08日
    浏览(46)
  • Java学数据结构(4)——散列表Hash table & 散列函数 & 哈希冲突

    1.散列表,key,散列函数; 2.哈希冲突的解决; 3.string中的hashCode; 查找树ADT,它允许对元素的集合进行各种操作。本章讨论散列表(hash table)ADT,不过它只支持二叉查找树所允许的一部分操作。散列表的实现常常叫作散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和

    2024年02月10日
    浏览(52)
  • 数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)

    目录 开放地址法(Open Addressing) 线性探测(Linear Probing) 散列表查找性能分析 平方探测(Quadratic Probing)  定理 平方探测法的查找与插入 双散列探测法(Double Hashing)  再散列(Rehashing) 分离链接法(Separate Chaining) 平均查找次数 分离链接法的散列表实现 常用处理冲突的

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

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

    2024年02月08日
    浏览(56)
  • C++利用开散列哈希表封装unordered_set,unordered_map

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

    2024年03月24日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包