精华内容
下载资源
问答
  • 最近在看Redis设计与实现,发现Redis中的哈希表也是根据负载因子的扩容和收缩。 当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作: 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令...

    最近在看Redis设计与实现,发现Redis中的哈希表也是根据负载因子的扩容和收缩。

    当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作:

    服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 1 ;
    服务器目前正在执行BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 5 ;

    上面意思是Redis在进行rdb快照备份的时候,负载因子为5。没有执行rdb快照时负载因子为1。

     

    为什么负载因子可以大于1,并且达到5?HashMap也就0.75而已。

    # 负载因子 = 哈希表已保存节点数量 / 哈希表大小
    load_factor = ht[0].used / ht[0].size
    

    因为已保存节点数量是包括冲突的节点数量,所以已保存节点数量是有可能大于哈希表大小的,所以也就可以达到5。
     

    为什么在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 负载因子要大于等于 5?而未执行时大于等于1?

    书中的解释是:

    根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行, 服务器执行扩展操作所需的负载因子并不相同, 这是因为在执行BGSAVE 命令或BGREWRITEAOF 命令的过程中, Redis 需要创建当前服务器进程的子进程,
    而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率, 所以在子进程存在期间,
    服务器会提高执行扩展操作所需的负载因子, 从而尽可能地避免在子进程存在期间进行哈希表扩展操作, 这可以避免不必要的内存写入操作,最大限度地节约内存。

     
    又又又触及到知识盲区了,什么是写时复制?这就要拿linux系统来讲了。

    首先了解什么是fork?

    在linux系统中,fork是类Unix操作系统上创建进程的主要方法。fork用于创建子进程(等同于当前进程的副本)。

    Copy On Write原理:

    fork创建出的子进程,与父进程共享内存空间。也就是说,如果子进程不对内存空间进行写入操作的话,内存空间中的数据并不会复制给子进程,这样创建子进程的速度就很快了!(不用复制,直接引用父进程的物理空间)。

    Copy On Write技术实现原理:

    fork()之后,kernel(内核)把父进程中所有的内存页的权限都设为read-only,然后子进程的地址空间指向父进程。当父子进程都只读内存时,相安无事。当其中某个进程写内存时,CPU硬件检测到内存页是read-only的,于是触发页异常中断(page-fault),陷入kernel(内核)的一个中断例程。中断例程中,kernel就会把触发的异常的页复制一份,于是父子进程各自持有独立的一份。

    Copy On Write技术好处是什么?

    COW技术可减少分配和复制大量资源时带来的瞬间延时。

    COW技术可减少不必要的资源分配。比如fork进程时,并不是所有的页面都需要复制,父进程的代码段和只读数据段都不被允许修改,所以无需复制。

    Copy On Write技术缺点是什么?

    如果在fork()之后,父子进程都还需要继续进行写操作,那么会产生大量的分页错误(页异常中断page-fault),这样就得不偿失。

    展开全文
  • //算法科学家总结出的一个增容质数,按照这样增容的效率更高 const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, ...

    哈希

    在之前介绍的数据结构中,元素与其所存储的位置之间没有对应的关系,所以在查找的时候就需要经过多次的比较,才能找到具体的位置。对于顺序结构来说,这样查找的时间复杂度一般都是O(N),而对于树形结构的如搜索树等则也需要O(logN)。
    但是,还存在着这样一种数据结构,他通过某种方法的处理,使得元素存储的位置与元素本身建立起了映射关系,此时如果要查找改数据,就可以直接到对应的位置去,使得时间复杂度达到了O(1),这就是哈希(散列)。


    哈希函数

    哈希函数就是建立起元素与其存储位置的映射关系。
    对于哈希函数来说,必须具有以下特点;

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

    哈希冲突大量出现往往都是因为哈希函数设计的不够合理,但是即使再优秀的哈希函数,也只能减少哈希冲突的次数,无法避免哈希冲突

    常见的哈希函数

    1. 直接定址法(常见)
      哈希函数:Hash(Key)= A*Key + B;
      这是最简单的哈希函数,直接取关键字本身或者他的线性函数来作为散列地址。
    2. 除留余数法(常见)
      哈希函数 :Hash(key) = key % capacity
      几乎是最常用的哈希函数,用一个数来对key取模,一般来说这个数都是容量。
    3. 平方取中法
      对关键字进行平方,然后取中间的几位来作为地址。
    4. 折叠法
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加
      求和,并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况**
    5. 随机数法
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为
      随机数函数。
      通常应用于关键字长度不等时采用此法
    6. 数学分析法
      设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能
      在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出
      现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址

    字符串哈希函数

    因为哈希函数的常用方法如直接定址、除留余数、平方取中等方法需要用的key值为整型,而大部分时候我们的key都是string,对于string来说,上面的方法都行不通,因为无法对string进行算数运算,所以需要考虑新的方法。

    常见的字符串哈希算法有BKD,SDB,RS等,这些算法大多通过一些公式来对字符串每一个字符的ascii值或者字符串的大小进行计算,来推导出一个不容易产生冲突的key值。

    例如BKDHash

    struct _Hash<std::string>
    {
    	const size_t& operator()(const std::string& key)
    	{
    		//BKDR字符串哈希函数
    		size_t hash = 0;
    
    		for (size_t i = 0; i < key.size(); i++)
    		{
    			hash *= 131;
    			hash += key[i];
    		}
    
    		return hash;
    	}
    };
    

    这里推荐两篇文章,一篇具体对比各类字符串哈希函数的效率,一篇是实现。

    字符串Hash函数对比
    各种字符串Hash函数


    哈希冲突

    哈希冲突就是两个不同的数据通过同一个哈希函数计算出了相同的位置,这种现象就是哈希冲突。

    哈希冲突使得多个数据映射的位置相同,但是每个位置又只能存储一个数据,所以就需要通过某种方法来解决哈希冲突。

    对于哈希冲突的解决方法,一般根据不同的结构,分为以下几种


    闭散列的解决方法

    因为闭散列是顺序的结构,所以可以通过遍历哈希表,来将冲突的数据放到空的位置上

    1. 线性探测
      线性探测即为从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
      这种方法实现起来极为简单,但是效率也不高,因为如果同一位置产生了大量的哈希冲突,就会导致每次都在同一个位置进行探测,例如我在10这里连续冲突100次,此时所有探测的次数加起来就会高达100!,这样方法效率十分的低下。

    2. 二次探测
      线性探测即为从发生冲突的位置开始,每次往后探测i^2个位置,如1, 2, 4, 8等,这样的话就将每次探测的效率从O(N)提升到了O(logN),即使有着大量的冲突堆积,也不会导致效率过低。


    开散列的解决方法

    因为开散列本身就是一种链式的结构,所以其本身就是一种解决方法,这种方法也叫做链地址法
    链地址法
    在这里插入图片描述
    链地址法在每一个映射位置都建立起一个链表(数据过多时可能会转为建立红黑树),将每次插入的数据都直接连接上这个链表,这样就不会像闭散列一样进行大量的探测,但是如果链表过长也会导致效率低下。


    负载因子以及增容

    哈希冲突出现的较为密集,往往代表着此时数据过多,而能够映射的地址过少,这就导致了随着数据的增多,冲突的次数就越来越多,而要想解决这个问题,就需要通过负载因子的判断来进行增容。

    负载因子的大小 = 表中数据个数 / 表的容量

    对于闭散列

    对于闭散列来说,因为其是一种线性的结构,所以一旦负载因子过高,就很容易出现哈希冲突的堆积,所以当负载因子达到一定程度时就需要进行增容,并且增容后,为了保证映射关系,还需要将数据重新映射到新位置。

    经过算法科学家的计算, 负载因子应当严格的控制在0.7-0.8以下,所以一旦负载因子到达这个范围,就需要进行增容。

    因为除留余数法等方法通常是按照表的容量来计算,所以科学家的计算,当对一个质数取模时,冲突的几率会大大的降低,并且因为增容的区间一般是1.5-2倍,所以算法科学家列出了一个增容质数表,按照这样的规律增容,冲突的几率会大大的降低。

    这也是STL中unordered_map/unordered_set使用的增容方法。

    //算法科学家总结出的一个增容质数表,按照这样增容的效率更高
    	const int PRIMECOUNT = 28;
    	
    	const size_t primeList[PRIMECOUNT] = 
    	{
    	 53ul, 97ul, 193ul, 389ul, 769ul,
    	 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	 1610612741ul, 3221225473ul, 4294967291ul
    	};
    

    对于开散列结构

    因为哈希桶是开散列的链式结构,发生了哈希冲突是直接在对应位置位置进行头插,而桶的个数是固定的,而插入的数据会不断增多,随着数据的增多,就可能会导致某一个桶过重,使得效率过低。

    所以最理想的情况,就是每个桶都有一个数据。这种情况下,如果往任何一个地方插入,都会产生哈希冲突,所以当数据个数与桶的个数相同时,也就是负载因子为1时就需要进行扩容

    具体实现

    哈希表(闭散列)

    对于闭散列,我们需要通过状态来记录一个数据是否在表中,所以这里会使用枚举来实现。

    enum State
    {
    		EMPTY,//空
    		EXITS,//存在
    		DELETE,//已经删除
    };
    
    template<class T>
    struct HashData
    {
    	HashData(const T& data = T(), const State& state = EMPTY)
    		: _data(data)
    		, _state(state)
    	{}
    
    	T _data;
    	State _state;
    };
    

    插入

    插入的思路很简单,计算出映射的地址后,开始遍历判断下面几种状态

    1. 如果映射位置已存在数据,并且状态为存在,则说明产生冲突,继续往后查找
    2. 如果映射位置的数据与插入的数据相同,并且状态为存在,则说明此时数据已经插入过,此时就不需要再次插入
    3. 如果映射位置的状态为删除或者空,则代表着此时表中没有这个数据,在这个位置插入即可
    bool Insert(const T& data)
    {
    	KeyOfT koft;
    	//判断此时是否需要增容
    	//当装填因子大于0.7时增容
    	if (_size * 10 / _table.size() >= 7)
    	{
    		//增容的大小按照别人算好的近似两倍的素数来增,这样效率更高,也可以直接2倍或者1.5倍。
    		std::vector<HashData> newTable(getNextPrime(_size));
    
    		for (size_t i = 0; i < _table.size(); i++)
    		{
    			//将旧表中的数据全部重新映射到新表中
    			if (_table[i]._state == EXITS)
    			{
    				//如果产生冲突,则找到一个合适的位置
    				size_t index = HashFunc(koft(_table[i]._data));
    
    				while (newTable[i]._state == EXITS)
    				{
    					i++;
    
    					if (i == _table.size())
    					{
    						i = 0;
    					}
    				}
    
    				newTable[i] = _table[i];
    			}
    		}
    
    		//最后直接将数据进行交换即可,原来的数据会随着函数栈帧一起销毁
    		_table.swap(newTable);
    	}
    
    	//用哈希函数计算出映射的位置
    	size_t index = HashFunc(koft(data));
    
    	//从那个位置开始探测, 如果该位置已经存在时,有两种情况,一种是已经存在,一种是冲突,这里使用的是线性探测
    	while (_table[index]._state == EXITS)
    	{
    		//如果已经存在了,则说明不用插入
    		if (koft(_table[index]._data) == koft(data))
    		{
    			return false;
    		}
    		else
    		{
    			index++;
    			index = HashFunc(index);
    		}
    	}
    
    	//如果走到这里,说明这个位置是空的或者已经被删除的位置,可以在这里插入
    	_table[index]._data = data;
    	_table[index]._state = EXITS;
    	_size++;
    
    	return true;
    }
    

    查找

    查找也分几种情况

    1. 如果映射的位置为空,则说明查找失败
    2. 如果映射的位置的数据不同,并且状态为存在,则说明产生冲突,继续向后查找
    3. 如果映射的位置的数据相同,如果状态为删除,则说明数据已经删除,查找失败,而如果数据为存在,则说明查找成功。
    HashData* Find(const K& key)
    {
    	KeyOfT koft;
    	size_t index = HashFunc(key);
    
    	//遍历,如果查找的位置为空,则说明查找失败
    	while (_table[index]._state != EMPTY)
    	{
    		//此时判断这个位置的数据是否相同,如果不同则说明出现哈希冲突,继续往后查找
    		if (koft(_table[index]._data) == key)
    		{
    			//此时有两个状态,一种是数据已经被删除,一种是数据存在。
    			if (_table[index]._state == EXITS)
    			{
    				return &_table[index];
    			}
    			else if (_table[index]._state == DELETE)
    			{
    				return nullptr;
    			}
    		}
    
    		index++;
    
    		//如果index越界,则归零
    		if (index == _table.size())
    		{
    			index = 0;
    		}
    	}
    
    	return nullptr;
    }
    

    删除

    直接遍历查找数据,如果找不到则说明已经被删除,如果找到了则直接将状态改为删除即可

    bool Erase(const K& key)
    {
    	HashData* del = Find(key);
    
    	//如果找不到则说明已经被删除
    	if (del == nullptr)
    	{
    		return false;
    	}
    	else
    	{
    		//找到了则直接更改状态即可
    		del->_state = DELETE;
    		_size--;
    		return true;
    	}
    }
    

    完整代码实现

    #pragma once
    #include<vector>
    
    namespace lee
    {
    	//算法科学家总结出的一个增容质数表,按照这样增容的效率更高
    	const int PRIMECOUNT = 28;
    	const size_t primeList[PRIMECOUNT] = 
    	{
    	 53ul, 97ul, 193ul, 389ul, 769ul,
    	 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	 1610612741ul, 3221225473ul, 4294967291ul
    	};
    
    	enum State
    	{
    		EMPTY,
    		EXITS,
    		DELETE,
    	};
    
    
    	template<class T>
    	struct HashData
    	{
    		HashData(const T& data = T(), const State& state = EMPTY)
    			: _data(data)
    			, _state(state)
    		{}
    
    		T _data;
    		State _state;
    	};
    
    	template<class K, class T, class KeyOfT>
    	class HashTable
    	{
    	public:
    		typedef HashData<T> HashData;
    
    		HashTable(size_t capacity = 10)
    			: _table(capacity)
    			, _size(0)
    		{}
    
    		size_t getNextPrime(size_t num)
    		{
    			size_t i = 0;
    
    			for (i = 0; i < PRIMECOUNT; i++)
    			{
    				//返回比那个数大的下一个质数 
    				if (primeList[i] > num)
    				{
    					return primeList[i];
    				}
    			}
    
    			//如果比所有都大,还是返回最后一个,因为最后一个已经是32位最大容量
    			return primeList[PRIMECOUNT - 1];
    		}
    
    		//除留余数法
    		size_t HashFunc(const K& key)
    		{
    			return key % _table.size();
    		}
    
    		bool Insert(const T& data)
    		{
    			KeyOfT koft;
    			//判断此时是否需要增容
    			//当装填因子大于0.7时增容
    			if (_size * 10 / _table.size() >= 7)
    			{
    				//增容的大小按照别人算好的近似两倍的素数来增,这样效率更高,也可以直接2倍或者1.5倍。
    				std::vector<HashData> newTable(getNextPrime(_size));
    
    				for (size_t i = 0; i < _table.size(); i++)
    				{
    					//将旧表中的数据全部重新映射到新表中
    					if (_table[i]._state == EXITS)
    					{
    						//如果产生冲突,则找到一个合适的位置
    						size_t index = HashFunc(koft(_table[i]._data));
    
    						while (newTable[i]._state == EXITS)
    						{
    							i++;
    
    							if (i == _table.size())
    							{
    								i = 0;
    							}
    						}
    
    						newTable[i] = _table[i];
    					}
    				}
    
    				//最后直接将数据进行交换即可,原来的数据会随着函数栈帧一起销毁
    				_table.swap(newTable);
    			}
    			
    			//用哈希函数计算出映射的位置
    			size_t index = HashFunc(koft(data));
    
    			//从那个位置开始探测, 如果该位置已经存在时,有两种情况,一种是已经存在,一种是冲突,这里使用的是线性探测
    			while (_table[index]._state == EXITS)
    			{
    				//如果已经存在了,则说明不用插入
    				if (koft(_table[index]._data) == koft(data))
    				{
    					return false;
    				}
    				else
    				{
    					index++;
    					index = HashFunc(index);
    				}
    			}
    
    			//如果走到这里,说明这个位置是空的或者已经被删除的位置,可以在这里插入
    			_table[index]._data = data;
    			_table[index]._state = EXITS;
    			_size++;
    
    			return true;
    		}
    
    		HashData* Find(const K& key)
    		{
    			KeyOfT koft;
    			size_t index = HashFunc(key);
    
    			//遍历,如果查找的位置为空,则说明查找失败
    			while (_table[index]._state != EMPTY)
    			{
    				//此时判断这个位置的数据是否相同,如果不同则说明出现哈希冲突,继续往后查找
    				if (koft(_table[index]._data) == key)
    				{
    					//此时有两个状态,一种是数据已经被删除,一种是数据存在。
    					if (_table[index]._state == EXITS)
    					{
    						return &_table[index];
    					}
    					else if (_table[index]._state == DELETE)
    					{
    						return nullptr;
    					}
    				}
    
    				index++;
    
    				//如果index越界,则归零
    				if (index == _table.size())
    				{
    					index = 0;
    				}
    			}
    
    			return nullptr;
    		}
    
    		bool Erase(const K& key)
    		{
    			HashData* del = Find(key);
    
    			//如果找不到则说明已经被删除
    			if (del == nullptr)
    			{
    				return false;
    			}
    			else
    			{
    				//找到了则直接更改状态即可
    				del->_state = DELETE;
    				_size--;
    				return true;
    			}
    		}
    
    	private:
    		std::vector<HashData> _table;
    		size_t _size;
    	};
    };
    

    哈希桶(开散列)

    在这里插入图片描述

    开散列也叫哈希桶,桶为每一个映射的位置,桶一般用链表或者红黑树实现(这里我用的是链表)。当我们通过映射的地址,找到存放数据的桶,再对桶进行插入或者删除操作即可。

    插入

    通过计算映射位置找到对应的桶,再判断数据是否存在后将数据头插进去即可(也可以尾插)

    bool Insert(const T& data)
    {
    	KeyofT koft;
    
    	/*
    		因为哈希桶是开散列的链式结构,发生了哈希冲突是直接在对应位置位置进行头插,而桶的个数是固定的,而插入的数据会不断增多,
    		随着数据的增多,就可能会导致某一个桶过重,使得效率过低。
    		所以最理想的情况,就是每个桶都有一个数据。这种情况下,如果往任何一个地方插入,都会产生哈希冲突,所以当数据个数与桶的个数相同时,也就是负载因子为1时就需要进行扩容。
    	*/
    	if (_size == _table.size())
    	{
    		//按照素数表来增容
    		size_t newSize = getNextPrime(_table.size());
    		size_t oldSize = _table.size();
    
    		std::vector<Node*> newTable(newSize);
    		_table.resize(newSize);
    
    		//接着将数据重新映射过去
    		for (size_t i = 0; i < oldSize; i++)
    		{
    			Node* cur = _table[i];
    			while (cur)
    			{
    				//重新计算映射的位置
    				size_t pos = HashFunc(koft(cur->_data));
    
    				//找到位置后头插进对应位置
    				Node* next = cur->_next;
    
    				cur->_next = newTable[pos];
    				newTable[pos] = cur;
    
    				cur = next;
    			}
    			//原数据置空
    			_table[i] == nullptr;
    		}
    		//直接和新表交换,交换过去的旧表会和函数栈帧一块销毁。
    		_table.swap(newTable);
    	}
    
    	size_t pos = HashFunc(koft(data));
    	Node* cur = _table[pos];
    
    	//因为哈希桶key值唯一,如果已经在桶中则返回false
    	while (cur)
    	{
    
    		if (koft(cur->_data) == koft(data))
    		{
    			return false;
    		}
    		else
    		{
    			cur = cur->_next;
    		}
    	}
    
    	//检查完成,此时开始插入,这里选择的是头插,这样就可以减少数据遍历的次数。
    	Node* newNode = new Node(data);
    
    	newNode->_next = _table[pos];
    	_table[pos] = newNode;
    
    	++_size;
    
    	return true;
    }
    
    

    查找

    直接根据映射的位置到桶中查找数据即可

    Node* Find(const K& key)
    {
    	KeyofT koft;
    
    	size_t pos = HashFunc(key);
    	Node* cur = _table[pos];
    
    	while (cur)
    	{
    		if (koft(cur->_data) == key)
    		{
    			return cur;
    		}
    		else
    		{
    			cur = cur->_next;
    		}
    	}
    
    	return nullptr;
    }
    

    删除

    bool Erase(const K& key)
    {
    	KeyofT koft;
    
    	size_t pos = HashFunc(key);
    	Node* cur = _table[pos];
    	Node* prev = nullptr;
    
    	while (cur)
    	{
    		if (koft(cur->_data) == key)
    		{
    			//如果要删除的是第一个节点,就让下一个节点成为新的头节点,否则直接删除。
    			if (prev == nullptr)
    			{
    				_table[pos] = cur->_next;
    			}
    			else
    			{
    				prev->_next = cur->_next;
    			}
    			delete cur;
    			--_size;
    
    			return true;
    		}
    		else
    		{
    			prev = cur;
    			cur = cur->_next;
    		}
    	}
    
    	return false;
    }
    
    

    完整代码实现

    #pragma once
    #include<vector>
    #include<string>
    
    namespace lee
    {
    	//算法科学家总结出的一个增容质数表,按照这样增容的效率更高
    	const int PRIMECOUNT = 28;
    	const size_t primeList[PRIMECOUNT] = 
    	{
    	 53ul, 97ul, 193ul, 389ul, 769ul,
    	 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	 1610612741ul, 3221225473ul, 4294967291ul
    	};
    
    	/*
    	因为哈希函数的常用方法如直接定地、除留余数、平方取中等方法需要用的key值为整型,而大部分时候我们的key都是string,
    	或者某些自定义类型,这个时候就可以提供一个仿函数的接口给外部,让他自己处理如何将key转换成我们需要的整型
    	*/
    	template<class K>
    	struct Hash
    	{
    		const K& operator()(const K& key)
    		{
    			return key;
    		}
    	};
    
    	template<>
    	struct Hash<std::string>
    	{
    		const size_t & operator()(const std::string& key)
    		{
    			//BKDR字符串哈希函数
    			size_t hash = 0;
    
    			for (size_t i = 0; i < key.size(); i++)
    			{
    				hash *= 131;
    				hash += key[i];
    			}
    
    			return hash;
    		}
    	};
    
    	template<class T>
    	struct HashNode
    	{
    
    		HashNode(const T& data = T())
    			: _data(data)
    			, _next(nullptr)
    		{}
    
    		T _data;
    		HashNode<T>* _next;
    	};
    
    	template<class K, class T, class KeyofT, class Hash = Hash<K>>
    	class HashBucket
    	{
    	public:
    		typedef HashNode<T> Node;
    
    		HashBucket(size_t capacity = 10)
    			: _table(capacity)
    			, _size(0)
    		{}
    
    		~HashBucket()
    		{
    			Clear();
    		}
    		
    		size_t getNextPrime(size_t num)
    		{
    			size_t i = 0;
    
    			for (i = 0; i < PRIMECOUNT; i++)
    			{
    				//返回比那个数大的下一个质数 
    				if (primeList[i] > num)
    				{
    					return primeList[i];
    				}
    			}
    
    			//如果比所有都大,还是返回最后一个,因为最后一个已经是32位最大容量
    			return primeList[PRIMECOUNT - 1];
    		}
    
    		size_t HashFunc(const K& key)
    		{
    			Hash hash;
    
    			return hash(key) % _table.size();
    		}
    
    		bool Insert(const T& data)
    		{
    			KeyofT koft;
    
    			/*
    				因为哈希桶是开散列的链式结构,发生了哈希冲突是直接在对应位置位置进行头插,而桶的个数是固定的,而插入的数据会不断增多,
    				随着数据的增多,就可能会导致某一个桶过重,使得效率过低。
    				所以最理想的情况,就是每个桶都有一个数据。这种情况下,如果往任何一个地方插入,都会产生哈希冲突,所以当数据个数与桶的个数相同时,也就是负载因子为1时就需要进行扩容。
    			*/
    			if (_size == _table.size())
    			{
    				//按照素数表来增容
    				size_t newSize = getNextPrime(_table.size());
    				size_t oldSize = _table.size();
    
    				std::vector<Node*> newTable(newSize);
    				_table.resize(newSize);
    
    				//接着将数据重新映射过去
    				for (size_t i = 0; i < oldSize; i++)
    				{
    					Node* cur = _table[i];
    					while (cur)
    					{
    						//重新计算映射的位置
    						size_t pos = HashFunc(koft(cur->_data));
    
    						//找到位置后头插进对应位置
    						Node* next = cur->_next;
    
    						cur->_next = newTable[pos];
    						newTable[pos] = cur;
    
    						cur = next;
    					}
    					//原数据置空
    					_table[i] == nullptr;
    				}
    				//直接和新表交换,交换过去的旧表会和函数栈帧一块销毁。
    				_table.swap(newTable);
    			}
    
    			size_t pos = HashFunc(koft(data));
    			Node* cur = _table[pos];
    			
    			//因为哈希桶key值唯一,如果已经在桶中则返回false
    			while (cur)
    			{
    				
    				if (koft(cur->_data) == koft(data))
    				{
    					return false;
    				}
    				else
    				{
    					cur = cur->_next;
    				}
    			}
    
    			//检查完成,此时开始插入,这里选择的是头插,这样就可以减少数据遍历的次数。
    			Node* newNode = new Node(data);
    			
    			newNode->_next = _table[pos];
    			_table[pos] = newNode;
    
    			++_size;
    
    			return true;
    		}
    
    		bool Erase(const K& key)
    		{
    			KeyofT koft;
    
    			size_t pos = HashFunc(key);
    			Node* cur = _table[pos];
    			Node* prev = nullptr;
    
    			while (cur)
    			{
    				if (koft(cur->_data) == key)
    				{
    					//如果要删除的是第一个节点,就让下一个节点成为新的头节点,否则直接删除。
    					if (prev == nullptr)
    					{
    						_table[pos] = cur->_next;
    					}
    					else
    					{
    						prev->_next = cur->_next;
    					}
    					delete cur;
    					--_size;
    
    					return true;
    				}
    				else
    				{
    					prev = cur;
    					cur = cur->_next;
    				}
    			}
    
    			return false;
    		}
    
    		Node* Find(const K& key)
    		{
    			KeyofT koft;
    
    			size_t pos = HashFunc(key);
    			Node* cur = _table[pos];
    
    			while (cur)
    			{
    				if (koft(cur->_data) == key)
    				{
    					return cur;
    				}
    				else
    				{
    					cur = cur->_next;
    				}
    			}
    
    			return nullptr;
    		}
    		
    		void Clear()
    		{
    			//删除所有节点
    			for (size_t i = 0; i < _table.size(); i++)
    			{
    				Node* cur = _table[i];
    
    				while (cur)
    				{
    					Node* next = cur->_next;
    					delete cur;
    					cur = next;
    				}
    
    				_table[i] = nullptr;
    			}
    		}
    
    	private:
    		std::vector<Node*> _table;
    		size_t _size;
    	};
    };
    
    展开全文
  • 哈希概念 常规搜索:   数据杂乱无章——-&amp;amp;gt;顺序查找—–&amp;amp;gt;时间复杂度0(n)。   数据有序—–&amp;amp;gt;二分查找——&amp;amp;gt;时间复杂度0(log(n))。   建立二叉...

    哈希概念

    常规搜索:
      数据杂乱无章——->顺序查找—–>时间复杂度0(n)。
      数据有序—–>二分查找——>时间复杂度0(log(n))。
      建立二叉搜索树—–>时间复杂度0(n)(单支树)。
    理想的搜索方法是:可以不经过任何比较,一次直接从表中得到要搜索的元素,如果构造一种存储结构,通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么查找时通过该函数可以很快的找到该元素。
    当该结构中:

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

    该方法即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表或者散列表。
    这里写图片描述
    用该方法进行搜索不必进行多次关键码的比较,因此搜索速度比较快。但是哈希函数中一般会选一个最接近m(空间大小)的质数作为除数。
    问题:按照上述哈希方法,向集合中插入2,会出现什么问题??

      对于两个数据元素的关键字M,N(M!=N),但有Hash(M)=Hash(N),即不同的关键字算出了相同的哈希地址,该现象称为哈希冲突或哈希碰撞,把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
    那么如何处理哈希冲突呢????


    发生哈希冲突的原因:
      1. 哈希函数设置不合理
       考虑重新设计哈希函数
        哈希函数设计原则:
          ①.哈希函数的定义域必须包含需要存储的全部关键码,如果散列表有m个地址,其值域必须在0~m-1之间。
          ②.哈希函数计算出来的地址能均匀的分布在整个空间中。
          ③.哈希函数应该比较简单。
    具体解决方法:

    • 闭散列:开放定值法,当发生哈希冲突时,如果哈希表未被装满,说明哈希表必然还有空位置,那么就把关键字存放到表中“下一个”空位置去。
    • 开散列:链地址法(开链法)首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一个集合,每一个子集称为一个桶,各个桶中的元素通过一个单链表链接起来。

    本篇我们主要讲解闭散列:


    闭散列:
      当发生哈希冲突时,如果哈希表未被装满,说明哈希表必然还有空位置,那么就把关键字存放到表中“下一个”空位置去。
      那如何寻找下一个空余位置?

    1. 线性探测
      从发生冲突的位置开始,依次继续向后探测,直到有空位置。
    插入时:使用哈希函数找到待插入元素在哈希表中的位置,如果该位置没有元素则直接插入,如果该位置有元素但不是待插入元素则发生哈希冲突,使用线性探测找到下一个空位置,在找空位置的路上如果遇到元素与待插入元素相同则不插入(即哈希表中不允许有相同的元素),没有遇到等找到空位置就插入。
    这里写图片描述
    说明: 由于哈希表里不能有相同的元素,所以删除元素时就不能随便删除元素,若直接删除极易导致哈希表中元素重复。
    这里写图片描述
    优点: 简单
    缺陷: 一旦发生哈希冲突,所有的冲突连在一起,容易产生数据堆积。
    那如何缓解呢??
    负载因子:
      散列表的负载因子定义为:α=填入表中的元素个数 / 散列表的长度。α是散列表装满程度的标志因子,由于表长是定值,α与填入表中的元素个数成正比,所以,α越大,填入表中的元素就越多,产生冲突的可能性就越大;反之,α越小,标明填入表中的元素就越少,产生冲突的可能性就越小。一般应该严格控制在0.7~0.8之间。超过0.8,查表时的不命中率按照指数曲线上升。


    1. 二次探测
        发生哈希冲突时,二次探测寻找下一个空位置的公式为:H(i)=(H(0)+i^2)^2%m
      这里写图片描述
      优点:不存在数据堆积。
      缺点: 当元素较多时需要比较很多次。

    代码实现:
    .h文件

    #include<assert.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include<math.h>
    #include<assert.h>
    #include<stdio.h>
    //哈希表的状态
    typedef enum state
    {
        EMPTY, //空
        EXIST, //存在
        DELETE,//删除
    }state;
    
    typedef int DataType;
    typedef struct Elem
    {
        DataType _data;
        enum state _state;
    }Elem;
    
    typedef struct Size
    {
        int size; //哈希表中有效元素个数
        int del;  //哈希表被删除元素的个数
    }Size;
    //哈希表
    typedef struct HashTable
    {
        Elem *data;
        int capacity;
        Size size;
    }HashTable;
    
    
    
    //初始化哈希表
    void InitHashTable(HashTable *hashtable);
    //插入哈希表
    void InsertHashTable(HashTable *hashtable, DataType data);
    //删除哈希表
    int  DeleteHashTable(HashTable *hashtable, DataType data);
    //查找
    int FindHashTable(HashTable *hashtable, DataType data);
    //判空
    int EmptyHashTable(HashTable *hashtable);
    //哈希表元素个数
    int SizeHashTable(HashTable *hashtable);
    //打印哈希表
    void print(HashTable *hashtable);
    //销毁哈希表
    void DestroyHashTable(HashTable *hashtable);
    

    HashTable.c

    #include"HashTable.h"
    
    //素数表
    #define primesize 28
    unsigned long int _PrimeList[primesize] = {
        53ul, 97ul, 193ul, 389ul, 769ul,
        1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
        49157ul, 98317ul, 196613ul, 39324ul, 786433ul,
        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
        60331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
        1610612741ul, 3221225473ul, 4294967291ul
    };
    //素数
    int Prime(int capacity)
    {
        int i = 0;
        for (i = 0; i < primesize; i++)
        {
            if ((int)_PrimeList[i] >= capacity)
            {
                return _PrimeList[i];
            }
        }
        return _PrimeList[primesize - 1];
    }
    //初始化哈希表
    void InitHashTable(HashTable *hashtable)
    {
        int i = 0;
        int capacity;
        assert(hashtable);
        //初始化容量
        capacity = 5;
        hashtable->capacity = Prime(capacity);
        //初始化data
        hashtable->data = (Elem*)malloc(hashtable->capacity*sizeof(Elem));
        if (hashtable->data == NULL)
        {
            assert(0);
            return ;
        }
        //初始化数组
        for (i = 0; i < hashtable->capacity; i++)
        {
            hashtable->data[i]._data = 0;
            hashtable->data[i]._state = EMPTY;
        }
    
        //初始化元素
        hashtable->size.size = 0;
        hashtable->size.del = 0;
    }
    
    
    //哈希函数
    int HashFun(HashTable* hashtable,DataType data)
    {
        assert(hashtable);
        return data % hashtable->capacity;
    }
    //判断是否需要扩容
    Elem * ExpandCapacity(HashTable *hashtable)
    {
        int i = 0;
        int addr = 0;
        int newcapacity = 0;
        int oldcapacity = hashtable->capacity;
        Elem *new = NULL;
        //扩容量
        newcapacity = Prime(hashtable->capacity);
        //开辟新空间
        new= (Elem *)malloc(newcapacity*sizeof(Elem));
        if (new == NULL)
        {
            assert(0);
            return NULL;
        }
    
        //初始化新空间
        for (i = 0; i < newcapacity; i++)
        {
            new[i]._data = 0;
            new[i]._state = EMPTY;
        }
    
        hashtable->capacity = newcapacity;
        //搬元素
        for (i = 0; i < oldcapacity; i++)
        {
            if (hashtable->data[i]._state == EXIST)
            {
                //新哈希地址
                addr = HashFun(hashtable, hashtable->data[i]._data);
                //插入新表
                while (new[addr]._state != EMPTY)
                {
    #if 0
                    //线性探测
                    addr++;
                    if (addr == hashtable->capacity)
                    {
                        addr = 0;
                    }
    #else
                    //二次探测
                    //二次探测
                    i++;
                    addr = addr + 2 * i + 1;
                    addr = addr%hashtable->capacity;
                }
    #endif
                new[addr]._data=hashtable->data[i]._data;
                new[addr]._state = EXIST;
            }
        }
        hashtable->size.del = 0;
        free(hashtable->data);
        hashtable->data = new;
        return new;
    }
    //插入哈希表
    void InsertHashTable(HashTable *hashtable, DataType data)
    {
        int i = 0;
        assert(hashtable);
        //判断是否扩容,如果表中的个数超过自己的哈希因子,则需要扩容
        if ((hashtable->size.del + hashtable->size.size) * 10 / hashtable->capacity >= 7)
        {
            ExpandCapacity(hashtable);
        }
        int Add = 0;
        Add = HashFun(hashtable,data);
        while (hashtable->data[Add]._state!=EMPTY )
        {
            //如果有与data相同的结点则不插入
            if (hashtable->data[Add]._state == EXIST&&
                hashtable->data[Add]._data == data)
            {
                return;
            }
    #if 0
            //线性探测
            Add++;
            if (Add == hashtable->capacity)
            {
                Add = 0;
            }
    #else
            //二次探测
            i++;
            Add = Add + 2 * i + 1;
            Add = Add%hashtable->capacity;
        }
    #endif
        hashtable->data[Add]._data = data;
        hashtable->data[Add]._state = EXIST;
        hashtable->size.size++;
    }
    
    //删除哈希表
    int  DeleteHashTable(HashTable *hashtable, DataType data)
    {
        int Add = 0;
        int i = 0;
        assert(hashtable);
        if (hashtable->size.size == 0)
        {
            //哈希表为空,无法删除
            printf("无法删除\n");
            return -1;
        }
        else
        {
            Add = HashFun(hashtable, data);
            while (hashtable->data[Add]._state != EMPTY)
            {
                if (hashtable->data[Add]._state == EXIST
                    &&hashtable->data[Add]._data == data)
                {
                    hashtable->data[Add]._state = DELETE;
                    hashtable->size.del++;
                    hashtable->size.size--;
                    return 1;
                }
                else
                {
    #if 0
                    Add++;
                    if (Add == hashtable->capacity)
                    {
                        Add = 0;
                    }
    #else
                    //二次探测
                    i++;
                    Add = Add + 2 * i + 1;
                    Add = Add % hashtable->capacity;
    #endif
                }
            }
            //没有找到元素,无法删除
            return -1;
        }
    }
    
    //查找
    int FindHashTable(HashTable *hashtable, DataType data)
    {
        int Add = 0;
        int i = 0;
        assert(hashtable);
        if (hashtable->size.size == 0)
        {
            printf("哈希表为空!\n");
            return -1;
        }
        else
        {
            Add = HashFun(hashtable, data);
            while (hashtable->data[Add]._state != EMPTY )
            {
                if (hashtable->data[Add]._state==EXIST
                    &&hashtable->data[Add]._data == data)
                {
                    return Add;
                }
    #if 0
                Add++;
                if (Add == hashtable->capacity)
                {
                    Add = 0;
                }
    #else
                //二次探测
                i++;
                Add = Add + 2 * i + 1;
                Add = Add % hashtable->capacity;
    #endif
            }
            return -1;
        }
    }
    
    //判空
    int EmptyHashTable(HashTable *hashtable)
    {
        assert(hashtable);
        return hashtable->size.size == 0;
    }
    //哈希表元素个数
    int SizeHashTable(HashTable *hashtable)
    {
        assert(hashtable);
        return hashtable->size.size;
    }
    
    //打印哈希表
    void print(HashTable *hashtable)
    {
        int i = 0;
        for (i = 0; i < hashtable->capacity; i++)
        {
            if (hashtable->data[i]._state == EMPTY)
            {
                printf("add=%d EMPTY %d\n", i,hashtable->data[i]._data);
            }
            else if (hashtable->data[i]._state == DELETE)
            {
                printf("add=%d DELETE %d\n",i, hashtable->data[i]._data);
            }
            else
            {
                printf("add=%d EXIST %d\n", i,hashtable->data[i]._data);
            }
        }
    }
    
    //销毁哈希表
    void DestroyHashTable(HashTable *hashtable)
    {
        assert(hashtable);
        free(hashtable->data);
        hashtable->data = NULL;
        hashtable->size.del = 0;
        hashtable->size.size = 0;
    }

    测试.c

    #include"HashTable.h"
    
    
    void Test()
    {
        HashTable hashtable;
    
        //初始化哈希表
        InitHashTable(&hashtable);
        //插入哈希表
        InsertHashTable(&hashtable, 10);
        InsertHashTable(&hashtable, 3);
        InsertHashTable(&hashtable, 19);
        InsertHashTable(&hashtable, 2);
        InsertHashTable(&hashtable, 20);
        //删除哈希表
        DeleteHashTable(&hashtable, 2);
    
    
        InsertHashTable(&hashtable, 4);
        InsertHashTable(&hashtable, 6);
        InsertHashTable(&hashtable, 108);
        InsertHashTable(&hashtable, 12);
        InsertHashTable(&hashtable, 8);
        //删除哈希表
        DeleteHashTable(&hashtable, 20);
        DeleteHashTable(&hashtable, 6);
    
        //查找
        if (FindHashTable(&hashtable, 19)!= -1)
        {
            printf("%d的哈希地址为:%d\n", 19, FindHashTable(&hashtable, 19));
        }
        else
        {
            printf("没有找到!\n");
        }
        printf("哈希表元素个数:%d\n", SizeHashTable(&hashtable));
    
        //判空
        if (EmptyHashTable(&hashtable))
        { 
            printf("哈希表为空!\n");
        }
        else
        {
            printf("哈希表不为空!\n");
        }
        print(&hashtable);
        //销毁哈希表
        DestroyHashTable(&hashtable);
    
    }
    int main()
    {
        Test();
        system("pause");
        return 0;
    }

    这里写图片描述
    这里写图片描述

    展开全文
  • 哈希表

    2021-05-07 16:09:25
    哈希表特点2.1 哈希冲突2.2 负载因子 1. 哈希表定义 哈希表又称为散列表 是一种使用哈希函数组织的数据结构,支持快速插入和搜索。 2.哈希表特点 2.1 哈希冲突 哈希函数的不完美会导致哈希冲突,哈希冲突不可避免。 ...

    1. 哈希表定义

    哈希表又称为散列表 是一种使用哈希函数组织的数据结构,支持快速插入和搜索。
    有两种类型的哈希表:哈希集合、哈希映射。
    哈希集合是集合的实现方式之一,用于存储非重复值。
    哈希映射是映射的实现方式之一,用于存储键值对。

    2.哈希表特点

    2.1 哈希冲突

    哈希函数的不完美会导致哈希冲突,哈希冲突不可避免。

    2.2 负载因子

    负载因子又称为装填因子,反映了哈希表的装满程度。
    比较合理的负载因子为0.7

    3. 哈希冲突解决

    3.1 线性试探法

    3.2 链地址法

    3.3 再哈希法

    3.4 公共溢出区法

    展开全文
  • 数据结构实验报告四哈希表查找名字字符串 实验题目哈希表查找名字字符串 实验目标 输入一组名字至少50个将其保存并利用哈希表查找输出哈希查找冲突次数哈希表负载因子查找命中率 数据结构 哈希表和数组二维二维数组...
  • 首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率。 1. 哈希函数的设计 哈希函数的定义...
  • 文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是:闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中,元素关键码与其...
  • 哈希表 概念: 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2Nlog_2 Nlog2​N),...
  • 关于Redis中rehash的负载因子问题

    千次阅读 2021-03-19 13:33:37
    哈希表中的键值对随着不断进行的操作增加或减少,为了将哈希表负载因子维持在较为合理的范围内,程序需对哈希表的大小进行相应的扩展或者收缩,而rehash(重新散列)操作就可以完成这项工作。 2. 负载因子的概念 ...
  • redis设计与实现 书中说,当服务器正处于BGSAVE或者BGREWRITEAOF时,并且哈希表负载因子大于5, 会进行哈希表的扩展。。。 想请教一下。。。为什么这里的负载因子会大于1呢?这个5哪里来的额?
  • 哈希表的实现

    2019-10-14 23:18:18
    负载因子=哈希表中的数据个数/数组的长度 负载因子越少,冲突率越低 把数组长度变大 事先规定好一个阙值,来控制size 一般情况下来讲,哈希表主要涉及两种办法 1.线性探测(主要是考试出题) 求成功的平均查找长度...
  • HashMap中负载因子的意义是什么?

    千次阅读 2020-05-09 16:41:35
    负载因子是在自动增加其哈希表容量之前允许哈希表获得的满度的度量。 当哈希表中的条目数超过负载因子和当前容量的乘积时,哈希表将被重新哈希 (即,内部数据结构将被重建),因此哈希表的存储桶数大约为两倍。 ...
  • 哈希表扩容简述

    2020-10-24 00:52:40
    影响哈希表扩容的因素有两个,本身的容量CapacityCapacityCapacity和负载因子LoadFactorLoadFactorLoadFactor,当前的哈希表大小大于Size>Threshold=Capacity∗LoadFactorSize>Threshold=Capacity*...
  • 哈希表笔记

    2019-05-02 23:14:06
    负载因子: 填入中的元素个数 / 散列表的长度 哈希冲突(哈希碰撞): 不同的Key映射到相同的哈希地址 冲突处理: 开发定址法 遇到冲突顺着原来的哈希地址逐个向下查找直到找到空闲地址,然后插入 拉链法 类似于邻...
  • 哈希表实现

    2020-03-26 21:12:29
    哈希和树的区别一个是表结构,一个是树结构 ...注意:任何情况下,哈希表都不会存满数据,数据越多,哈希冲突的概率越大,一般当负载因子大于或者等于某一个阈值(0.7)时, 就需要进行扩容 开散列: 哈希桶就是...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 272
精华内容 108
关键字:

哈希表负载因子