数据结构：散列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;
		}
	};

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠