一個合格的程序員必會Hash詳解

• 1. 哈希表的基本思想
• 2. 哈希表的相關基本概念
• 3. 哈希表的實現方法
• 4. 哈希表“定址”的方法
• 5. 哈希表“解決衝突”的方法
• 6. 哈希表“定址”和“解決衝突”之間的權衡
• 7. 哈希表實例

哈希表（Hash Table）是一種特殊的數據結構，它最大的特點就是可以快速實現查找、插入和刪除。因為它獨有的特點，Hash表經常被用來解決大數據問題，也因此被廣大的程序員所青睞。為了能夠更加靈活地使用Hash來提高我們的代碼效率，今天，我們就談一談Hash的那點事。

1. 哈希表的基本思想

我們知道，數組的最大特點就是：尋址容易，插入和刪除困難；而鏈表正好相反，尋址困難，而插入和刪除操作容易。那麼如果能夠結合兩者的優點，做出一種尋址、插入和刪除操作同樣快速容易的數據結構，那該有多好。這就是哈希表創建的基本思想，而實際上哈希表也實現了這樣的一個“夙願”，哈希表就是這樣一個集查找、插入和刪除操作於一身的數據結構。

回到頂部

2. 哈希表的相關基本概念

在介紹Hash之前，首先我們要搞明白幾個概念：

哈希表（Hash Table）：也叫散列表，是根據關鍵碼值（Key-Value）而直接進行訪問的數據結構，也就是我們常用到的map。

哈希函數：也稱為是散列函數，是Hash表的映射函數，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值。哈希函數能使對一個數據序列的訪問過程變得更加迅速有效，通過哈希函數數據元素能夠被很快的進行定位。

哈希表和哈希函數的標準定義：

• 若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為哈希函數，按這個思想建立的表為哈希表。

設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K（|K|比|U|小得多）。

散列方法是使用函數h將U映射到表T[0..m-1]的下標上（m=O(|U|)）。這樣以U中關鍵字為自變量，以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。

其中：

① h：U→{0，1，2，…，m-1} ，通常稱h為哈希函數(Hash Function)。哈希函數h的作用是壓縮待處理的下標範圍，使待處理的|U|個值減少到m個值，從而降低空間開銷。

② T為哈希表(Hash Table)。

③ h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。

④ 將結點按其關鍵字的哈希地址存儲到哈希表中的過程稱為散列(Hashing)

1）衝突：

兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為衝突(Collision)或碰撞。發生衝突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。

2）安全避免衝突的條件：

最理想的解決衝突的方法是安全避免衝突。要做到這一點必須滿足兩個條件：

①其一是|U|≤m

②其二是選擇合適的散列函數。

這隻適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函數h有可能完全避免衝突。

3）衝突不可能完全避免

通常情況下，h是一個壓縮映像。雖然|K|≤m，但|U|>m，故無論怎樣設計h，也不可能完全避免衝突。因此，只能在設計h時儘可能使衝突最少。同時還需要確定解決衝突的方法，使發生衝突的同義詞能夠存儲到表中。

4）影響衝突的因素

衝突的頻繁程度除了與h相關外，還與表的填滿程度相關。

設m和n分別表示表長和表中填入的結點數，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿，衝突的機會也越大。通常取α≤1。

回到頂部

3. 哈希表的實現方法

我們之前說了，哈希表是一個集查找、插入和刪除操作於一身的數據結構。那這麼完美的數據結構到底是怎麼實現的呢？哈希表有很多種不同的實現方法，為了實現哈希表的創建，這些所有的方法都離不開兩個問題——“定址”和“解決衝突”。

在這裡，我們通過詳細地介紹哈希表最常用的方法——取餘法（定值）+拉鍊法（解決衝突），來一起窺探一下哈希表強大的優點。

取餘法大家一定不會感覺陌生，就是我們經常說的取餘數的操作。

拉鍊法是什麼，“拉鍊”說白了就是“鏈表數組”。我這麼一解釋，大家更暈了，啥是“鏈表數組”啊？為了更好地解釋“鏈表數組”，我們用下圖進行解釋：圖中的主幹部分是一個順序存儲結構數組，但是有的數組元素為空，有的對應一個值，有的對應的是一個鏈表，這就是“鏈表數組”。比如數組0的位置對應一個鏈表，鏈表有兩個元素“496”和“896”，這說明元素“496”和“896”有著同樣的Hash地址，這就是我們上邊介紹的“衝突”或者“碰撞”。但是“鏈表數組”的存儲方式很好地解決了Hash表中的衝突問題，發生衝突的元素會被存在一個對應Hash地址指向的鏈表中。實際上，“鏈表數組”就是一個指針數組，每一個指針指向一個鏈表的頭結點，鏈表可能為空，也可能不為空。

說完這些，大家肯定已經理解了“鏈表數組”的概念，那我們就一起看看Hash表是如何根據“取餘法+拉鍊法”構建的吧。

將所有關鍵字為同義詞的結點鏈接在同一個鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鍊法中，裝填因子α可以大於1，但一般均取α≤1。

舉例說明拉鍊法的執行過程，設有一組關鍵字為(26，36，41，38，44，15，68，12，6，51)，用取餘法構造散列函數，初始情況如下圖所示：

最終結果如下圖所示：

理解了Hash表的創建，那根據建立的Hash表進行查找就很容易被理解了。

查找操作，如果理解了插入和刪除，查找操作就比較簡單了，令待查找的關鍵字是x，也可分為幾種情況：

1）x所屬的Hash地址未被佔用，即不存在與x相同的Hash地址關鍵字，當然也不存在x了；

2）x所屬的Hash地址被佔用了，但它所存的關鍵不屬於這個Hash地址，與1）相同，不存在與x相同Hash地址的關鍵字；

3）x所屬的Hash地址被佔用了，且它所存的關鍵屬於這個Hash地址，即存在與x相同sHash地址的關鍵字，只是不知這個關鍵字是不是x，需要進一步查找。

由此可見，Hash表插入、刪除和插入操作的效率都相當的高。

思考一個問題：如果關鍵字是字符串怎麼辦？我們怎麼根據字符串建立Hash表？

通常都是將元素的key轉換為數字進行散列，如果key本身就是整數，那麼散列函數可以採用keymod tablesize（要保證tablesize是質數）。而在實際工作中經常用字符串作為關鍵字，例如身姓名、職位等等。這個時候需要設計一個好的散列函數進程處理關鍵字為字符串的元素。參考《數據結構與算法分析》第5章，有以下幾種處理方法：

方法1：將字符串的所有的字符的ASCII碼值進行相加，將所得和作為元素的關鍵字。設計的散列函數如下所示：

int hash(const string& key,int tablesize)
{
 int hashVal = 0;
 for(int i=0;i hashVal += key[i];
 return hashVal % tableSize;
}

此方法的缺點是不能有效的分佈元素，例如假設關鍵字是有8個字母構成的字符串，散列表的長度為10007。字母最大的ASCII碼為127，按照方法1可得到關鍵字對應的最大數值為127×8=1016，也就是說通過散列函數映射時只能映射到散列表的槽0-1016之間，這樣導致大部分槽沒有用到，分佈不均勻，從而效率低下。

方法2：假設關鍵字至少有三個字母構成，散列函數只是取前三個字母進行散列。設計的散列函數如下所示：

int hash(const string& key,int tablesize)
{
 //27 represents the number of letters plus the blank
 return (key[0]+27*key[1]+729*key[2])%tablesize;
}

該方法只是取字符串的前三個字符的ASCII碼進行散列，最大的得到的數值是2851，如果散列的長度為10007，那麼只有28%的空間被用到，大部分空間沒有用到。因此如果散列表太大，就不太適用。

方法3：藉助Horner's 規則，構造一個質數（通常是37）的多項式，（非常的巧妙，不知道為何是37）。計算公式為:key[keysize-i-1]*37ⁱ, 0<=i

int hash(const string & key,int tablesize)
{
 int hashVal = 0;
 for(int i =0;i hashVal = 37*hashVal + key[i];
 hashVal %= tableSize;
 if(hashVal<0) //計算的hashVal溢出
 hashVal += tableSize;
 return hashVal;
}

該方法存在的問題是如果字符串關鍵字比較長，散列函數的計算過程就變長，有可能導致計算的hashVal溢出。針對這種情況可以採取字符串的部分字符進行計算，例如計算偶數或者奇數位的字符。

回到頂部

4. 哈希表“定址”的方法

其實常用的“定址”的手法有“五種”：

1）直接定址法

很容易理解，key=Value+C；這個“C"是常量。Value+C其實就是一個簡單的哈希函數。

2）除法取餘法

key=value%C

3）數字分析法

這種蠻有意思，比如有一組value1=112233，value2=112633，value3=119033，針對這樣的數我們分析數中間兩個數比較波動，其他數不變。那麼我們取key的值就可以是key1=22,key2=26,key3=90。

4）平方取中法

5）摺疊法

舉個例子，比如value=135790，要求key是2位數的散列值。那麼我們將value變為13+57+90=160，然後去掉高位“1”,此時key=60，哈哈，這就是他們的哈希關係，這樣做的目的就是key與每一位value都相關，來做到“散列地址”儘可能分散的目地。

影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的數據元素的哈希值相同時，就會發生衝突。為減少發生衝突的可能性，哈希函數應該將數據儘可能分散地映射到哈希表的每一個表項中。

回到頂部

5. 哈希表“解決衝突”的方法

Hash表解決衝突的方法主要有以下兩種：

1）開放地址法

如果兩個數據元素的哈希值相同，則在哈希表中為後插入的數據元素另外選擇一個表項。當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往後查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。

開放地址法包括線性探測、二次探測以及雙重散列等方法。其中線性探測法示意圖如下：

散列過程如下圖所示：

2）鏈地址法

將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須採用線性查找方法。

回到頂部

6. 哈希表“定址”和“解決衝突”之間的權衡

雖然哈希表是在關鍵字和存儲位置之間建立了對應關係，但是由於衝突的發生，哈希表的查找仍然是一個和關鍵字比較的過程，不過哈希表平均查找長度比順序查找要小得多，比二分查找也小。

查找過程中需和給定值進行比較的關鍵字個數取決於下列三個因素：哈希函數、處理衝突的方法和哈希表的裝填因子。

哈希函數的"好壞"首先影響出現衝突的頻繁程度，但如果哈希函數是均勻的，則一般不考慮它對平均查找長度的影響。

對同一組關鍵字，設定相同的哈希函數，但使用不同的衝突處理方法，會得到不同的哈希表，它們的平均查找長度也不同。

一般情況下，處理衝突方法相同的哈希表，其平均查找長度依賴於哈希表的裝填因子α。顯然，α越小，產生衝突的機會就越大；但α過小，空間的浪費就過多。通過選擇一個合適的裝填因子α，可以將平均查找長度限定在一個範圍內。

總而言之，哈希表“定址”和“解決衝突”之間的權衡決定了哈希表的性能。

回到頂部

7. 哈希表實例

一個哈希表實現的C++實例，在此設計的散列表針對的是關鍵字為字符串的元素，採用字符串散列函數方法3進行設計散列函數，採用鏈接方法處理碰撞，然後採用根據裝載因子（指定為1，同時將n個元素映射到一個鏈表上，即n==m時候）進行再散列。採用C++，藉助vector和list，設計的hash表框架如下：

template 
class HashTable
{
public:
 HashTable(int size = 101);
 int insert(const T& x);
 int remove(const T& x);
 int contains(const T& x);
 void make_empty();
 void display()const;
private:
 vector > lists;
 int currentSize;//當前散列表中元素的個數
 int hash(const string& key);
 int myhash(const T& x);
 void rehash();
};

實現的完整程序如下所示：

#include  

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int nextPrime(const int n);
template 
class HashTable
{
public:
 HashTable(int size = 101);
 int insert(const T& x);
 int remove(const T& x);
 int contains(const T& x);
 void make_empty();
 void display()const;
private:
 vector > lists;
 int currentSize;
 int hash(const string& key);
 int myhash(const T& x);
 void rehash();
};
template 
HashTable::HashTable(int size)
{
 lists = vector >(size);
 currentSize = 0;
}
template 
int HashTable::hash(const string& key)
{
 int hashVal = 0;
 int tableSize = lists.size(); 

 for(int i=0;i hashVal = 37*hashVal+key[i];
 hashVal %= tableSize;
 if(hashVal < 0)
 hashVal += tableSize;
 return hashVal;
}
template 
int HashTable:: myhash(const T& x)
{
 string key = x.getName();
 return hash(key);
}
template 
int HashTable::insert(const T& x)
{
 list &whichlist = lists[myhash(x)];
 if(find(whichlist.begin(),whichlist.end(),x) != whichlist.end())
 return 0;
 whichlist.push_back(x);
 currentSize = currentSize + 1;
 if(currentSize > lists.size())
 rehash();
 return 1;
}
template 
int HashTable::remove(const T& x)
{
 typename std::list::iterator iter;
 list &whichlist = lists[myhash(x)];
 iter = find(whichlist.begin(),whichlist.end(),x);
 if( iter != whichlist.end())
 {
 whichlist.erase(iter);
 currentSize--;
 return 1;
 }
 return 0;
}
template  

int HashTable::contains(const T& x)
{
 list whichlist;
 typename std::list::iterator iter;
 whichlist = lists[myhash(x)];
 iter = find(whichlist.begin(),whichlist.end(),x);
 if( iter != whichlist.end())
 return 1;
 return 0;
}
template 
void HashTable::make_empty()
{
 for(int i=0;i lists[i].clear();
 currentSize = 0;
 return 0;
}
template 
void HashTable::rehash()
{
 vector > oldLists = lists;
 lists.resize(nextPrime(2*lists.size()));
 for(int i=0;i lists[i].clear();
 currentSize = 0;
 for(int i=0;i {
 typename std::list::iterator iter = oldLists[i].begin();
 while(iter != oldLists[i].end())
 insert(*iter++);
 }
}
template 
void HashTable::display()const
{
 for(int i=0;i {
 cout< 
 typename std::list::const_iterator iter = lists[i].begin();
 while(iter != lists[i].end())
 {
 cout< ++iter;
 }
 cout< }
}
int nextPrime(const int n)
{
 int ret,i;
 ret = n;
 while(1)
 {
 int flag = 1;
 for(i=2;i if(ret % i == 0)
 {
 flag = 0;
 break;
 }
 if(flag == 1)
 break;
 else
 {
 ret = ret +1;
 continue;
 }
 }
 return ret;
}
class Employee
{
public:
 Employee(){}
 Employee(const string n,int s=0):name(n),salary(s){ }
 const string & getName()const { return name; }
 bool operator == (const Employee &rhs) const
 {
 return getName() == rhs.getName();
 }
 bool operator != (const Employee &rhs) const
 {
 return !(*this == rhs);
 }
 friend ostream& operator < {
 out< return out;
 }
private: 

 string name;
 int salary;
};
int main()
{
 Employee e1("Tom",6000);
 Employee e2("Anker",7000);
 Employee e3("Jermey",8000);
 Employee e4("Lucy",7500);
 HashTable emp_table(13);
 emp_table.insert(e1);
 emp_table.insert(e2);
 emp_table.insert(e3);
 emp_table.insert(e4);
 cout< emp_table.display();
 if(emp_table.contains(e4) == 1)
 cout< if(emp_table.remove(e1) == 1)
 cout< if(emp_table.contains(e1) == 1)
 cout< else
 cout< //emp_table.display();
 exit(0);
}
 

原文：http://www.cnblogs.com/maybe2030/p/4719267.html

閱讀更多 全民學編程 的文章

關鍵字: 技術 定址 數據結構