數(shù)據(jù)結(jié)構(gòu)：散列2（探測(cè)法）

上1章的內(nèi)容：散列1：分離鏈接法

對(duì)List和Vector，都是使用自己實(shí)現(xiàn)的簡(jiǎn)單模板。Vector模板的實(shí)現(xiàn) List模板的實(shí)現(xiàn)

散列表的填裝因子（load factor）λ為散列表中的元素個(gè)數(shù)和散列表大小的比值。

探測(cè)散列表：在找到位置后，發(fā)現(xiàn)已有數(shù)據(jù)，繼續(xù)找下1個(gè)，直到找到位置。這類表叫做探測(cè)散列表。

再散列：當(dāng)散列表中數(shù)據(jù)很多的時(shí)候，插入可能會(huì)失敗，這個(gè)時(shí)候就擴(kuò)大為原來(lái)大于2倍的新散列表，1般是找下1個(gè)素?cái)?shù)。然后把舊表的數(shù)據(jù)放到新表中。

當(dāng)表達(dá)式到達(dá)某1個(gè)填裝因子時(shí)進(jìn)行再散列。

再散列是1種非常耗時(shí)間的操作，但是由于不是常常產(chǎn)生，所以效果還好。

	//使用探測(cè)法（probing hash tables）
	template<typename HashedObj>
	class HashTable2
	{
	public:
		//構(gòu)造函數(shù)
		explicit HashTable2(int size = 101) :array(nextPrime(size))
		{
			makeEmpty();//設(shè)定結(jié)點(diǎn)的狀態(tài)
		}
		//是不是包括某個(gè)實(shí)體
		bool contains(const HashedObj& x)const
		{
			return isActive(findPos(x));//找到位置，這個(gè)位置是不是被使用的
		}
		//清空散列表
		void makeEmpty()
		{
			currentSize = 0;
			for (int i = 0; i < array.size(); i++)
			{
				array[i].info = EMPTY;
			}
		}
		//插入數(shù)據(jù)
		bool insert(const HashedObj& x)
		{
			int currentPos = findPos(x);//找到位置
			if (isActive(currentPos))//已有了就不插入了
			{
				return false;
			}
			//構(gòu)建新的實(shí)體
			array[currentPos] = HashEntry(x, ACTIVE);
			++currentSize;
			if (currentSize > array.size()/2)
			{
				rehash();//超過(guò)1半就重構(gòu)
			}
			return true;
		}
		//刪除實(shí)體
		void remove(const HashedObj& x)
		{
			//找到位置
			int currentPos = findPos(x);
			if (!isActive(currentPos))
			{
				return false;//沒(méi)有在使用的
			}
			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;
		//當(dāng)前位置的狀態(tài)
		bool isActive(int currentPos)const
		{
			return array[currentPos].info == ACTIVE;
		}
		//找實(shí)體的位置，理論上，是不會(huì)出現(xiàn)找到最后的位置也被使用掉的情況，由于超過(guò)1半了就要重構(gòu)了
		int findPos(const HashedObj& x)const
		{
			int offset = 1;
			int currentPos = myhash(x);//散列函數(shù)
			//如果位置為空或找到了相等的，就中斷
			while (array[currentPos].info != EMPTY && array[currentPos].element != x)
			{
				currentPos += offset;
				offset += 2;
				if (currentPos >= array.size())
				{
					currentPos -= array.size();
				}
			}
			return currentPos;
		}
		//重構(gòu)1個(gè)散列表
		void rehash()
		{
			Vector<HashEntry> oldArray = array;//原來(lái)的散列表
			//擴(kuò)大數(shù)組大小，原來(lái)的兩倍以后的第1個(gè)素?cái)?shù)
			array.resize(nextPrime(2 * oldArray.size()));
			for (int i = 0; i < array.size(); i++)
			{
				array[i].info = EMPTY;//將信息置為空
			}
			currentSize = 0;
			//插入原來(lái)的數(shù)據(jù)
			for (int i = 0; i < oldArray.size(); i++)
			{
				if (oldArray[i].info == ACTIVE)
				{
					insert(oldArray[i].element);
				}
			}
		}
		//散列函數(shù)
		int myhash(const HashedObj& x)const
		{
			int hashVal = hash(x);
			hashVal %= array.size();
			if (hashVal < 0)
			{
				hashVal += array.size();
			}
			return hashVal;
		}
	};

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)