精华内容
下载资源
问答
  • 哈希装填因子

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

    加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.

    冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.

    因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

    转载于:https://www.cnblogs.com/jinhui666/p/8609868.html

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

    万次阅读 多人点赞 2020-05-30 15:57:24
    装填因子:a=n/m 其中n 为关键字个数,m为表长。 加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:...

    装填因子:a=n/m 其中n 为关键字个数,m为表长。

    加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.

    冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.

    因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

    展开全文
  • 文章目录哈希哈希(散列)函数 哈希 哈希(散列)是一种数据结构,通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素...哈希函数计算出来的地址能均匀分布在整个空间中(防止产生密集的哈希冲突


    哈希

    哈希(散列)是一种数据结构,通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系,如果要查、改数据,就可以直接到对应的位置去,使得时间复杂度达到了 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;
    	};
    };
    
    展开全文
  • 怎样设计哈希函数 字符串哈希算法 优秀的字符串哈希算法 怎样处理哈希冲突 一、开放定址法 1.线性探测法 2.二次探测法 3.再哈希法 二、拉链法(哈希桶) 哈希表的设计主要是为了对内存中的数据进行快速...

    目录

    怎样控制哈希表的长度

    怎样设计哈希函数

    字符串哈希算法

    优秀的字符串哈希算法

    怎样处理哈希冲突

    一、开放定址法

      1.线性探测法

      2.二次探测法

      3.再哈希法

    二、拉链法(哈希桶)


    哈希表的设计主要是为了对内存中的数据进行快速查找,它的查找时间复杂度是O(1)。设计一个哈希表的关键有三个:怎么控制哈希表的长度,怎么设计哈希函数,怎么处理哈希冲突。

    怎样控制哈希表的长度

    哈希表的长度一般是定长的,在存储数据之前我们应该知道存储的数据规模是多大,应该尽可能地避免频繁地让哈希表扩容。我们设计的哈希表的大小,必须要做到尽可能地减小哈希冲突,并且也要尽可能地不浪费空间,选择合适的哈希表的大小是提升哈希表性能的关键。

    当我们选择哈希函数的时候,经常会选择除留余数法,即用存储数据的key值除以哈希表的总长度,得到的余数就是它的哈希值。常识告诉我们,当一个数除以一个素数的时候,会产生最分散的余数(哈希值会对key有更多的依赖)。由于我们通常使用表的大小对哈希函数的结果进行模运算,如果表的大小是一个素数,那么这样我们就会尽可能地产生分散的哈希值。

    哈希表中还有一个概念就是表的装填因子(负载因子),它的值一般被定义为:

    装填因子 a = 总键值对数(下标占用数)/ 哈希表总长度装填因子 a = 总键值对数(下标占用数) /  哈希表总长度

    至于为什么要设计这样一个概念,我们可以想,如果一个哈希表中的数据装的越多,是不是越容易发生哈希冲突。如果当哈希表中满到只剩下一个下标可以插入的时候,这个时候我们还要往这个哈希表中插入数据,于是我们可能会达到一个O(n)级别的插入效率,我们甚至要遍历整个哈希表才可能找到那个能存储的位置。

    通常,我们关注的是使哈希表平均查找长度最小,把平均查找长度保证在O(1)级别。装填因子a的取值越小,产生冲突的机会就越小,但是也不能取太小,这样我们会造成较大的空间浪费。即如果我们a取0.1,而我们哈希表的长度为100,那我们只装了10个键值对就存不下了,就要对哈希表进行扩容,而剩下90个键值对空间其实是浪费了的。通常,只要a取的合适(一般取0.7-0.8之间),哈希表的平均查找长度就会是常数也就是O(1)级别的

    当然,根据数据量的不同,会有不同的哈希表的大小。当数据量小的时候,最好就是能够实现哈希表扩容的机制,即达到了哈希表当前长度的装填因子,我们就需要扩大哈希表大小,一般都是乘2。

    下面,对上面这些观点进行一个总结,来设计一个效率尽可能高的哈希表大小

    1. 确保哈希表长度是一个素数,这样会产生最分散的余数,尽可能减少哈希冲突
    2. 设计好哈希表装填因子,一般控制在0.7-0.8
    3. 确认我们的数据规模,如果确认了数据规模,可以将数据规模除以装填因子,根据这个结果来寻找一个可行的哈希表大小
    4. 当数据规模可能会动态变化,不确定的时候,这个时候我们也需要能够根据数据规模的变化来动态给我们的哈希表扩容,所以一开始需要自己确定一个哈希表的大小作为基数,然后在此基础上达到装填因子规模时对哈希表进行扩容。

    怎样设计哈希函数

    哈希函数,是用来计算存储数据的哈希值的,根据存储数据的类型,可以设计不同的哈希函数。

    一个好的哈希函数(让哈希表效率高的函数),一般都具备下面两个特点:

    1. 速度快(能够快速的计算一个key的哈希值)
    2. 能够将得到的哈希值均匀地分布在整个哈希表中,尽量不产生聚集

    通常一个哈希函数具有下面的形式:哈希值 = 计算后的存储值 / 哈希表的大小

    对于如果存储的数是整数这种类型,我们完全可以不用计算,直接将整数的值作为上式中计算后的存储值。

    而对于非整数,如字符串这种类型,我们要设计一个相对较好的算法,来计算出它们的存储值。

    下面介绍一些常见的字符串哈希算法,其他类型的数据都可以用相似的思路来设计适合自己的哈希算法。

    字符串哈希算法

    马上就能想到的算法:简单地将字符串中每个字符的ASCII码加起来

    size_t stringHash(const string& key){
        size_t hashKey = 0;
     
        for(size_t i = 0; i < key.size(); ++i)
            hashKey += key[i];
        
        return hashKey;
    }

    用上面的方法可以很快地算出哈希值,但是如果表很大时,则函数就不能很好的分配。比如我的表的大小是10000,即我的数据规模大概是7000个左右(取装填因子为0.7),但是我的字符最多只有8个字符长,由于ASCII码最大值是127,因此hash函数计算出来的哈希值只能在0-1016之间取值,其中127 * 8 =1016,这就会有一种聚集的效果,这就不是我们上面提到的两点想要的,我们要尽可能地避免聚集。

    这个方法可能是刚接触字符串哈希函数的人会马上想到的,但其实我们有很多的优秀的字符串哈希算法。

    优秀的字符串哈希算法

    BKDR哈希算法

    size_t BKDR_hash(const string& key){
        size_t hashKey = 0;
        size_t seed = 131;    //也可以是31 131 1313 13131 131313
        for(size_t i = 0; i < key.size(); ++i)
            hashKey += hashKey * seed + key[i];
     
        return hashKey;
    }

    根据上面的算法,我们就可以根据结果得到非聚合的一些哈希值。

    这个算法是效率很高的一个算法,其他的字符串算法可以看这里:字符串哈希算法,是人家总结的一篇文章,涵盖了当今很多的哈希算法。

    怎样处理哈希冲突

    所谓哈希冲突,就是两个key值经过哈希函数计算以后得到了相同的哈希值,而一个下标只能存放一个key,这就产生了哈希冲突。

    产生了哈希冲突,我们就要解决。选择一个好的解决哈希冲突的方法,也是提高哈希表效率的关键。

    一、开放定址法

    当冲突发生时,通过查找哈希表的一个空位,将数据填入。

    根据查找空位时,查找下标的增量取值方式,再细分为三种:

      1.线性探测法

    线性探测空位。当数据通过哈希函数计算应该放在 i 这个位置,但是 i 这个位置已经有数据了,那么接下来就应该查看 i+1 位置是否空闲,再查看 i+2 位置,依次类推,直至找到空位置。

    需要注意的是,当哈希表中接近被填满时,向表中插入数据就会效率很低,当hash表真的被填满了,这时候算法应该停止,在这之前应该对数组进行扩展,对hash表中的数据进行转移。

    聚集现象:当哈希表越来越满时,这导致产生非常长的探测长度,后续的数据插入将会非常费时。通常数据超过三分之二满时性能下降严重,因此设计哈希表关键确保不会超过这个数据容量的一半,最多不超过三分之二。

      2.二次探测法

    刚开始产生冲突的位置基础之上±n²(n从1开始,1,2,3.....)探测。

    ​​​​​​​

    二次探测可以消除在线性探测中产生的聚集问题,但是二次探测还是会产生一种更明确更细的聚集:二次聚集。二次聚集是在二次探测的基础上产生的现象。

    二次探测并不常用,解决聚集问题还是有一种更好的办法:再哈希法。

      3.再哈希法

    再哈希法是在二次探测法的基础上将步长的改进:当第一次哈希发生冲突时,第二次哈希得到的结果是索引需要加的值。这样不同的key各自对应着不同的探测步长,发生聚集的几率大大降低。

    缺点:每次冲突都要重新哈希,计算时间增加。

    二、拉链法哈希桶

    每个下标中存的都是一个链表,相同哈希值的key直接插入到链表。

    这种方法的特点是表的大小和存储的数据数量差不多(大不了每个下标都只放一个节点,如果下标一样的都是放在同一下标的链表中,并没有占据新的下标),因此哈希桶的方法没有特别依赖于装载因子,哈希表快满时,它还是可以做到较好的效率,而开放地址法就需要保证装载因子。

    拉链法的缺点:

    • 它需要稍微多一点的空间来存放元素,因为还要有一个指向下一个节点的指针。
    • 每次探测也要花费较多的时间,因为它需要间接引用指针,而不是直接访问元素。

    但其实这些缺点是微不足道的,所以实际使用哈希时,一般都是用哈希桶来解决冲突(C++STL的hash_map用的就是拉链法)

    手写拉链法的哈希表【C++】

    C++11新特性:STL中的无序关联容器unordered_map的底层实现和用法

    展开全文
  • //判断此时是否需要增容 //当装填因子大于0.7时增容 if (_size * 10 / _table.size() >= 7) { //增容的大小按照别人算好的近似两倍的素数来增,这样效率更高,也可以直接2倍或者1.5倍。 std::vector...
  • 哈希函数的构造方法有:直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法; 处理冲突的方法: 开放地址法(线性探测、二次探测、伪随机探测)、链地址法、多重散列法 开放定址法解决冲突的做法...
  • 哈希函数,是用来计算存储数据的哈希值的,根据存储数据的类型,可以设计不同的哈希函数。一个好的哈希函数(让哈希表效率高的函数),一般都具备下面两个特点: 速度快(别计算一个哈希值计算了半天,导致效率很低...
  • 哈希函数+解决冲突的方法 构造方法 直接定址法,除留余数法 解决冲突的方法 开放定址法:线性探测法,平方探测法 拉链法 1、散列表的若干术语 散列方法(杂凑法) 选取某个函数,依该函数按关键字计算元素的存储位置...
  • HashMap装填因子为啥默认0.75?

    千次阅读 2020-06-10 20:50:17
    在Java中,散列表用链表数组实现.每个列表被称为桶.(见...例如,如果装填因子为0.75(默认值),而表中超过75%的位置已经填入元素,这个表就会用双倍的桶数自动地进行再散列.对于大多数程序来说,装填因子为0.75是比较合理的.
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。在介绍一些集合...
  • 哈希表详细总结

    千次阅读 2018-07-04 16:30:21
    一、哈希表 1、概念 &nbsp;&nbsp;&nbsp;&nbsp;...哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的...这个映射函数就做散列函...
  • 数据结构 - 哈希函数

    千次阅读 2015-05-03 09:55:21
    哈希查找之前的查找算法,时间复杂度为O(n),或者O(㏒2n),其效率取决于“比较”的次数。 即使对于采取排序树结构的查找表,由于每一次比较的结果,如果关键字与数据元素不相等,则有“大于”或者“小于”两个结果,...
  • 哈希函数 哈希函数是从关键字集合到地址集合的映射。这一映射过程称为哈希造表或散列,所得存储位置为哈希地址或散列地址。 哈希函数的构造方法 1.1直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即...
  • 哈希函数 如何生成key的哈希值 Long和Double的哈希值 字符串的哈希值 关于31的探讨 自定义对象的哈希值 自定义对象作为key 哈希值的进一步处理:扰动计算 装填因子 TreeMap vs HashMap LinkedHashMap 关于使用%来计算...
  • 几种常见的哈希函数(散列函数)构造方法 直接定址法 取关键字或关键字的某个线性函数值为散列地址。 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。 比如 除留余数法 取关键字被某个不大于散...
  • 哈希

    2017-07-26 00:00:41
    哈希表概念哈希表(Hash Table)也叫散...散列存储的基本思路以数据中每个元素的关键字K为自变量,通过散列函数H(k)计算出哈希值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。
  • 重温数据结构:哈希 哈希函数 哈希表

    万次阅读 多人点赞 2016-10-27 00:49:30
    在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。 什么是 HashHash(哈希),又称“散列”。散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。在某种程度上,散列是与排序相反的一种操作,...
  • 设散列函数得到的散列地址域在区间**[0,M-1]** ,关键字记录总数为N,则把链地址表中每个链表的平均长度定义为装填因子α,即α=N/M。 NOTICE!!:先要知道散列地址的范围,才能使用链地址法。 [参考]:《数据结构...
  • 哈希函数(Hash Function)

    千次阅读 2019-07-23 12:23:36
    哈希函数(散列函数)说明应用解释Q:冲突是不是可以避免的?hash函数的构造准则:简单、均匀hash函数的构造方法:处理冲突的方法:参考 说明 散列的概念属于查找,它不以关键字的比较为基本操作,采用直接寻址技术...
  • 哈希方法 选取某个函数,依该函数按关键字计算元素的存储位置,并按此...通常关键字的集合比哈希地址集合大得多,所以经过哈希函数变换后,可能将不同的关键字映射到同一个哈希地址上,这种现象称为冲突。 映射到同一
  • Java笔试题常见知识点:哈希函数和哈希冲突哈希函数的构造方法有哪些?产生哈希冲突的影响因素有哪些:处理冲突的方法1.开放定址法(1)线性探测再散列(2)二次探测再散列2.再哈希法3.链地址法4.建立一个公共溢出区...
  • 哈希哈希表定义 哈希表(Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。 哈希表(散列表)的基本概念 基本思想: 记录的...
  • 哈希函数:记录的存储位置和它的关键字之间建立一个确定的对应关系。 冲突:对不同的关键字可能得到同一哈希地址,这种现象称为冲突。 哈希函数构造方法 1.直接定址法 取关键字或关键字的某个线性函数值为哈希...
  • 在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。 在介绍一些...
  • 散列函数(哈希函数,Hash Function)

    万次阅读 2018-05-18 17:52:59
    简单的说,hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。(下图来源于维基百科)散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定...
  • 系统学习hash算法(哈希算法)

    千次阅读 2016-12-06 21:28:39
    系统学习hash算法(哈希算法) 转载请说明出处。 前言: 关于本文《系统学习hash算法》的由来。在看到了《十一、从头到尾彻底解析Hash 表算法》这篇文章之后,原文中没有暴雪hash快的原因分析以及和别的hash...
  • 哈希表是key-value类型的数据结构, 可以理解为一个键值需要按照一定规则存放的数组, 而哈希函数就是这个规则 字典本质上是一个散列表(总有空白元素的数组, python至少保证1/3的数组是空的), 字典中的每个键都占用一...
  • 面试高频-哈希

    2020-04-11 22:06:34
    关于哈希表的知识点也是经常在面试中被问到,通过这几天对于哈希表的学习,包括看了哈希表的源码,以及手动编写了一个简单的哈希表,加深了对哈希表的理解,并在此进行总结! 1. 什么是哈希表 Hash表也称散列表,也...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,885
精华内容 1,554
热门标签
关键字:

哈希函数装填因子