C++(資料結構與算法):30---散列(哈希)表的介紹（散列函數、散列沖突、散列溢出）

一、散列（哈希）介紹

• 散列使用一個散列函數（也稱為哈希函數）把字典的數對映射到一個散清單（也稱為哈希表）的具體位置
• 散列的存儲與查找：
  • 查找：如果數對p的關鍵字是k，散列函數為f，那麼在理想的情況下，p在散清單中的位置為f(k)，我們首選計算f(k)，然後檢視在散清單的f(k)處是否存在要查找的值
  • 存儲：與查找相同，使用f(k)函數算出鍵值對k在散清單的位置，然後把元素插入到散清單對應的位置
• 複雜度：在理想情況下，初始化一個空字典的時間為O(b)（b為散清單擁有的位置數），查找、插入、删除操作的時間均為Θ(1)

二、桶和起始桶

• 桶：散清單的每一個位置叫一個桶
• 起始桶：對關鍵字為k的數對，f(k)是起始桶
• 桶的數量等于散清單的長度或大小

三、散列函數

• 散列函數是一個将關鍵字k映射到散清單對應位置的函數
• 散列函數根據需求，可以有多種不同的種類

普通的散列函數

• 例如一個班級最多有100個學生，它們的ID号位于951000~952000之間，那麼可以設計一個散列函數f(k)=k-951000把學生ID号映射到散清單的位置0到1000之間，是以可以用數組table[10001]來存儲這些ID号

除法散列函數

• 在多種散列函數中，除法散列函數是最常用的
• 其形式如下：
  • k是關鍵字，D是散清單的長度（即桶的數量），%為求模操作符

• 例如下面D為11，序号從0到10，則24的散列索引為2（24%11=2）、80對應的散列索引為3（80%11=3）、40對應的散列索引為7（40%11=7）、65的散列索引為10（65%11=10）。如下圖所示

四、散列沖突和散列溢出

散列沖突

• 當多個不同的關鍵字所對應的起始桶相同時，就會發生沖突
• 散列沖突之後可以根據政策來進行解決，例如将沖突資料向後存儲或者在同一個桶處存儲多個數對
• 比如一上面那張圖來說，索引3處已經存在關鍵字80了，如果此時58也要加入散清單中，其根據散列函數求得58%11=3，是以跟80産生沖突，這個就叫做散列沖突

散列溢出

• 一個桶之可以存儲多個數對，那麼發生散列沖突也沒事，因為可以将多個資料存儲在一個桶中
• 但是如果散清單中的一個桶數量用完時，沒有多餘的空間來存儲新數對，那麼就稱之為散列溢出
• 散列溢出時有很多的解決辦法，其中最常用的方法是線性探針法（見後面的文章）

五、均勻散列函數、良好散列函數

均勻散列函數

• 因為有散列沖突和散列溢出問題的存在，是以我們要設計一個優良的散列函數，使的散清單中每一個桶可以存儲的關鍵字數量大緻相等且均勻，那麼沖突和溢出就會減少。我們将這樣的函數成為均勻散列函數

例如：

• 非均勻散列函數：假設散列有b個桶，且b>1。散列函數f(k)=0，那麼無論什麼關鍵字都隻能存儲在散清單的0索引處，其他桶都使用不到就造成沖突與浪費了，那麼這個散列函數就不是均勻散列函數
• 均勻散列函數：假設b=11，關鍵字的範圍為[0,98]，散列函數為f(k)=k%b。那麼關鍵字[0,98]會把大約每9個關鍵字映射到一個桶中，這樣一來，每個桶存儲的數字都比較均勻，那麼産生散列沖突的機率就會減少，那麼這個散列函數相對來說就是均勻的散列函數

良好散列函數

• 遺憾的是，我們無法使用某一種固定的方法選擇一個關鍵字來設計均勻散列函數。在應用中，關鍵字都有某種程式的關聯性
• 例如，當關鍵字是整數時，可能是奇數占優或者偶數占優，不會是奇數和偶數均等。當關鍵字是字母數字形式的時候，字首或字尾相同的關鍵字可能會占堆兒
• 在實際應用中，關鍵字不是從關鍵字範圍内均勻選擇的，是以有的均勻散列函數表現好一點，有一些就差一些。在實際應用中性能表現好的均勻散列函數稱為良好散列函數

六、散列函數除數D的選擇

• 除法散列函數的格式如下：

• 原則：對于D的選擇，有些會産生良好散列函數，有些會産生不良散列函數。但是隻要D>1，對D的所有選擇，都會産生均勻散列函數
• D的選擇：
  • 如果D選擇為偶數：
    • 當k是偶數時，f(k)結果為偶數；當k是奇數時，f(k)結果為奇數；
    • 例如如果應用中以偶數關鍵字為主，則大部分關鍵字會被映射到序号為偶數的起始桶中。如果應用中以奇數關鍵字為主，則大部分關鍵字會被映射到序号為奇數的起始桶中
    • 是以使用D為偶數，得到的是不良散列函數
  • 如果D可以被諸如3、5、7這樣的小奇數整除時，不會産生良好散列函數
  • 是以，選擇的除數D應該既不是偶數也不能被小的奇數整除
  • 理想的D是一個素數/質數（素數與質數是一個概念）。如果你找到一個接近散清單長度的素數時，你應該選擇不能被2和19之間的整數整除的D。D的其它考量在後面還有介紹
• 總結：當使用除法散列函數時，選擇除數D為奇數，可以是散列值依賴關鍵字的所有位。當D即是素數又不能被小于20的整數除，就能得到良好散列函數
• 除數D的選擇也可以參考文章：javascript:void(0)

七、非整型關鍵字

• 如果用哈希存儲字典，如果字典的關鍵字不是一個整型，那麼就需要将字典的關鍵字轉換為整型，然後插入到對應的桶中

程式①

• 下面建立一個函數，用來将一個長度為3的字元串轉換為一個長整型

long threeToLong(std::string s)
{
	//最左邊的字元
	long answer = s.at(0);

	//左移8位，加入下一個字元
	answer = (answer << 8) + s.at(1);

	//左移8位，加入下一個字元
	return ((answer << 8) + s.at(2));
}           

• 當輸入s為abc時，s.at(0)=a、s.at(1)=b、s.at(2)=c，它們的值分别為97、98、99
• 3個字元構成的串不同，轉換的長整型數也不同，是以此函數可以把一個長度為3的字元串轉換為唯一的長整型數（長整型數的範圍為[0,

  

  -1]）
• 因為一個左移8位的操作符等價于乘以

  

  ，是以輸出abc會輸出((97*256+98)*256)+99=6382179

程式②

long threeToInt(std::string s)
{
	int length = (int)s.length(); //s中的字元個數
	int answer = 0;

	//如果字元串長度為奇數
	if (length % 2 == 1) {
		answer = s.at(length - 1);
		length--;
	}

	//長度為偶數
	for (int i = 0; i < length; i += 2) {
		//同時轉換兩個字元
		answer += s.at(i);
		answer += ((int)s.at(i + 1)) << 8;
	}

	return (answer < 0) ? -answer : answer;
}           

• 上面的程式①隻可以把長度為3個字元的字元串轉換為一個唯一的整數，但是這樣方法比較有局限性
• 在實際應用中，散列函數可以把若幹個關鍵字散列到相同的起始桶處，是以我們不必要把每個字元串轉換為唯一的一個整數，此處我們的函數采用一個算法，用來把一個任意長的字元串轉換為一個整數，不同字元串轉換之後可能得到的值會相同
• 函數的思想：我們取輸入的字元串的每個字元，并把每個字元轉換為整數，然後将這些整數相加（相加的時候可以自己設計一算算法，例如上面每兩個字元進行一次<<8的操作）
• 例如下面是兩個示範案例

hash函數

template<class K> class hash;

template<>
class hash<std::string>
{
public:
	std::size_t operator()(const std::string theKey)const
	{
		unsigned long hashValue = 0;
		int length = (int)theKey.length();
		for (int i = 0; i < length; i++) {
			hashValue = hashValue * 5 + theKey.at(i);
		}

		return std::size_t(hashValue);
	}
};           

• 我們定義了一個模闆類，這個類用來将一個字元串轉換為一個size_t類型的非負整數
• 當然，我們也可以把一個int或long類型的整數轉換為size_t類型的非負整數

template<>
class hash<int>
{
public:
	std::size_t operator()(const int theKey) const
	{
		return std::size_t(theKey);
	}
};

template<>
class hash<long>
{
public:
	std::size_t operator()(const long theKey) const
	{
		return std::size_t(theKey);
	}
};