精华内容
下载资源
问答
  • 从解决一个问题入手:大量的数据要存储查询,构造哈希表来解决 初步想法 借鉴数组下标访问的思路来做,只需知道起始位置和下标值, 不管数组中有多少个元素,都可以一次访问到, 将元素和元素位置建立一种一一...

    理解HashMap底层,首先应该理解Hash函数

    从解决一个问题入手:大量的数据要存储查询,构造哈希表来解决

    初步想法

    借鉴数组下标访问的思路来做,只需知道起始位置和下标值,

    不管数组中有多少个元素,都可以一次访问到,

    将元素和元素位置建立一种一一对应的关系

    Hash函数的出现

    输入的元素的范围可能很大甚至无穷,而我们的内存有限,

    所以说我们需要一种函数映射关系,将这些无限的元素映射到我们有限的内存地址上。

    Hash函数代表着一类函数,即把任意范围的元素可以通过映射关系压缩成固定范围的元素。

    Hash函数的选择

    如果是正整数,我们可以用这个正整数数除以某个数,取其余数,即我们常用的 k % m,k为正整数,m 为除数;

    这样一来,范围就缩小了很多,比如说 15%10=5,26%10=6,...,所有的正整数经过运算,都变成了 0-9 范围之间的数了,

    这样范围就缩小了很多

    m 的选择

    这种做法,m 的选择就非常重要了,如果 k 值分布均匀还无所谓,如果 k 值具有某些特征

    比如说 k 的个位基本上不变,而高位分布均匀,如 15,25,45,65,85,95,155,就遭遇大冲突了,

    必须要使得经过Hash函数后关键字的分布均匀,尽量减少冲突

    链地址法

    为了解决冲突,引出链地址法

    在存储的时候,如果多个元素被Hash到同一位置,那么就加入到该位置所指向的链表中,

    如果该位置没有元素,则为null(指向空)”

    由于新加入的元素很可能被再次访问到,使用“头插”

    rehash

    这样解决冲突固然好,但是也有瓶颈

    当我们实际存入的值越来越多的时候,这个链表也势必越来越长,

    那当我们进行查找的时候,势必就会遍历链表,效率也就越来越慢。

    因此,我们要选取一个相关的新的Hash函数(比如之前使用 key % m,现在只改变一下m的值)

    将旧Hash表中所有的元素通过新的Hash函数计算出新的Hash值,并将其插入到新表中(仍然使用链表),这就叫rehash

     这里的数组就扩大了近两倍,由于要大小要选素数,那就选原数组大小两倍后的第一个素数7,旧Hash表和新Hash表采用了不同的Hash函数,但相关,只是m的取值变了

    装载因子 α 

     我们可以定义这样一个变量 α = 所有元素个数/数组的大小,

    它代表着我们的Hash表(也就是数组)的装满程度,在这里也代表链表的平均长度

     这个装载因子代表了Hash表的装满程度,这里也可以代表链表的平均长度,那么也就可以代表查询时的时间长短了。

     

    参考资料:神速哈希上神速哈希下

    转载于:https://www.cnblogs.com/kumata/p/9857341.html

    展开全文
  • 文章目录前言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%的内存一直被浪费,这便是空间换时间的设计理念。










    展开全文
  • 哈希表原理

    千次阅读 2019-07-08 18:05:07
    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理哈希表底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后...

    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到O(1)O(1),最坏的情况是O(n)O(n),当然这种是最极端的情况,极少遇到。
    image
    不管哪门语言,实现一个HashMap的过程均可分为三大步骤:

    • 实现一个Hash函数
    • 合理解决Hash冲突
    • 实现HashMap的操作方法

    Hash函数

    Hash函数非常重要,一个好的Hash函数不仅性能优越,而且还会让存储于底层数组中的值分配的更加均匀,减少冲突发生。之所以是减少冲突,是因为取Hash的过程,实际上是将输入键(定义域)映射到一个非常小的空间中,所以冲突是无法避免的,能做的只是减少Hash碰撞发生的概率。具体实现时,哈希函数算法可能不同,在Rust及很多语言的实现中,默认选择SipHash哈希算法。

    默认情况下,Rust的HashMap使用SipHash哈希算法,其旨在防止哈希表碰撞攻击,同时在各种工作负载上提供合理的性能。虽然 SipHash 在许多情况下表现出竞争优势,但其中一个比其它哈希算法要慢的情况是使用短键,例如整数。这就是为什么 Rust 程序员经常观察到 HashMap 表现不佳的原因。在这些情况下,经常推荐 FNV 哈希,但请注意,
    它不具备与 SipHash 相同的防碰撞性。

    影响Hash碰撞(冲突)发生的除了Hash函数本身意外,底层数组容量也是一个重要原因。很明显,极端情况下如果数组容量为1,哪必然发生碰撞,如果数组容量无限大,哪碰撞的概率非常之低。所以,哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值,比如数组容量100,当前存贮了90个键值对,负载因子为0.9。负载因子决定了哈希表什么时候扩容,如果负载因子的值太大,说明存储的键值对接近容量,增加碰撞的风险,如果值太小,则浪费空间。

    所以,既然冲突无法避免,就必须要有解决Hash冲突的机制方法。

    处理冲突的几种方法

    主要有四类处理冲突的方法:

    • 外部拉链法(常用)
    • 开放定址法(常用)
    • 公共溢出区(不常用)
    • 再Hash法(不常用)

    外部拉链法

    主要思想是基于数组和链表的组合来解决冲突,桶(Bucket)中不直接存储键值对,每个Bucket都链接一个链表,当发生冲突时,将冲突的键值对插入链表中。外部拉链法的有点在于方法简单,非同义词之间也不会产生聚集现象(相比于开放定址法),并且其空间结构是动态申请的,所以比较适合无法确定表长的情况:缺点是链表指针需要额外的空间,遇到碰撞拒绝服务时会退化为单链表。

    同义词:两个元素通过Hash函数得到了相同的索引地址,这两个元素就叫做同义词。

    下面是外部拉链法的两种实现方法,主要区别在于桶(Bucket)中是否存储数据。
    image

    image

    开放定址法

    主要思想是发生冲突时,直接去寻找下一个空的地址,只要底层的表足够大,就总能找到空的地址。这个寻找下一个地址的行为,叫做探测。 hashi=(hash(key)+di)&ThinSpace;&VeryThinSpace;mod&VeryThinSpace;&ThinSpace;mi=1,2...k&ThinSpace;(km1){hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}, i=1,2...k\,(k\leq m-1)`,其中hash(key)hash(key)为哈希函数,mm为哈希表长,did_{i}为增量序列,ii为已发生冲突的次数。根据增量序列取法的不同有多种探测方法:

    • di=1,2,3...(m1)d_{i}=1,2,3...(m-1)称为线性探测(Linear Probing);即 di=id_{i}=i,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。
    • di=±12,±22,±32...±k2(km/2)d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)称为平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔$ d_{i}=i^{2}$个单元的位置是否为空,如果为空,将地址存放进去。
    • di=d_{i}=伪随机数序列,称为伪随机探测。

    下图为线性探测:

    image

    公共溢出区

    主要思想是建立一个独立的公共区,把冲突的键值对都放在其中。不常用,这里不再细述。

    再Hash法

    主要思想是有冲突时,换另外一个Hash函数来算Hash值。不常用,这里不再细述。

    实现哈希表的操作方法

    主要是:

    • insert
    • remove
    • get
    • contains_key
    • …等等…

    其中最重要的是插入、查找、删除这三个操作。

    参考文档Hash table

    关注微信公众号,推送常用数据结构、TCP/IP、分布式、后端开发等技术分享,共同学习进步!

    展开全文
  • 字典是通过哈希表实现的。字典也被称为哈希数组等。字典 ---------------------哈希数组键------(哈希函数)--数组索引值-------------------------数组值哈希函数的目的是使键均匀地分布在数组中,并且可以在内存中...
  • python 字典底层实现原理python字典底层是通过哈希表来实现的,也就是所字典底层也是一个列表,当我们用字典当中的`key`去获取对应的`value`时,会将`key`转换为列表当中的`index`,通过`index`去准确快速的获取到`...
  • Hash哈希表原理

    2020-10-27 17:45:17
    哈希表原理:如果说每一个数据它都对应着一个固定的位置,那我们查找特定一个数据时,就可以直接查看这个数据对应的位置是否存在数据。一个形象的例子就是学生在教室中的位置,开学的时候,老师会给学
  • HashMap底层哈希表原理分析,HashMap原码分析 HashMap 在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理位置冲突,同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的...
  • 详解Python字典的底层原理————哈希表(Python面试必备) 作者:Loren no hurry 2019-06-9 Python面试经常会被问到: 你能说一说Python字典的底层实现原理吗? 这个问题可以从三个方面来回答: 1.python字典及其...
  • 1.NSDictionary底层哈希表,下面会介绍具体是用拉链法还是开放定址法线性探测来解决冲突?由于Apple给的查询复杂度可以快至O(1),那么为什么是O(1),底层是如何通过空间换取时间的? 2.NSArray是线性连续内存,这...
  • Redis字典在redis中被广泛运用,作为redis字典底层实现的哈希表结构是怎样的呢,今天结合源码初步了解下typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } ...
  • dict底层实现在Python中,字典是依靠散列表或说哈希表(Hash Table)进行实现的,使用开放地址法解决冲突。所以其查找的时间复杂度会是O(1),下文会具体讲解哈希表的工作原理和解决冲突时的具体方法。也就是说,字典也...
  • 哈希表存储数据结构原理

    千次阅读 2018-03-31 20:59:48
    哈希表底层使用的也是数组机制,数组中也存放对象,而这些对象往数组中存放时的位置比较特殊,当需要把这些对象给数组中存放时,那么会根据这些对象的特有数据结合相应的算法,计算出这个对象在数组中的位置,然后把...
  • 上一篇我们主要介绍了String和List的底层实现原理,今天我们来说说Hash的数据结构。哈希作为我们常见的一种数据结构,那么在Redis中它是怎么实现的呢?01Hash的数据结构Redis 中的hash,内部是由 HashTable 或者 ...
  • 哈希表的概念和原理

    2020-03-31 23:44:48
    java集合中给出了底层结构采用哈希表数据结构的实现类,按照时间顺序分别为第一代Hashtable、第二代HashMap、第三代ConcurrentHashMap。他们的共同点是:底层结构都是哈希表,都是用来存储key-value映射,都实现了...
  • 文章目录1、为什么要说哈希表2、什么是哈希表3、哈希函数的构造4、哈希冲突的处理4.1 开放定址法4.2 链地址法5、如何设计一个健壮的哈希表5.1 Hash Table的扩容5.2 如何选择扩容的策略5.3 开放定址法 VS 链地址法6、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,241
精华内容 496
关键字:

哈希表底层原理