數(shù)據(jù)結(jié)構(gòu)：散列1（分離鏈接法）

散列：

將每一個(gè)鍵映照到從0到TableSize⑴這個(gè)范圍的某個(gè)數(shù)，并將其放到適當(dāng)?shù)膯卧小＿@個(gè)映照成為散列函數(shù)

理想情況下，不同的鍵映照到不同的單元，但是現(xiàn)實(shí)中是不可能的，所以好的散列函數(shù)，應(yīng)當(dāng)盡可能均勻地分配鍵。

列表的大小最好是素?cái)?shù)，這個(gè)非常非常重要。

解決沖突：

沖突：如果1個(gè)元素插入時(shí)與1個(gè)已插入的元素散列到相同的值，那末就產(chǎn)生了1個(gè)沖突。

解決沖突的方法：分離鏈接法和探測(cè)法

分離鏈接法：將散列到的同1個(gè)值的所有元素保存到1個(gè)鏈表中。肯定是要分配內(nèi)存。

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

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

先看看1些公用的函數(shù)：

//通過迭代器查找相同的對(duì)象
	template<class InputIterator, class T>
	InputIterator find(InputIterator first, InputIterator last, const T& val)
	{
		while (first != last)
		{
			if (*first == val) return first;
			++first;
		}
		return last;
	}
	//是不是1個(gè)素?cái)?shù)
	bool isPrime(int num)
	{
		if (num == 2 || num == 3)
		{
			return true;
		}
		if (num % 6 != 1 && num % 6 != 5)
		{
			return false;
		}
		for (int i = 5; i*i <= num; i += 6)
		{
			if (num % i == 0 || num % (i + 2) == 0)
			{
				return false;
			}
		}
		return true;
	}
	//查找比x大的第1個(gè)素?cái)?shù)
	int nextPrime(int n)
	{
		bool state = isPrime(n);
		while (!state)
		{
			state = isPrime(++n);

		}
		return n;
	}
	//string的散列函數(shù)	
	int hash(const std::string& key)
	{
		int hashVal = 0;
		for (size_t i = 0; i < key.length(); i++)
		{
			hashVal = 37 * hashVal + key[i];
		}
		return hashVal;
	}
	//int的散列函數(shù)
	int hash(int key)
	{
		return key;
	}

	//分離鏈接法
	template <typename HashedObj>
	class HashTable
	{
	public:
		//構(gòu)造函數(shù)
		explicit HashTable(int size = 101) :theList(size){}
		//包括某個(gè)對(duì)象
		bool contains(const HashedObj& x)const
		{
			const List<HashedObj>& whichList = theList[myhash(x)];
			return find(whichList.begin(), whichList.end(), x) != whichList.end();
		}
		//清空散列表
		void makeEmpty()
		{
			for (int i = 0; i < theList.size(); i++)
			{
				theList[i].clear();//對(duì)每一個(gè)散列表清空
			}
		}
		//插入數(shù)據(jù)
		bool insert(const HashedObj& x)
		{
			//找到散列表中對(duì)應(yīng)位置的鏈表
 			List<HashedObj>& whichList = theList[myhash(x)];
			//在鏈表中找到x
 			List<HashedObj>::iterator iter = find(whichList.begin(), whichList.end(), x);
			if (iter != whichList.end())
			{
				return false;
			}
 			whichList.push_back(x);
			++currentSize;
			//數(shù)據(jù)的大小超過了散列表的大小，因而可知，理想情況下，散列表下的鏈表應(yīng)當(dāng)是只放1個(gè)數(shù)據(jù)是最好的
			if (currentSize > theList.size())
			{
				rehash();//重構(gòu)1個(gè)更加大的散列表
			}
			return true;
		}
		//刪除數(shù)據(jù)
		void remove(const HashedObj& x)
		{
			//找到鏈表
			List<HashedObj>& whichList = theList[myhash(x)];
			List<HashedObj>::iterator iter = find(whichList.begin(), whichList.end(), x);
			if (iter == whichList.end())
			{
				return false;
			}
			//刪除
			whichList.erase(iter);
			--currentSize;
			return true;
		}
	private:
		Vector<List<HashedObj>> theList;//散列表
		int currentSize;//當(dāng)前數(shù)據(jù)量
		//重新構(gòu)造1個(gè)散列表
		void rehash()
		{
			//原來的散列表
 			Vector<List<HashedObj>> oldList = theList;
			//散列表的大小擴(kuò)大兩倍，然后再找接下來的第1個(gè)素?cái)?shù)
			theList.resize(nextPrime(2 * theList.size()));
			//清空散列表
			for (int i = 0; i < theList.size(); i++)
			{
				theList[i].clear();
			}
			//插入舊的數(shù)據(jù)
			currentSize = 0;
			for (int i = 0; i < oldList.size(); i++)
			{
				List<HashedObj>::iterator iter = oldList[i].begin();
				while (iter != oldList[i].end())
				{
					insert(*iter);
					iter++;
				}
			}
		}
		//計(jì)算散列數(shù)
		int myhash(const HashedObj& x)const
		{
			int hashVal = hash(x);
			hashVal %= theList.size();
			if (hashVal < 0)
			{
				hashVal += theList.size();
			}
			return hashVal;
		}
	};

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