精华内容
下载资源
问答
  • 文章目录前言unordered_map/_set介绍底层结构哈希概念哈希冲突哈希函数哈希冲突解决闭散列开散列开散列增容与插入开散列与闭散列比较模拟实现unordered_set模拟实现unordered_map 前言 在C++98中,STL提供了底层...

    前言

    在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到O(log2N),即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到.
    因此在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同,本文中只对unordered_map和unordered_set进行介绍,unordered_multimap和unordered_multiset可查看文档介绍。

    unordered_map/_set的介绍

    unordered_map在线文档说明

    1. unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value。
    2. 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
    3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
    4. unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。
    5. unordered_maps实现了直接访问操作符(operator[]),它允许使用key作为参数直接访问value。
    6. 它的迭代器至少是前向迭代器。

    而unordered_set是存储键值的容器,且键值不允许重复,细节详见unordered_set在线文档说明

    底层结构

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

    哈希概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN )(以2为底),搜索的效率取决于搜索过程中元素的比较次数。
    理想的搜索方法(O(1)):可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。当向该结构中:

    1. 插入元素
      根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
    2. 搜索元素
      对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表).

    哈希冲突

    不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
    注意:不论如何定义哈希函数,当数据量达到一定范围时,必定会发生哈希冲突,这是无法避免的,只能最大限度的减少哈希冲突的情况。

    哈希函数

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

    • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    • 哈希函数计算出来的地址能均匀分布在整个空间中(最大限度减少冲突)
    • 哈希函数应该比较简单

    常见哈希函数
    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)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
    5. 折叠法–(了解)
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
    折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
    6. 随机数法–(了解)
    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。
    通常应用于关键字长度不等时采用此法

    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突。

    哈希函数采用处理余数法,被模的key必须要为整形才可以映射处理,此处提供将key转化为整形的方法而整形数据不需要转化

    字符串哈希算法

    template<class T>
    	struct Hash    //默认的整型类型
    	{
    		const T& operator()(const T& data)
    		{
    			return data;
    		}
    	};
    	template<>
    	struct Hash <string> //对字符串类型的特化
    	{
    		size_t  operator()(const string& data)
    		{
    			size_t count = 0;
    			for (size_t i = 0; i < data.size(); i++)
    			{
    				count *= 131;  // 这里使用的是 BKDR Hash算法
    				count += data[i];
    			}
    			return count;
    		}
    	};
    

    哈希冲突解决

    无法避免哈希冲突,那必然就要有解决的方法。
    解决哈希冲突两种常见的方法是:闭散列和开散列

    闭散列

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢?而找这个下一个位置,又分为线性探测和二次探测
    1.线性探测
    比如下面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
    插入时:
    -通过哈希函数获取待插入元素在哈希表中的位置
    -如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素
    在这里插入图片描述
    删除时:
    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响(找44时,计算出的地址在4的位置,但是4才被删除,为空,这时就不知道该如何寻找了)。因此线性探测采用标记的伪删除法来删除一个元素。(可以根据4被删除的状态,知道与要找的44存在哈希冲突,便可以往后面去找)

    // 哈希表每个空间给个标记
    // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
    	enum State{EMPTY, EXIST, DELETE};
    

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

    2. 二次探测
    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:H1 = (H0 + i * i )% m,或者: H1= (H0 - i * i)% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。

    哈希表的扩容问题:
    散列表的载荷因子定义为: a =填入表中的元素个数/散列表的长度,a是散列表装满程度的标志因子。由于表长是定值,a与“填入表中的元素个数”成正比,所以, a越大,表明填入表中的元素越多,产生冲突的可能性就越大:反之, a越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子a的函数,只是不同处理冲突的方法有不同的函数。
    对于开放定址法,荷载因子是特别重要因素,应严格限制在0.7 - 0.8以下。超过0. 8,查表时的CPU缓存不命中( cachemissing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表。
    扩容流程:
    1.开新表
    2.遍历旧表的数据,重新计算在新表中位置,在插入到新表里去
    3.释放旧表

    因此:闭散列(开放地址法)最大的缺陷就是空间利用率比较低,这也是哈希的缺陷

    闭散列实现的哈希表

    //哈希冲突解决:
    //1.闭散列哈希 也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去
    //而找这个下一个位置,又分为线性探测和二次探测
    namespace CLOSE_HASH
    {
    	// 哈希表每个空间给个标记
    	// EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
    	enum State{ EMPTY, EXIST, DELETE };
    
    	//节点定义
    	template <class T>
    	struct HashData
    	{
    		T _data;
    		State _state;
    	};
    	template <class K, class T, class KeyOfT>
    	class HashTable
    	{
    		typedef HashData<T> HashData;
    	public:
    		KeyOfT koft;
    		// 负载因子 = 表中数据/表的大小 衡量哈希表满的程度
    		// 表越接近满,插入数据越容易冲突,冲突越多,效率越低
    		// 负载因子越小,冲突概率越低,整体效率越高,但是负载因子越小,浪费的空间越大,
    		// 哈希表并不是满了才增容,开放定制法中,一般负载因子到了0.7左右就开始增容
    		bool Insert(const T& data)
    		{
    			扩容的一般的做法:
    			//if (_hashtable.size() == 0 || _num * 10 / _hashtable.size() >= 7) //hash表里为空,或者该扩容
    			//{
    			//	// 1.开2倍大小的新表
    			//	// 2.遍历旧表的数据,重新计算在新表中位置
    			//	// 3.释放旧表
    			//	//1.
    			//	vector<HashData> newtable;
    			//	size_t newtablesize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
    			//	newtable.resize(newtablesize);
    			//	//2.
    			//	for (int i = 0; i < _hashtable.size(); i++)
    			//	{
    			//		if (_hashtable[i]._state == EXIST) //找到旧表中的有效数据,重新计算映射到新表中去
    			//		{
    			//			size_t index = koft(_hashtable[i]._data) % newtablesize;
    			//			while (newtable[index]._state == EXIST)//哈希冲突时,使用线性探测找下一个空位置
    			//			{
    			//				++index;
    			//				if (index == newtablesize)//回到开头继续找
    			//				{
    			//					index = 0;
    			//				}
    			//			}
    			//			newtable[index] = _hashtable[i];//插入
    			//		}
    			//	}
    			//	_hashtable.swap(newtable);
    			//}
    
    			//利用insert插入,可以根据不同的探测方式来具体的插入
    			if (_hashtable.size() == 0 || _num * 10 / _hashtable.size() >= 7) //hash表里为空,或者该扩容
    			{
    				HashTable<K, T, KeyOfT> newhashtable;//开一个对象
    				size_t newtablesize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
    				newhashtable._hashtable.resize(newtablesize);
    				for (size_t i = 0; i < _hashtable.size(); i++)
    				{
    					if (_hashtable[i]._state == EXIST)
    					{
    						newhashtable.Insert(_hashtable[i]._data);//继续利用insert函数把数据插入到新的空间
    					}
    				}
    				_hashtable.swap(newhashtable._hashtable);
    			}
    			//容量没满,则开始插入逻辑
    
    			//线性探测
    			//先计算data在哈希表里的映射位置
    			//size_t index = koft(data) % _hashtable.size();
    			//while (_hashtable[index]._state == EXIST)
    			//{
    			//	if (koft(_hashtable[index]._data) == koft(data))//不允许键值重复
    			//		return false;
    			//	++index; //线性探测
    			//	index %= _hashtable.size();
    			//}
    			//_hashtable[index]._data = data;
    			//_hashtable[index]._state = EXIST;
    			//_num++;
    			//return true;
    
    			//二次探测
    			size_t start = koft(data) % _hashtable.size();
    			size_t index = start;
    			int i = 1;
    			while (_hashtable[index]._state == EXIST)
    			{
    				if (koft(_hashtable[index]._data) == koft(data))//不允许键值重复
    					return false;
    				index = start + i*i;//二次探测
    				i++;
    				index %= _hashtable.size();
    			}
    			_hashtable[index]._data = data;
    			_hashtable[index]._state = EXIST;
    			_num++;
    			return true;
    		}
    		//根据键值查找,也是先计算其映射的位置,但是可能是存在探测后的位置,所以需要向后一直遍历去找,直到遇到空
    		HashData* Find(const K& key)
    		{
    			KeyOfT koft;
    			size_t index = key%_hashtable.size();
    			while (_hashtable[index]._state != EMPTY)
    			{
    				if (koft(_hashtable[index]._data) == key)
    				{
    					if (_hashtable[index]._state == EXIST)
    					{
    						return &_hashtable[index];
    					}
    					else if (_hashtable[index]._state == DELETE)
    					{
    						return nullptr;
    					}
    				}
    				++index;
    				index %= _hashtable.size();
    			}
    			return nullptr;
    		}
    
    		bool Erase(const K& key)
    		{
    			HashData* ret = Find(key);
    			if (ret)
    			{
    				ret->_state = DELETE;
    				--_num;
    				return true;
    			}
    			return false;
    		}
    	private:
    		vector<HashData> _hashtable; //映射表
    		size_t _num = 0; //有效数据个数
    	};
    }
    

    开散列

    开散列概念
    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    对应之前4与44的哈希地址冲突的问题,链地址法将哈希地址相同的元素放入一个桶中:即:开散列中每个桶中放的都是发生哈希冲突的元素。
    在这里插入图片描述
    节点结构

    //节点结构
    	template<class T>
    	struct HashNode
    	{
    		T _data;
    		HashNode<T>* _next;
    		
    		HashNode(const T& data)
    			:_data(data)
    			, _next(nullptr)
    		{}
    	};
    

    哈希表结构

    	// K:关键码类型
    	// T: 不同容器V的类型不同,如果是unordered_map,T代表一个键值对,如果是unordered_set,T为 键类型
    	// KeyOfT: 因为T的类型不同,通过data取键的方式就不同,
    	// Hash: 哈希函数仿函数对象类型,哈希函数使用除留余数法,需要将Key转换为整形数字才能取模,
    	//哈希表可以存整型,或者字符串类型,而映射时字符串必须要转化为整数,需要哈希算法
    template<class K, class T,class KeyOfT,class Hash> 
    	class HashTable
    	{
    		typedef HashNode <T> Node;
    	public:
    		friend struct hashiterator < K, T, KeyOfT, Hash>;  //因为实现迭代器时需要用到找到下一个桶,所以需要访问底层的哈希表,但是为私有成员,所以用友元声明
    		typedef hashiterator<K, T, KeyOfT, Hash> iterator;//迭代器
    		//Insert
    		//Find
    		//。。。。方法
    	private:
    		vector<Node*> _hashtable;
    		size_t _num = 0;
    

    桶结构的迭代器

    //连地址法的桶结构的迭代器
    	template <class K,class T,class KeyOfT,class Hash>
    	struct hashiterator
    	{
    		typedef HashNode<T> Node;
    		typedef HashTable<K, T, KeyOfT, Hash> HT;
    		typedef hashiterator<K, T, KeyOfT, Hash> self;
    
    		Node* _node;// 当前迭代器关联的节点
    		HT* _ht;  // 哈希桶--主要是为了找下一个空桶时候方便
    
    		hashiterator(Node* node,HT* ht)
    			:_node(node)
    			, _ht(ht)
    		{}
    
    		T& operator*()
    		{
    			return _node->_data;
    		}
    		T* operator->()
    		{
    			return &_node->_data;
    		}
    		// 注意:因为哈希桶在底层是单链表结构,所以哈希桶的迭代器不需要--操作
    		self& operator++()
    		{
    			// 当前迭代器所指节点后还有节点时直接取其下一个节点
    			if (_node->_next)
    				_node = _node->_next;
    			else // 找下一个不空的桶,返回该桶中第一个节点
    			{
    				KeyOfT koft;
    				size_t index = _ht->HashFunc(koft(_node->_data)) % _ht->_hashtable.size();
    				index++;
    				for (; index < _ht->_hashtable.size(); index++)
    				{
    					Node* cur = _ht->_hashtable[index];//判断下一个桶是否为空
    					if (cur)
    					{
    						_node = cur;
    						return *this;
    					}
    				}
    				_node = nullptr;//后面一个也没有,则置空返回
    			}
    			return *this;	
    		}
    		bool operator!=(const self& s)
    		{
    			return _node != s._node;
    		}
    		bool operator==(const self& s)
    		{
    			return _node == s._node;
    		}
    	};
    

    在哈希表内部,我们写一个函数来调用仿函数模板类(哈希函数)计算映射的位置

    size_t HashFunc(const K& key)//键值取整型
    		{
    			Hash hash;
    			return hash(key);
    		}
    

    开散列的增容与插入

    增容:
    桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容。即荷载因子为1时,触发扩容
    增容流程也一样:
    1.开新表
    2.遍历旧表的数据,重新计算在新表中位置,插入进去,只不过还要遍历到桶里的每一个元素而已
    3.释放旧表

    if (_hashtable.size()== 0 ||_num == _hashtable.size() ) // 如果负载因子等于1,则增容,避免大量的哈希冲突
    			{
    				// 1.开2倍大小的新表(不一定是2倍)
    				// 2.遍历旧表的数据,重新计算在新表中位置
    				// 3.释放旧表
    				//1
    				vector<Node*> newtable;
    				size_t newtablesize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
    				newtable.resize(newtablesize);
    				//2.
    				for (size_t i = 0; i < _hashtable.size(); i++)
    				{
    					// 将旧表中的节点取下来重新计算在新表中的位置,并插入到新表
    					Node* cur = _hashtable[i];
    					while (cur)
    					{
    						Node* next = cur->_next;
    						size_t index = HashFunc(koft(cur->_data)) % newtablesize;//重新计算位置
    						cur->_next = newtable[index];
    						newtable[index] = cur;
    
    						cur = next;
    					}
    					//3.
    					_hashtable[i] = nullptr;
    				}
    				_hashtable.swap(newtable);
    			}
    

    插入元素

    //未满,计算插入位置再插入
    			size_t index = HashFunc(koft(data)) % _hashtable.size();
    			//1.先查找这个键值存不存在
    			Node* cur = _hashtable[index];
    			while (cur)
    			{
    				if (koft(cur->_data) == koft(data))
    				{
    					return make_pair(iterator(cur,this),false);//,对于unordered_map,不允许存在重复值,所以不允许插入,
    													/但是[]底层是调用insert函数的,存在 修改键对应的值 的这个操作,例如 map[2]++、map[2]=4更改键2对应的值为4等操作;所以要返回迭代器节点
    				}
    				else
    					cur = cur->_next;
    			}
    			//2.则可以头插或者尾插进链表
    			Node* newnode = new Node(data);
    			newnode->_next = _hashtable[index];
    			_hashtable[index] = newnode;
    			++_num;
    			return make_pair(iterator(newnode,this),true);
    

    开散列与闭散列比较
    应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如探测法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间

    哈希表底层增删查操作

    	template<class K, class T,class KeyOfT,class Hash> 
    	class HashTable
    	{
    		typedef HashNode <T> Node;
    	public:
    		friend struct hashiterator < K, T, KeyOfT, Hash>;  //因为实现迭代器时需要用到找到下一个桶,所以需要访问底层的哈希表,但是为私有成员,所以用友元声明
    		typedef hashiterator<K, T, KeyOfT, Hash> iterator;
    
    		iterator begin()
    		{
    			//第一个不为空的桶的第一个元素
    			for (size_t i = 0; i < _hashtable.size(); i++)
    			{
    				if (_hashtable[i])
    				{
    					return iterator(_hashtable[i],this);
    				}
    			}
    			return end();
    		}
    		iterator end()
    		{
    			//最后一个元素的下一个元素,可以直接设置为nullptr
    			return iterator(nullptr, this);
    		}
    
    
    		~HashTable()
    		{
    			Clear();
    		}
    		void Clear()
    		{
    			//一个桶一个桶的删除
    			for (int i = 0; i < _hashtable.size(); i++)
    			{
    				Node* cur = _hashtable[i];
    				while (cur)
    				{
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    				}
    				_hashtable[i] = nullptr;
    			}
    		}
    
    		size_t HashFunc(const K& key)//键值取整型
    		{
    			Hash hash;
    			return hash(key);
    		}
    		pair<iterator,bool> Insert(const T& data)
    		{
    			KeyOfT koft;
    			//也还是要先判断是否要增容,
    			//开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容。
    			if (_hashtable.size()== 0 ||_num == _hashtable.size() ) // 如果负载因子等于1,则增容,避免大量的哈希冲突
    			{
    				// 1.开2倍大小的新表(不一定是2倍)
    				// 2.遍历旧表的数据,重新计算在新表中位置
    				// 3.释放旧表
    				//1
    				vector<Node*> newtable;
    				size_t newtablesize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
    				newtable.resize(newtablesize);
    				//2.
    				for (size_t i = 0; i < _hashtable.size(); i++)
    				{
    					// 将旧表中的节点取下来重新计算在新表中的位置,并插入到新表
    					Node* cur = _hashtable[i];
    					while (cur)
    					{
    						Node* next = cur->_next;
    						size_t index = HashFunc(koft(cur->_data)) % newtablesize;//重新计算位置
    						cur->_next = newtable[index];
    						newtable[index] = cur;
    
    						cur = next;
    					}
    					//3.
    					_hashtable[i] = nullptr;
    				}
    				_hashtable.swap(newtable);
    			}
    			//未满,计算插入位置插入
    			size_t index = HashFunc(koft(data)) % _hashtable.size();
    			//1.先查找这个键值存不存在
    			Node* cur = _hashtable[index];
    			while (cur)
    			{
    				if (koft(cur->_data) == koft(data))
    				{
    					return make_pair(iterator(cur,this),false);//,对于unordered_map,不允许存在重复值,所以不允许插入,
    													/但是[]底层是调用insert函数的,存在 修改键对应的值 的这个操作,例如 map[2]++、map[2]=4更改键2对应的值为4等操作;所以要返回迭代器节点
    				}
    				else
    					cur = cur->_next;
    			}
    			//2.则可以头插或者尾插进链表
    			Node* newnode = new Node(data);
    			newnode->_next = _hashtable[index];
    			_hashtable[index] = newnode;
    			++_num;
    			return make_pair(iterator(newnode,this),true);
    		}
    		Node* Find(const K& key)
    		{
    			KeyOfT koft;
    			//也还是先计算出映射位置,在进入到挂载的链表里找
    			size_t index = HashFunc(key) % _hashtable.size();
    			Node* cur = _hashtable[index];
    			while (cur)
    			{
    				if (koft(cur->_data) == key)
    				{
    					return cur;
    				}
    				cur = cur->_next;
    			}
    			return nullptr;
    		}
    		bool Erase(const K& key)
    		{
    			KeyOfT koft;
    			size_t index = HashFunc(key) % _hashtable.size();
    			//因为是单链表,所以遍历时也要保存前一个指针,方便删除后的链接
    			Node* prev = nullptr;
    			Node* cur = _hashtable[index];
    			while (cur)
    			{
    				if (koft(cur->_data) == key)
    				{
    					if (prev == nullptr)//第一个就是要删除的
    					{
    						_hashtable[index] = cur->_next;
    					}
    					else
    					{
    						prev->_next = cur->_next;
    					}
    					delete cur;
    					return true;
    				}
    				else   //继续往下找
    				{
    					prev = cur;
    					cur = cur->_next;
    				}
    			}
    			return false;
    
    		}
    	private:
    		vector<Node*> _hashtable;
    		size_t _num = 0;
    	};
    

    模拟实现unordered_set

    #pragma once
    #include "HashTable.h"
    
    using namespace OPEN_HASH;
    namespace MyHashSet
    {
    	template<class K,class V,class Hash=Hash<K>>
    	class unordered_set
    	{
    		struct SetKeyOfT
    		{
    			const K& operator()(const K& key)
    			{
    				return key;
    			}
    		};
    
    	public:
    		typedef typename HashTable<K, V, SetKeyOfT, Hash> ::iterator iterator;
    		iterator begin()
    		{
    			return _hashset.begin();
    		}
    		iterator end()
    		{
    			return _hashset.end();
    		}
    		pair<iterator, bool> Insert(const K& key)
    		{
    			return _hashset.Insert(key);
    		}
    		//其他接口也都是基于底层的_hashset的接口函数
    	private:
    		HashTable<K, V, SetKeyOfT, Hash> _hashset;
    	};
    
    	void test_unordered_set()
    	{
    		unordered_set<int,int> s;
    		s.Insert(1);
    		s.Insert(5);
    		s.Insert(4);
    		s.Insert(2);
    
    		unordered_set<int,int>::iterator it = s.begin();
    		while (it != s.end())
    		{
    			cout << *it << " ";
    			++it;
    		}
    		cout << endl;
    	}
    }
    

    模拟实现unordered_map

    #pragma once
    #include <iostream>
    #include <string>
    #include "HashTable.h"
    using namespace std;
    using namespace OPEN_HASH;
    
    namespace MyHashMap
    {
    
    	// unordered_map中存储的是pair<K, V>的键值对,K为key的类型,V为value的类型,Hash为哈希函数类型,根据指定的关键字类型,对应不同的模板
    	// unordered_map在实现时,只需将_maphash中的接口重新封装即可
    	template<class K,class V,class Hash=Hash<K>>
    	class unordered_map
    	{
    		struct MapKeyOfT
    		{
    			const K& operator()(const pair<K, V>& kv)
    			{
    				return kv.second;
    			}
    		};
    	public:
    		typedef typename HashTable<K, pair<K, V>, MapKeyOfT, Hash>::iterator iterator;
    		iterator begin()
    		{
    			return _maphash.begin();
    		}
    		iterator end()
    		{
    			return _maphash.end();
    		}
    		pair<iterator, bool> Insert(const pair<K, V>& kv)
    		{
    			return _maphash.Insert(kv);
    		}
    		V& operator[](const K& key) 
    		{
    			pair<iterator, bool> ret = _maphash.Insert(make_pair(key, V()));  //得到返回的节点
    			//return ret.first->second; //再返回节点里键 对应的值,用于修改 ,返回值为引用,且此对象不是临时变量,视为可修改的左值 
    			return ret.first->second;
    		}
    		//。。。。其他接口也都是封装与哈希表结构的接口函数
    		//iterator Find(const K& key){ return _maphash.Find(key);}
    		//size_t count(const K& key){ return _maphash.count(key);}
    		//iterator erase(iterator position){return _maphash.Erase(key);}
    	private:
    		HashTable<K, pair<K,V>, MapKeyOfT, Hash> _maphash;
    	};
    
    
    
    	void test_unordered_map()
    	{
    		unordered_map<string, string> dict;//定义一个 字典
    		//插入
    		dict.Insert(make_pair("sort", "排序"));
    		dict.Insert(make_pair("left", "左边"));
    		dict.Insert(make_pair("string", "字符串"));
    		//使用[]更改键对应的值 ,,因为重载[]是使用的引用返回,作为左值,可以被修改
    		dict["left"] = "剩余"; //修改value
    		dict["end"] = "尾部";//或者插入
    
    		//unordered_map<string, string>::iterator it = dict.begin();
    		auto it = dict.begin();
    		while (it != dict.end())
    		{
    			cout << it->first << ":" << it->second << endl;
    			++it;
    		}
    	}
    }
    
    

    map/set和unordered_ map/unordered_ set总结

    1、它们都可以可以实现key和key/value的搜索场景,并且功能和使用基本一样。
    2、map/set的底层是使用红黑树实现的,遍历出来是有序的,增删查改的时间复杂度是O(logN).
    3、unordered_ map/ unordered_set 的底层是使用哈希表实现的,遍历出来是无序的,增删查改的时间复杂度是0(1)
    4、map和set是双向迭代器,unordered_map和unorded_set 是单向迭代器。

    展开全文
  • 哈希表实现原理

    千次阅读 2016-07-14 16:22:37
    1.hash 哈希表作为一种高效的存储结构,可以大大降低查询和存储的时间,其核心...哈希表的底层为一个长度较长的数组,通过将存放的各个元素进行一系列运算而转化为一串hash值,再通过相同的规则与数组的下标进行对应。

    1.hash

    哈希表作为一种高效的存储结构,可以大大降低查询和存储的时间,其核心理念为空间换时间,消耗一部分多余的内存来换取较高的性能,在当下电脑内存越来越大的趋势下,十分划算。
    哈希表又称为散列表,可以分为闭散列和开散列两种,这里只研究闭散列。

    2.实现原理

    哈希表的底层为一个长度较长的数组,通过将存放的各个元素进行一系列运算而转化为一串hash值,再通过相同的规则与数组的下标进行对应。但是,这并不能保证元素对应的下标唯一,可能存在两个元素运算后的hash值相同,从而指定到相同的下标(也会存在不同的hash值对应相同的数组下标),此时需要对这种冲突进行处理。

    故哈希表的实现主要为“建立下标对应”和“冲突处理”两部分。

    3.hash值的实现

    hash值的计算应该尽量实现少重复的特性,下面以String的HashCode方法为例:

    public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }
    与素数相乘是使用较多的处理方法,并且相乘的素数越大,重复的概率越小,是一种高效的处理手段。

    4.建立数组下标对应关系

    一般采用的方法有两种:

        1.取余法

        length为数组的长度

        利用hash%length建立对应关系,为了降低余数的重复性,length为素数,这样可以充分运用数组的每个下标,且不会越界。

        2.&运算

        将length设为2的倍数,可以得到length-1的二进制所有位都为1,所以hash&(length-1)可以运用数组的每一个下标,且不会越界

    5.冲突处理

    哈希表的设计从一直在避免重复,但重复的情况依旧会发生,这里介绍两种处理方法:

    1.后退法

    此方法必须在节点中添加一个next属性,将连续的有效节点变成一个链表,同时重复的元素会占用本属于别的元素的下标,而别的元素在被占用下标后又只能继续占用其他下标,这会使查询的效率大大降低,此设计模式要求哈希表中的冲突维持在较低水平,而且冲突上升会非常快。在移除一个节点后,需要将前节点的next属性修改(前节点非空时),否则会导致链表断裂,数据丢失。查询元素时,便可以使用next属性来遍历,直至空节点。

    下面为后退法设计的一个小案例 

    </pre><pre name="code" class="java">public void addEntry(K key, V value) {
            int hash = hash(key);//计算hash值,不具体写了,怎么实现可以自己定,重复率较低就行
            int i = indexFor(hash,length);//获取对应的数组下标,不具体写了,取余或&都可以
            Entry<K,V> e;
            for (; e != null; i++) {           
                e = table[i];
                if(e.hash==hash && e.key==key){//若该key已存在,则替换value
                    e.value=value; 
                    return null;
                }
            }
            e=new Entry();若未找到该key,则在空节点处创建包含该键值对的节点
            if(null!=table[i-1]){
                table[i-1].next=e;//此方法必须将有效节点连接起来
            }
            e.hash=hash;
            e.key=key;
            e.value=value;
            e.next=table[i+1];
      }
    2.链表法

    当两个不同的元素下标冲突时,将这两个下标合成一个链表存放于同一个下标下。HashMap便运用了此方法,下面为HashMap的源码

    void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);//若原来该下标有值,将以链表的形式在该下标位存放多个元素,并size++
            size++;
        }
    此方法的好处是不会影响别的下标,效率上高于第一种方法。


    6.总结

    根据对存储模式的分析,可以得到这样的结论:在容量使用率较低时,哈希表的查询和存储会非常的快(很少有多个元素的计算下标值相同,基本不需要冲突处理),而当容量使用率较高时,冲突出现的概率大大增加,查询的效率会大打折扣。据统计,使用率到打80%时,查询效率会开始有明显的下降,而到打90%时,查询效率已经非常低了,会有大量的冲突存在。所以一般的哈希表都会在使用率达到一定值后对哈希表进行扩容,并将各个元素存入新数组,各个元素也将获得新的下标,由于使用率的下降,冲突会大大降低,使哈希表的查询和存储性能一直维持在较高水平。但是这会造成一定的内存浪费,例如hashmap的加载因子(使用率)为75%(容量使用率超过75%就会进行扩容),这使得有25%的内存一直被浪费,这便是空间换时间的设计理念。










    展开全文
  • 哈希表的概念和原理

    2020-03-31 23:44:48
    哈希表的概念 哈希表(hashtable也叫散列表)是一种数据结构,它的神奇之处在于查询、添加和删除效率非常快,时间复杂度可以到达o(n) java集合中给出了底层结构采用哈希表数据结构的实现类,按照时间顺序分别为...

    一 哈希表的概念

    哈希表(hashtable也叫散列表)是一种数据结构,它的神奇之处在于查询、添加和删除效率非常快,时间复杂度可以到达o(n)
    在这里插入图片描述
    java集合中给出了底层结构采用哈希表数据结构的实现类,按照时间顺序分别为第一代Hashtable、第二代HashMap、第三代ConcurrentHashMap。他们的共同点是:底层结构都是哈希表,都是用来存储key-value映射,都实现了Map接口。
    在这里插入图片描述在这里插入图片描述
    哈希表的底层是由数组+链表组成的,当链表节点大于8时,还会有红黑树。
    在这里插入图片描述

    二 哈希表的原理

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    哈希表的原理(结构 添加步骤 查询步骤)

    1.哈希表的结构与特点
    在这里插入图片描述
    在这里插入图片描述
    2.哈希表是如何添加数据的
    在这里插入图片描述
    3.哈希表是如何查询数据的
    在这里插入图片描述

    展开全文
  • 哈希表的实现

    2016-12-16 11:31:00
    在了解到哈希表的原理之后要实现一个哈希表也很容易,主要需要完成的工作只有三点: 实现哈希函数 冲突的解决 操作接口的实现 数据结构 首先我们需要一个容器来保存我们的哈希表,哈希表需要保存的内容主要...

    在php的底层实现中,hash表是最常见的一种使用。那hash表具体是怎样实现的呢?

     

    哈希表的实现

    在了解到哈希表的原理之后要实现一个哈希表也很容易,主要需要完成的工作只有三点:

    1. 实现哈希函数
    2. 冲突的解决
    3. 操作接口的实现

    数据结构

    首先我们需要一个容器来保存我们的哈希表,哈希表需要保存的内容主要是保存进来的的数据, 同时为了方便的得知哈希表中存储的元素个数,需要保存一个大小字段, 第二个需要的就是保存数据的容器了。作为实例,下面将实现一个简易的哈希表。基本的数据结构主要有两个, 一个用于保存哈希表本身,另外一个就是用于实际保存数据的单链表了,定义如下:

    typedef struct _Bucket
    {
        char *key;
        void *value;
        struct _Bucket *next;
    } Bucket;
     
    typedef struct _HashTable
    {
        int size;
        int elem_num;
        Bucket** buckets;
    } HashTable;

    上面的定义和PHP中的实现类似,为了便于理解裁剪了大部分无关的细节,在本节中为了简化, key的数据类型为字符串,而存储的数据类型可以为任意类型。

    Bucket结构体是一个单链表,这是为了解决多个key哈希冲突的问题,也就是前面所提到的的链接法。 当多个key映射到同一个index的时候将冲突的元素链接起来。

    哈希函数实现

    哈希函数需要尽可能的将不同的key映射到不同的槽(slot或者bucket)中,首先我们采用一种最为简单的哈希算法实现: 将key字符串的所有字符加起来,然后以结果对哈希表的大小取模,这样索引就能落在数组索引的范围之内了。

    static int hash_str(char *key)
    {
        int hash = 0;
     
        char *cur = key;
     
        while(*cur != '\0') {
            hash += *cur;
            ++cur;
        }
     
        return hash;
    }
     
    // 使用这个宏来求得key在哈希表中的索引
    #define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

    这个哈希算法比较简单,它的效果并不好,在实际场景下不会使用这种哈希算法, 例如PHP中使用的是称为DJBX33A算法, 这里列举了Mysql,OpenSSL等开源软件使用的哈希算法, 有兴趣的读者可以前往参考。

    有兴趣的读者可以运行本小节实现的哈希表实现,在输出日志中将看到很多的哈希冲突, 这是本例中使用的哈希算法过于简单造成的.

    操作接口的实现

    为了操作哈希表,实现了如下几个操作接口函数:

    int hash_init(HashTable *ht);                               // 初始化哈希表
    int hash_lookup(HashTable *ht, char *key, void **result);   // 根据key查找内容
    int hash_insert(HashTable *ht, char *key, void *value);     // 将内容插入到哈希表中
    int hash_remove(HashTable *ht, char *key);                  // 删除key所指向的内容
    int hash_destroy(HashTable *ht);

    下面以初始化、插入和获取操作函数为例:

    int hash_init(HashTable *ht)
    {
        ht->size        = HASH_TABLE_INIT_SIZE;
        ht->elem_num    = 0;
        ht->buckets     = (Bucket **)calloc(ht->size, sizeof(Bucket *));
     
        if(ht->buckets == NULL) return FAILED;
     
        LOG_MSG("[init]\tsize: %i\n", ht->size);
     
        return SUCCESS;
    }

    初始化的主要工作是为哈希表申请存储空间,函数中使用calloc函数的目的是确保 数据存储的槽为都初始化为0,以便后续在插入和查找时确认该槽为是否被占用。

    int hash_insert(HashTable *ht, char *key, void *value)
    {
        // check if we need to resize the hashtable
        resize_hash_table_if_needed(ht);
     
        int index = HASH_INDEX(ht, key);
     
        Bucket *org_bucket = ht->buckets[index];
        Bucket *tmp_bucket = org_bucket;
     
        // check if the key exits already
        while(tmp_bucket)
        {
            if(strcmp(key, tmp_bucket->key) == 0)
            {
                LOG_MSG("[update]\tkey: %s\n", key);
                tmp_bucket->value = value;
     
                return SUCCESS;
            }
     
            tmp_bucket = tmp_bucket->next;
        }
     
        Bucket *bucket = (Bucket *)malloc(sizeof(Bucket));
     
        bucket->key   = key;
        bucket->value = value;
        bucket->next  = NULL;
     
        ht->elem_num += 1;
     
        if(org_bucket != NULL)
        {
            LOG_MSG("[collision]\tindex:%d key:%s\n", index, key);
            bucket->next = org_bucket;
        }
     
        ht->buckets[index]= bucket;
     
        LOG_MSG("[insert]\tindex:%d key:%s\tht(num:%d)\n",
            index, key, ht->elem_num);
     
        return SUCCESS;
    }

    上面这个哈希表的插入操作比较简单,简单的以key做哈希,找到元素应该存储的位置,并检查该位置是否已经有了内容, 如果发生碰撞则将新元素链接到原有元素链表头部。

    由于在插入过程中可能会导致哈希表的元素个数比较多,如果超过了哈希表的容量, 则说明肯定会出现碰撞,出现碰撞则会导致哈希表的性能下降,为此如果出现元素容量达到容量则需要进行扩容。 由于所有的key都进行了哈希,扩容后哈希表不能简单的扩容,而需要重新将原有已插入的预算插入到新的容器中。

    static void resize_hash_table_if_needed(HashTable *ht)
    {
        if(ht->size - ht->elem_num < 1)
        {
            hash_resize(ht);
        }
    }
     
    static int hash_resize(HashTable *ht)
    {
        // double the size
        int org_size = ht->size;
        ht->size = ht->size * 2;
        ht->elem_num = 0;
     
        LOG_MSG("[resize]\torg size: %i\tnew size: %i\n", org_size, ht->size);
     
        Bucket **buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *));
     
        Bucket **org_buckets = ht->buckets;
        ht->buckets = buckets;
     
        int i = 0;
        for(i=0; i < org_size; ++i)
        {
            Bucket *cur = org_buckets[i];
            Bucket *tmp;
            while(cur)
            {
                // rehash: insert again
                hash_insert(ht, cur->key, cur->value);
     
                // free the org bucket, but not the element
                tmp = cur;
                cur = cur->next;
                free(tmp);
            }
        }
        free(org_buckets);
     
        LOG_MSG("[resize] done\n");
     
        return SUCCESS;
    }

    哈希表的扩容首先申请一块新的内存,大小为原来的2倍,然后重新将元素插入到哈希表中, 读者会发现扩容的操作的代价为O(n),不过这个问题不大,因为只有在到达哈希表容量的时候才会进行。

    在查找时也使用插入同样的策略,找到元素所在的位置,如果存在元素, 则将该链表的所有元素的key和要查找的key依次对比, 直到找到一致的元素,否则说明该值没有匹配的内容。

    int hash_lookup(HashTable *ht, char *key, void **result)
    {
        int index = HASH_INDEX(ht, key);
        Bucket *bucket = ht->buckets[index];
     
        if(bucket == NULL) goto failed;
     
        while(bucket)
        {
            if(strcmp(bucket->key, key) == 0)
            { 
                LOG_MSG("[lookup]\t found %s\tindex:%i value: %p\n",
                    key, index, bucket->value);
                *result = bucket->value;
     
                return SUCCESS;
            } 
     
            bucket = bucket->next;
        }
     
    failed:
        LOG_MSG("[lookup]\t key:%s\tfailed\t\n", key);
        return FAILED;
    }

    PHP中数组是基于哈希表实现的,依次给数组添加元素时,元素之间是有先后顺序的, 而这里的哈希表在物理位置上显然是接近平均分布的,这样是无法根据插入的先后顺序获取到这些元素的, 在PHP的实现中Bucket结构体还维护了另一个指针字段来维护元素之间的关系。 具体内容在后一小节PHP中的HashTable中进行详细说明。上面的例子就是PHP中实现的一个精简版。

    转载于:https://www.cnblogs.com/tangchuanyang/p/6186196.html

    展开全文
  • HashMap底层的哈希表原理分析,HashMap原码分析 HashMap 在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理位置冲突,同一hash值节点都存储在一个链表里。但是当位于一个桶中元素较多,即hash值相等...
  • 你能说一说Python字典的底层实现原理吗? 这个问题可以从三个方面来回答: 1.python字典及其特性 字典是Python的一种可变、无序容器数据结构,它的元素以键值对的形式存在,键值唯一,它的特点搜索速度很快:数据量...
  • HashMap的底层实现原理

    2019-10-13 14:23:05
    HashMap的底层实现原理 HashMap底层实现采用的是哈希表,一种非常重要的数据结构 哈希表的基本结构是:数组+链表 数组的特点:占用空间连续,寻址容易,查询速度快.但是,增加和删除的效率非常低 链表的特点:占用...
  • 哈希表原理

    2020-08-14 11:14:36
    哈希表的底层实际上是基于数组来存储的, 当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。 取值时,先对指定的键求Hash值,再和...
  • HashMap的实现原理底层结构 哈希表 哈希表也叫散列表,是一种重要数据结构,应用场景比较丰富。 和其他数据结构相比,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突情况下,仅需一次...
  • HashMap底层实现原理解析

    万次阅读 多人点赞 2020-12-18 10:37:27
    一:HashMap底层实现原理解析 我们常见有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自数据结构特点: 1、数组结构: 存储区间连续、内存占用严重、空间复杂度大 优点:...
  • hashmap的底层实现原理

    2018-06-11 17:52:20
    HashMap实现原理及源码分析 哈希表(hash table)也叫散列表,是一种非常重要数据结构,应用场景及其丰富,许多缓存技术(比如memcached)核心其实就是在内存中维护一张大的哈希表,而HashMap的实现原理也常常...
  • Map集合哈希表哈希表概述HashMap底层实现原理HashMap底层源代码map.put(k,v), v=map.get(k)两方法实现原理HashMap集合Key特点hashmap扩容机制二、HashTableHashTable与HashMap区别 哈希表 哈希表概述 哈希表是一...
  • Hash哈希表原理

    2020-10-27 17:45:17
    哈希表原理:如果说每一个数据它都对应着一个固定位置,那我们查找特定一个数据时,就可以直接查看这个数据对应位置是否存在数据。一个形象例子就是学生在教室中位置,开学时候,老师会给学

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 867
精华内容 346
关键字:

哈希表的底层实现原理