数据结构:散列2(探测法)

上1章的内容:散列1:分离链接法

对List和Vector,都是使用自己实现的简单模板。Vector模板的实现 List模板的实现

散列表的填装因子(load factor)λ为散列表中的元素个数和散列表大小的比值。

探测散列表:在找到位置后,发现已有数据,继续找下1个,直到找到位置。这类表叫做探测散列表。


再散列:当散列表中数据很多的时候,插入可能会失败,这个时候就扩大为原来大于2倍的新散列表,1般是找下1个素数。然后把旧表的数据放到新表中。

当表达式到达某1个填装因子时进行再散列。

再散列是1种非常耗时间的操作,但是由于不是常常产生,所以效果还好。

	//使用探测法(probing hash tables)
	template<typename HashedObj>
	class HashTable2
	{
	public:
		//构造函数
		explicit HashTable2(int size = 101) :array(nextPrime(size))
		{
			makeEmpty();//设定结点的状态
		}
		//是不是包括某个实体
		bool contains(const HashedObj& x)const
		{
			return isActive(findPos(x));//找到位置,这个位置是不是被使用的
		}
		//清空散列表
		void makeEmpty()
		{
			currentSize = 0;
			for (int i = 0; i < array.size(); i++)
			{
				array[i].info = EMPTY;
			}
		}
		//插入数据
		bool insert(const HashedObj& x)
		{
			int currentPos = findPos(x);//找到位置
			if (isActive(currentPos))//已有了就不插入了
			{
				return false;
			}
			//构建新的实体
			array[currentPos] = HashEntry(x, ACTIVE);
			++currentSize;
			if (currentSize > array.size()/2)
			{
				rehash();//超过1半就重构
			}
			return true;
		}
		//删除实体
		void remove(const HashedObj& x)
		{
			//找到位置
			int currentPos = findPos(x);
			if (!isActive(currentPos))
			{
				return false;//没有在使用的
			}
			array[currentPos].info = DELETED;//删除掉
			return true;
		}
		enum EntryType{ ACTIVE, EMPTY, DELETED };
	private:
		struct HashEntry 
		{
			HashedObj element;
			EntryType info;
			HashEntry(const HashedObj& e = HashedObj(), EntryType i = EMPTY)
				:element(e), info(i){}
		};
		Vector<HashEntry> array;
		int currentSize;
		//当前位置的状态
		bool isActive(int currentPos)const
		{
			return array[currentPos].info == ACTIVE;
		}
		//找实体的位置,理论上,是不会出现找到最后的位置也被使用掉的情况,由于超过1半了就要重构了
		int findPos(const HashedObj& x)const
		{
			int offset = 1;
			int currentPos = myhash(x);//散列函数
			//如果位置为空或找到了相等的,就中断
			while (array[currentPos].info != EMPTY && array[currentPos].element != x)
			{
				currentPos += offset;
				offset += 2;
				if (currentPos >= array.size())
				{
					currentPos -= array.size();
				}
			}
			return currentPos;
		}
		//重构1个散列表
		void rehash()
		{
			Vector<HashEntry> oldArray = array;//原来的散列表
			//扩大数组大小,原来的两倍以后的第1个素数
			array.resize(nextPrime(2 * oldArray.size()));
			for (int i = 0; i < array.size(); i++)
			{
				array[i].info = EMPTY;//将信息置为空
			}
			currentSize = 0;
			//插入原来的数据
			for (int i = 0; i < oldArray.size(); i++)
			{
				if (oldArray[i].info == ACTIVE)
				{
					insert(oldArray[i].element);
				}
			}
		}
		//散列函数
		int myhash(const HashedObj& x)const
		{
			int hashVal = hash(x);
			hashVal %= array.size();
			if (hashVal < 0)
			{
				hashVal += array.size();
			}
			return hashVal;
		}
	};
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 数据结构:散列2(探测法)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡