數據結構：散列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;
		}
	};

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈