精华内容
下载资源
问答
  • 哈希 哈希算法理解为一种将很大的数据块经过哈希计算,用一个很小的字符串来标识这个很大的数据块 对应的<key,value>模型 key表示计算的哈希值,value表示存放的...

    ###哈希

    哈希算法理解为一种将很大的数据块经过哈希计算,用一个很小的字符串来标识这个很大的数据块
    对应的<key,value>模型
    key表示计算的哈希值,value表示存放的数值
    对应可以实现 key = func(value) 的函数称为哈希函数

    一般情况都是采用value % length计算哈希值
    很明显的一般的数据结构不会太大,这样计算的哈希值的方法就不能保证每一个value对应的key都是不重复的,就出现的哈希冲突的问题。
    ####1.哈希冲突
    出现多个不同的数据(value) 计算得到的哈希值(key)相同的情况,称为哈希冲突

    ####2.如何解决哈希冲突
    **(a)开放定址法 (闭散列) **
    生成一个Hash序列 H1 ,H2, H3, H4…
    第一个冲突了,就继续下一个

    H0 = value % length
    Hi = (H0 + di) % lenght

    1. 线性探测再散列
      di = 1,2,3,4,…(也是用到最多的方法)
      线性探测容易产生“聚集”现象。当表中的第i、i+1、i+2的位置上已经存储某些关键字,则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上,这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为“聚集”。聚集对查找效率有很大影响。
    2. 平方探测再散列
      di = 1^2 , 2^2, 3^2…
      二次探测能有效避免“聚集”现象,但是不能够探测到哈希表上所有的存储单元,但是至少能够探测到一半。
    3. 随机探测再散列
      di =伪随机数产生的 di
      这里写图片描述
      散列因子
      用来描述哈希表的密集程度
      a = 元素个数 / 哈希表长度
      a 越大,产生冲突的概率就越大,a越小,空间浪费就大,散列因子一般控制在0.7~0.8左右

    (b)链地址法 (开散列、哈希桶)
    将存在哈希冲突的元素组织成链表,哈希表中存放该链表的链首地址
    这里写图片描述
    (c)再哈希
    采用多个哈希函数的方法,如果使用第一个哈希函数计算的key值冲突了,就采用第二个哈希函数进行,依次类推。这样就要计算多次,查找的时候同样

    (d)建立公共溢出区
    另外开辟一块空间,将哈希表分为基本表和溢出表两部分,存在哈希冲突的数据存放再溢出表部分,这种方法若是哈希冲突严重,则效率很低。

    ###位图
    用每一个比特位的 0/1 来表示是否存在,一般用来判断数字是否存于一堆数字中

    ###波隆过滤器
    用来判断字符串是否存在于一长串字符串中。因为冲突率比较大,一般用再哈希的方法解决冲突

    展开全文
  • 文章目录哈希哈希(散列)函数 哈希 哈希(散列)是一种数据结构,通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系,如果要查、改数据,就可以直接到对应的位置去,使得...


    哈希

    哈希(散列)是一种数据结构,通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系,如果要查、改数据,就可以直接到对应的位置去,使得时间复杂度达到了 O(1) ,原因如下:

    若结构中存在和 关键字K 相等的记录,则必定在 f(K) 的存储位置上。由此,不需比较便可直接取得所查记录。

    称上面的对应关系 f散列函数(Hash function),按这个映射关系事先建立的表为散列表,这一映象过程称为 散列造表散列 ,最终所得的存储位置称 散列地址


    哈希(散列)函数

    哈希函数用来建立元素与其存储位置的映射关系。

    对于哈希函数来说,必须具有以下特点:

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

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


    常见的哈希函数

    1. 直接定址法(常见)
      哈希函数:Hash(Key) = A * Key + B
      这是最简单的哈希函数,直接取关键字本身或者他的线性函数来作为散列地址。

    2. 除留余数法(常见)
      哈希函数 :Hash(key) = key % capacity
      几乎是最常用的哈希函数,用一个数来对 key 取模,一般来说这个数都是容量。

    3. 平方取中法
      对关键字进行平方,然后取中间的几位来作为地址。

    4. 折叠法
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和(去除进位),并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况.

    5. 随机数法
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random(key),其中 random 为随机数函数。通常应用于关键字长度不等时。

    6. 数学分析法
      分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。


    字符串哈希函数

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

    常见的字符串哈希算法有 BKDSDBRS 等,这些算法大多通过一些公式来对字符串每一个 字符的 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;
    	}
    };
    

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


    哈希冲突

    对不同的关键字可能得到同一散列地址,即 key1≠key2 ,而 f(key1)=f(key2) ,这种现象称碰撞(哈希冲突)

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

    查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高;产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

    1. 散列函数是否均匀;
    2. 处理冲突的方法;
    3. 散列表的负载因子(装填因子)。

    第一点取决于上面讲过的哈希函数,不再赘述,下面详细讲一下2、3点。

    处理冲突的方法可分为两类:开散列方法( open hashing,也称为拉链法,separate chaining )闭散列方法( closed hashing,也称为开地址方法,open addressing )。这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。


    闭散列(开放地址法)

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

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

    2. 二次探测
      二次探测即为从发生冲突的位置开始,每次往后探测 ±k2(k<=m/2,m为散列表长) 个位置,如:12,-(12),22,-(22) 等。
      这样的话就将每次探测的效率从 O(N) 提升到了 O(logN) ,即使有着大量的冲突堆积,也不会导致效率过低。

    3. 伪随机数探测
      这种方法并不常见,实现方法是:创建一个伪随机数序列,根据序列内容决定每次往后探测的长度。


    开散列(链地址法/拉链法)

    先用哈希函数计算每个数据的散列地址,把具有相同地址的元素归于同一个集合之中,把该集合处理为一个链表,链表的头节点存储于哈希表之中。

    在这里插入图片描述

    链地址法在每一个映射位置都建立起一个链表(数据过多时可能会转为建立红黑树),将每次插入的数据都直接连接上这个链表,这样就不会像闭散列一样进行大量的探测,但是如果链表过长也会导致效率低下。


    负载因子以及增容

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

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

    对于闭散列

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

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

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

    这也是 STLunordered_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
    	};
    
    

    hashmap 的负载因子为什么默认是 0.75

    比如说当前的容器容量是 16,负载因子是 0.75,16*0.75=12,也就是说,当容量达到了 12 的时候就会进行扩容操作。而负载因子定义为 0.75 的原因是:

    • 当负载因子是 1.0 的时候,也就意味着,只有当散列地址全部填充了,才会发生扩容。意味着随着数据增长,最后势必会出现大量的冲突,底层的红黑树变得异常复杂。虽然空间利用率上去了,但是查询时间效率降低了。
    • 负载因子是 0.5 的时候,这也就意味着,当数组中的元素达到了一半就开始扩容。虽然时间效率提升了,但是空间利用率降低了。 诚然,填充的元素少了,Hash冲突也会减少,那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。但是,这时候空间利用率就会大大的降低,原本存储 1M 的数据,现在就意味着需要 2M 的空间。

    对于开散列结构

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

    所以最理想的情况,就是每个桶都有一个数据。这种情况下,如果往任何一个地方插入,都会产生哈希冲突,所以当数据个数与桶的个数相同时,也就是负载因子为 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;
    };
    

    插入

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

    • 如果映射位置已存在数据,并且值与当前数据不同,则说明产生冲突,继续往后查找
    • 如果映射位置的数据与插入的数据相同,则说明此时数据已经插入过,此时就不需要再次插入
    • 如果映射位置的状态为删除或者空,则代表着此时表中没有这个数据,在这个位置插入即可
    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;
    	}
    }
    

    完整代码

    #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;
    	};
    };
    
    展开全文
  • 文章目录 哈希 哈希函数 常见的哈希函数 字符串哈希函数 哈希冲突 闭散列的解决方法 开散列的解决方法 负载因子以及增容 对于闭散列 对于开散列结构 具体实现 哈希表(闭散列) 插入 查找 删除 完整代码实现 哈希桶...

    哈希

    在之前介绍的数据结构中,元素与其所存储的位置之间没有对应的关系,所以在查找的时候就需要经过多次的比较,才能找到具体的位置。对于顺序结构来说,这样查找的时间复杂度一般都是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;
    	};
    };
    
    展开全文
  • 本文主要对以下内容进行介绍: 为什么HashMap需要加载因子?...HashMap的底层是哈希表,是存储键值对的结构类型,它需要通过一定的计算才可以确定数据在哈希表中的存储位置: static final int hash(O...

    本文主要对以下内容进行介绍:

    • 为什么HashMap需要加载因子?

    • 解决冲突有什么方法?

    • 为什么加载因子一定是0.75?而不是0.8,0.6?

    若文章有不正之处,或难以理解的地方,请多多谅解,欢迎指正。

    为什么HashMap需要加载因子?

    HashMap的底层是哈希表,是存储键值对的结构类型,它需要通过一定的计算才可以确定数据在哈希表中的存储位置:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    

    // AbstractMap

    public int hashCode() {
         int h = 0;
         Iterator<Entry<K,V>> i = entrySet().iterator();
         while (i.hasNext())
             h += i.next().hashCode();
    
         return h;
    }
    

    一般的数据结构,不是查询快就是插入快,HashMap就是一个插入慢、查询快的数据结构。

    但这种数据结构容易产生两种问题:

    ① 如果空间利用率高,那么经过的哈希算法计算存储位置的时候,会发现很多存储位置已经有数据了(哈希冲突);

    ② 如果为了避免发生哈希冲突,增大数组容量,就会导致空间利用率不高。

    而加载因子就是表示Hash表中元素的填满程度。

    加载因子 = 填入表中的元素个数 / 散列表的长度

    加载因子越大,填满的元素越多,空间利用率越高,但发生冲突的机会变大了;

    加载因子越小,填满的元素越少,冲突发生的机会减小,但空间浪费了更多了,而且还会提高扩容rehash操作的次数。

    冲突的机会越大,说明需要查找的数据还需要通过另一个途径查找,这样查找的成本就越高。因此,必须在“冲突的机会”与“空间利用率”之间,寻找一种平衡与折衷。

    所以我们也能知道,影响查找效率的因素主要有这几种:

    散列函数是否可以将哈希表中的数据均匀地散列?

    怎么处理冲突?

    哈希表的加载因子怎么选择?

    本文主要对后两个问题进行介绍。

    解决冲突有什么方法?

    1. 开放定址法

    Hi = (H(key) + di) MOD m,其中i=1,2,…,k(k<=m-1)

    H(key)为哈希函数,m为哈希表表长,di为增量序列,i为已发生冲突的次数。其中,开放定址法根据步长不同可以分为3种:

    1.1 线性探查法(Linear Probing):di = 1,2,3,…,m-1

    简单地说,就是以当前冲突位置为起点,步长为1循环查找,直到找到一个空的位置,如果循环完了都占不到位置,就说明容器已经满了。举个栗子,就像你在饭点去街上吃饭,挨家去看是否有位置一样。

    1.2 平方探测法(Quadratic Probing):di = ±12, ±22,±32,…,±k2(k≤m/2)

    相对于线性探查法,这就相当于的步长为di = i2来循环查找,直到找到空的位置。以上面那个例子来看,现在你不是挨家去看有没有位置了,而是拿手机算去第i2家店,然后去问这家店有没有位置。

    1.3 伪随机探测法:di = 伪随机数序列

    这个就是取随机数来作为步长。还是用上面的例子,这次就是完全按心情去选一家店问有没有位置了。

    但开放定址法有这些缺点:

    这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好;

    删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点;

    如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。

    2. 再哈希法

    Hi = RHi(key), 其中i=1,2,…,k

    RHi()函数是不同于H()的哈希函数,用于同义词发生地址冲突时,计算出另一个哈希函数地址,直到不发生冲突位置。这种方法不容易产生堆集,但是会增加计算时间。

    所以再哈希法的缺点是:

    增加了计算时间。

    3. 建立一个公共溢出区

    假设哈希函数的值域为[0, m-1],设向量HashTable[0,…,m-1]为基本表,每个分量存放一个记录,另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录,一旦发生冲突,不管他们哈希函数得到的哈希地址是什么,都填入溢出表。

    但这个方法的缺点在于:

    查找冲突数据的时候,需要遍历溢出表才能得到数据。

    4. 链地址法(拉链法)

    将冲突位置的元素构造成链表。在添加数据的时候,如果哈希地址与哈希表上的元素冲突,就放在这个位置的链表上。

    拉链法的优点:

    处理冲突的方式简单,且无堆集现象,非同义词绝不会发生冲突,因此平均查找长度较短;

    由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况;

    删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。

    拉链法的缺点:

    需要额外的存储空间。

    从HashMap的底层结构中我们可以看到,HashMap采用是数组+链表/红黑树的组合来作为底层结构,也就是开放地址法+链地址法的方式来实现HashMap。

    至于为什么在JDK1.8的时候要运用到红黑树,下篇文章会介绍。

    为什么HashMap加载因子一定是0.75?而不是0.8,0.6?

    从上文我们知道,HashMap的底层其实也是哈希表(散列表),而解决冲突的方式是链地址法。HashMap的初始容量大小默认是16,为了减少冲突发生的概率,当HashMap的数组长度到达一个临界值的时候,就会触发扩容,把所有元素rehash之后再放在扩容后的容器中,这是一个相当耗时的操作。

    而这个临界值就是由加载因子和当前容器的容量大小来确定的:

    临界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR

    即默认情况下是16x0.75=12时,就会触发扩容操作。

    那么为什么选择了0.75作为HashMap的加载因子呢?笔者不才,通过看源码解释和大佬的文章,才知道这个跟一个统计学里很重要的原理——泊松分布有关。

    泊松分布是统计学和概率学常见的离散概率分布,适用于描述单位时间内随机事件发生的次数的概率分布。有兴趣的读者可以看看维基百科或者阮一峰老师的这篇文章:泊松分布和指数分布:10分钟教程

    等号的左边,P 表示概率,N表示某种函数关系,t 表示时间,n 表示数量。等号的右边,λ 表示事件的频率。

    在HashMap的源码中有这么一段注释:

    * Ideally, under random hashCodes, the frequency of
    * nodes in bins follows a Poisson distribution
    * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
    * parameter of about 0.5 on average for the default resizing
    * threshold of 0.75, although with a large variance because of
    * resizing granularity. Ignoring variance, the expected
    * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
    * factorial(k)). The first values are:
    * 0:    0.60653066
    * 1:    0.30326533
    * 2:    0.07581633
    * 3:    0.01263606
    * 4:    0.00157952
    * 5:    0.00015795
    * 6:    0.00001316
    * 7:    0.00000094
    * 8:    0.00000006
    * more: less than 1 in ten million
    

    笔者拙译:在理想情况下,使用随机哈希码,在扩容阈值(加载因子)为0.75的情况下,节点出现在频率在Hash桶(表)中遵循参数平均为0.5的泊松分布。忽略方差,即X = λt,P(λt = k),其中λt = 0.5的情况,按公式:

    计算结果如上述的列表所示,当一个bin中的链表长度达到8个元素的时候,概率为0.00000006,几乎是一个不可能事件。

    所以我们可以知道,其实常数0.5是作为参数代入泊松分布来计算的,而加载因子0.75是作为一个条件,当HashMap长度为length/size ≥ 0.75时就扩容,在这个条件下,冲突后的拉链长度和概率结果为:

    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    

    那么为什么不可以是0.8或者0.6呢?

    HashMap中除了哈希算法之外,有两个参数影响了性能:初始容量和加载因子。初始容量是哈希表在创建时的容量,加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。

    在维基百科来描述加载因子:

    对于开放定址法,加载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了加载因子为0.75,超过此值将resize散列表。

    ===============================================
    这句话里边(CPU缓存不命中)我的理解是通过开放地址法就能直接获取到值,不需要再通过链地址法去查找,欢迎大佬指点
    ===============================================
    在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少扩容rehash操作次数,所以,一般在使用HashMap时建议根据预估值设置初始容量,以便减少扩容操作。

    选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择。

    展开全文
  • 哈希的装填因子

    千次阅读 2018-03-20 16:05:00
    装填因子:a=n/m 其中n 为关键字个数,m为表长。加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:...
  • hash表装载因子(load factor)的计算

    千次阅读 2020-01-07 21:20:49
    今有表长为10的hash表,里面包含7个元素,所以它的装载因子为: 7 / 10 = 0.7 装载因子的计算结果请注意使用小数表示。 ...
  • 哈希算法

    千次阅读 2019-11-07 15:39:56
    哈希算法(上):如何防止数据库中的用户信息被脱库? 1.什么是哈希算法 1).任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 2)...
  • 哈希表中的装填因子

    万次阅读 多人点赞 2020-05-30 15:57:24
    装填因子:a=n/m 其中n 为关键字个数,m为表长。 加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:...
  • 哈希概念 常规搜索:   数据杂乱无章——-&amp;amp;gt;顺序查找—–&amp;amp;gt;时间复杂度0(n)。   数据有序—–&amp;amp;gt;二分查找——&amp;amp;gt;时间复杂度0(log(n))。   建立二叉...
  • 最近在看Redis设计与实现,发现Redis中的哈希表也是根据负载因子的扩容和收缩。 当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作: 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令...
  • Hash函数与算法、哈希查找、哈希冲突解决方法总结

    千次阅读 多人点赞 2019-09-01 22:02:57
    Hash哈希 1.基本概念   Hash,也叫哈希或散列,就是把任意长度的输入(也叫预映射),通过散列算法,变换成固定长度的输出,该输出就是散列值。   若结构中存在和关键字key相等的记录,则必定在H(key)的存储位置...
  • 初始容量是哈希表在创建时的容量,加载因子哈希表在其容量自动扩容之前可以达到多满的一种度量。 在维基百科来描述加载因子: 对于开放定址法,加载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时...
  • 神奇的算法:HashMap(哈希映射)

    万次阅读 多人点赞 2018-10-21 23:41:52
    HashMap,又称哈希映射或散列图。是一个用于储存键—值对(key-value)的集合,每个键—值对又称Entry,将这些Entry储存在一个数组里,这个数组就为HashMap。 一般初始的HashMap为空,如上图所示。 而HashMap最主要...
  • 哈希表 概念: 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2Nlog_2 Nlog2​N),...
  • HashMap的确有很多细节值得我们注意,正如被问到HashMap加载因子为什么是0.75?,好了废话不多说,直接上源码分享。 HashMap加载因子是什么? static final int hash(Object key) { int h; return (key == null) ?...
  • 哈希运算过程

    2020-12-22 11:54:00
    哈希运算过程 ● 使用 Entry[] 存放数据 ● 数组的默认初始容量是 16 ● 容量翻倍增长 ● 内部运算过程,由键... ■ 负载率,加载因子 0.75 ◆ 新建翻倍容量的新数组 ◆ 所有数据重新执行哈希运算放入新数组 ■ jdk1.
  • 【18】哈希算法

    2019-10-07 18:55:53
    18 哈希算法1. 什么是哈希算法?2. 哈希算法的常见应用有哪些?3. 思考4. 参考资料5. 声明 1. 什么是哈希算法? 定义 将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始...
  • 哈希

    2017-07-26 00:00:41
    哈希表概念哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的...
  • JS排序算法:冒泡法、快速排序法、选择排序法、插入排序法、哈希排序//生成数组 var arr = new Array(1000); for (var i = 0; i ; i++) { arr[i] = (Math.round(Math.random() * 1000)); }1.冒泡法 排序思想:...
  • 1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。 2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。 3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,...
  • 关于Redis中rehash的负载因子问题

    千次阅读 2021-03-19 13:33:37
    哈希表中的键值对随着不断进行的操作增加或减少,为了将哈希表的负载因子维持在较为合理的范围内,程序需对哈希表的大小进行相应的扩展或者收缩,而rehash(重新散列)操作就可以完成这项工作。 2. 负载因子的概念 ...
  • 哈希表和哈希

    千次阅读 2018-05-24 22:31:55
    哈希表简介:  哈希表是通过关键值来访问的数据结构,也就是说他通过把关键值映射到表中的一个位置来访问记录,以加快 查找速度,这个映射关系就是哈希函数,存放数据的列表叫做散列表。         首先给...
  • 哈希表原理

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,774
精华内容 17,509
关键字:

哈希因子