• . 哈希表的基本思想
• 2. 哈希表的相關(guān)基本概念
• 3. 哈希表的實(shí)現(xiàn)方法
• 4. 哈希表“定址”的方法
• 5. 哈希表“解決沖突”的方法
• 6. 哈希表“定址”和“解決沖突”之間的權(quán)衡
• 7. 哈希表實(shí)例

哈希表（Hash Table）是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它最大的特點(diǎn)就是可以快速實(shí)現(xiàn)查找、插入和刪除。因?yàn)樗?dú)有的特點(diǎn)，Hash表經(jīng)常被用來解決大數(shù)據(jù)問題，也因此被廣大的程序員所青睞。為了能夠更加靈活地使用Hash來提高我們的代碼效率，今天，我們就談一談Hash的那點(diǎn)事。

1. 哈希表的基本思想

我們知道，數(shù)組的最大特點(diǎn)就是：尋址容易，插入和刪除困難；而鏈表正好相反，尋址困難，而插入和刪除操作容易。那么如果能夠結(jié)合兩者的優(yōu)點(diǎn)，做出一種尋址、插入和刪除操作同樣快速容易的數(shù)據(jù)結(jié)構(gòu)，那該有多好。這就是哈希表創(chuàng)建的基本思想，而實(shí)際上哈希表也實(shí)現(xiàn)了這樣的一個(gè)“夙愿”，哈希表就是這樣一個(gè)集查找、插入和刪除操作于一身的數(shù)據(jù)結(jié)構(gòu)。

回到頂部

2. 哈希表的相關(guān)基本概念

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

哈希表（Hash Table）：也叫散列表，是根據(jù)關(guān)鍵碼值（Key-Value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，也就是我們常用到的map。

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

哈希表和哈希函數(shù)的標(biāo)準(zhǔn)定義：

• 若關(guān)鍵字為k，則其值存放在f(k)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)，按這個(gè)思想建立的表為哈希表。

設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡稱全集)。實(shí)際發(fā)生(即實(shí)際存儲(chǔ))的關(guān)鍵字集合記為K（|K|比|U|小得多）。

散列方法是使用函數(shù)h將U映射到表T[0..m-1]的下標(biāo)上（m=O(|U|)）。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。

其中：

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

② T為哈希表(Hash Table)。

③ h(Ki)(Ki∈U)是關(guān)鍵字為Ki結(jié)點(diǎn)存儲(chǔ)地址(亦稱散列值或散列地址)。

④ 將結(jié)點(diǎn)按其關(guān)鍵字的哈希地址存儲(chǔ)到哈希表中的過程稱為散列(Hashing)

1）沖突：

兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞(Synonym)。

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

最理想的解決沖突的方法是安全避免沖突。要做到這一點(diǎn)必須滿足兩個(gè)條件：

①其一是|U|≤m

②其二是選擇合適的散列函數(shù)。

這只適用于|U|較小，且關(guān)鍵字均事先已知的情況，此時(shí)經(jīng)過精心設(shè)計(jì)散列函數(shù)h有可能完全避免沖突。

3）沖突不可能完全避免

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

4）影響沖突的因素

沖突的頻繁程度除了與h相關(guān)外，還與表的填滿程度相關(guān)。

設(shè)m和n分別表示表長和表中填入的結(jié)點(diǎn)數(shù)，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿，沖突的機(jī)會(huì)也越大。通常取α≤1。

回到頂部

3. 哈希表的實(shí)現(xiàn)方法

我們之前說了，哈希表是一個(gè)集查找、插入和刪除操作于一身的數(shù)據(jù)結(jié)構(gòu)。那這么完美的數(shù)據(jù)結(jié)構(gòu)到底是怎么實(shí)現(xiàn)的呢？哈希表有很多種不同的實(shí)現(xiàn)方法，為了實(shí)現(xiàn)哈希表的創(chuàng)建，這些所有的方法都離不開兩個(gè)問題——“定址”和“解決沖突”。

在這里，我們通過詳細(xì)地介紹哈希表最常用的方法——取余法（定值）+拉鏈法（解決沖突），來一起窺探一下哈希表強(qiáng)大的優(yōu)點(diǎn)。

取余法大家一定不會(huì)感覺陌生，就是我們經(jīng)常說的取余數(shù)的操作。

拉鏈法是什么，“拉鏈”說白了就是“鏈表數(shù)組”。我這么一解釋，大家更暈了，啥是“鏈表數(shù)組”啊？為了更好地解釋“鏈表數(shù)組”，我們用下圖進(jìn)行解釋：圖中的主干部分是一個(gè)順序存儲(chǔ)結(jié)構(gòu)數(shù)組，但是有的數(shù)組元素為空，有的對(duì)應(yīng)一個(gè)值，有的對(duì)應(yīng)的是一個(gè)鏈表，這就是“鏈表數(shù)組”。比如數(shù)組0的位置對(duì)應(yīng)一個(gè)鏈表，鏈表有兩個(gè)元素“496”和“896”，這說明元素“496”和“896”有著同樣的Hash地址，這就是我們上邊介紹的“沖突”或者“碰撞”。但是“鏈表數(shù)組”的存儲(chǔ)方式很好地解決了Hash表中的沖突問題，發(fā)生沖突的元素會(huì)被存在一個(gè)對(duì)應(yīng)Hash地址指向的鏈表中。實(shí)際上，“鏈表數(shù)組”就是一個(gè)指針數(shù)組，每一個(gè)指針指向一個(gè)鏈表的頭結(jié)點(diǎn)，鏈表可能為空，也可能不為空。

說完這些，大家肯定已經(jīng)理解了“鏈表數(shù)組”的概念，那我們就一起看看Hash表是如何根據(jù)“取余法+拉鏈法”構(gòu)建的吧。

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

舉例說明拉鏈法的執(zhí)行過程，設(shè)有一組關(guān)鍵字為(26，36，41，38，44，15，68，12，6，51)，用取余法構(gòu)造散列函數(shù)，初始情況如下圖所示：

最終結(jié)果如下圖所示：

理解了Hash表的創(chuàng)建，那根據(jù)建立的Hash表進(jìn)行查找就很容易被理解了。

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

1）x所屬的Hash地址未被占用，即不存在與x相同的Hash地址關(guān)鍵字，當(dāng)然也不存在x了；

2）x所屬的Hash地址被占用了，但它所存的關(guān)鍵不屬于這個(gè)Hash地址，與1）相同，不存在與x相同Hash地址的關(guān)鍵字；

3）x所屬的Hash地址被占用了，且它所存的關(guān)鍵屬于這個(gè)Hash地址，即存在與x相同sHash地址的關(guān)鍵字，只是不知這個(gè)關(guān)鍵字是不是x，需要進(jìn)一步查找。

由此可見，Hash表插入、刪除和插入操作的效率都相當(dāng)?shù)母摺?/p>

思考一個(gè)問題：如果關(guān)鍵字是字符串怎么辦？我們怎么根據(jù)字符串建立Hash表？

通常都是將元素的key轉(zhuǎn)換為數(shù)字進(jìn)行散列，如果key本身就是整數(shù)，那么散列函數(shù)可以采用keymod tablesize（要保證tablesize是質(zhì)數(shù)）。而在實(shí)際工作中經(jīng)常用字符串作為關(guān)鍵字，例如身姓名、職位等等。這個(gè)時(shí)候需要設(shè)計(jì)一個(gè)好的散列函數(shù)進(jìn)程處理關(guān)鍵字為字符串的元素。參考《數(shù)據(jù)結(jié)構(gòu)與算法分析》第5章，有以下幾種處理方法：

方法1：將字符串的所有的字符的ASCII碼值進(jìn)行相加，將所得和作為元素的關(guān)鍵字。設(shè)計(jì)的散列函數(shù)如下所示：

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

此方法的缺點(diǎn)是不能有效的分布元素，例如假設(shè)關(guān)鍵字是有8個(gè)字母構(gòu)成的字符串，散列表的長度為10007。字母最大的ASCII碼為127，按照方法1可得到關(guān)鍵字對(duì)應(yīng)的最大數(shù)值為127×8=1016，也就是說通過散列函數(shù)映射時(shí)只能映射到散列表的槽0-1016之間，這樣導(dǎo)致大部分槽沒有用到，分布不均勻，從而效率低下。

方法2：假設(shè)關(guān)鍵字至少有三個(gè)字母構(gòu)成，散列函數(shù)只是取前三個(gè)字母進(jìn)行散列。設(shè)計(jì)的散列函數(shù)如下所示：

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;
}

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

方法3：借助Horner's 規(guī)則，構(gòu)造一個(gè)質(zhì)數(shù)（通常是37）的多項(xiàng)式，（非常的巧妙，不知道為何是37）。計(jì)算公式為:key[keysize-i-1]*37ⁱ, 0<=i<keysize求和。設(shè)計(jì)的散列函數(shù)如下所示：

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

該方法存在的問題是如果字符串關(guān)鍵字比較長，散列函數(shù)的計(jì)算過程就變長，有可能導(dǎo)致計(jì)算的hashVal溢出。針對(duì)這種情況可以采取字符串的部分字符進(jìn)行計(jì)算，例如計(jì)算偶數(shù)或者奇數(shù)位的字符。

回到頂部

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

其實(shí)常用的“定址”的手法有“五種”：

1）直接定址法

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

2）除法取余法

key=value%C

3）數(shù)字分析法

這種蠻有意思，比如有一組value1=112233，value2=112633，value3=119033，針對(duì)這樣的數(shù)我們分析數(shù)中間兩個(gè)數(shù)比較波動(dòng)，其他數(shù)不變。那么我們?nèi)ey的值就可以是key1=22,key2=26,key3=90。

4）平方取中法

5）折疊法

舉個(gè)例子，比如value=135790，要求key是2位數(shù)的散列值。那么我們將value變?yōu)?3+57+90=160，然后去掉高位“1”,此時(shí)key=60，哈哈，這就是他們的哈希關(guān)系，這樣做的目的就是key與每一位value都相關(guān)，來做到“散列地址”盡可能分散的目地。

影響哈希查找效率的一個(gè)重要因素是哈希函數(shù)本身。當(dāng)兩個(gè)不同的數(shù)據(jù)元素的哈希值相同時(shí)，就會(huì)發(fā)生沖突。為減少發(fā)生沖突的可能性，哈希函數(shù)應(yīng)該將數(shù)據(jù)盡可能分散地映射到哈希表的每一個(gè)表項(xiàng)中。

回到頂部

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

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

1）開放地址法

如果兩個(gè)數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)。當(dāng)程序查找哈希表時(shí)，如果沒有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素，程序就會(huì)繼續(xù)往后查找，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)。

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

散列過程如下圖所示：

2）鏈地址法

將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線性查找方法。

回到頂部

6. 哈希表“定址”和“解決沖突”之間的權(quán)衡

雖然哈希表是在關(guān)鍵字和存儲(chǔ)位置之間建立了對(duì)應(yīng)關(guān)系，但是由于沖突的發(fā)生，哈希表的查找仍然是一個(gè)和關(guān)鍵字比較的過程，不過哈希表平均查找長度比順序查找要小得多，比二分查找也小。

查找過程中需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)取決于下列三個(gè)因素：哈希函數(shù)、處理沖突的方法和哈希表的裝填因子。

哈希函數(shù)的"好壞"首先影響出現(xiàn)沖突的頻繁程度，但如果哈希函數(shù)是均勻的，則一般不考慮它對(duì)平均查找長度的影響。

對(duì)同一組關(guān)鍵字，設(shè)定相同的哈希函數(shù)，但使用不同的沖突處理方法，會(huì)得到不同的哈希表，它們的平均查找長度也不同。

一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子α。顯然，α越小，產(chǎn)生沖突的機(jī)會(huì)就越大；但α過小，空間的浪費(fèi)就過多。通過選擇一個(gè)合適的裝填因子α，可以將平均查找長度限定在一個(gè)范圍內(nèi)。

總而言之，哈希表“定址”和“解決沖突”之間的權(quán)衡決定了哈希表的性能。

回到頂部

7. 哈希表實(shí)例

一個(gè)哈希表實(shí)現(xiàn)的C++實(shí)例，在此設(shè)計(jì)的散列表針對(duì)的是關(guān)鍵字為字符串的元素，采用字符串散列函數(shù)方法3進(jìn)行設(shè)計(jì)散列函數(shù)，采用鏈接方法處理碰撞，然后采用根據(jù)裝載因子（指定為1，同時(shí)將n個(gè)元素映射到一個(gè)鏈表上，即n==m時(shí)候）進(jìn)行再散列。采用C++，借助vector和list，設(shè)計(jì)的hash表框架如下：

template <class T>
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<list<T> > lists;
 int currentSize;//當(dāng)前散列表中元素的個(gè)數(shù)
 int hash(const string& key);
 int myhash(const T& x);
 void rehash();
};

實(shí)現(xiàn)的完整程序如下所示：

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int nextPrime(const int n);
template <class T>
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<list<T> > lists;
 int currentSize;
 int hash(const string& key);
 int myhash(const T& x);
 void rehash();
};
template <class T>
HashTable<T>::HashTable(int size)
{
 lists=vector<list<T> >(size);
 currentSize=0;
}
template <class T>
int HashTable<T>::hash(const string& key)
{
 int hashVal=0;
 int tableSize=lists.size();
 for(int i=0;i<key.length();i++)
 hashVal=37*hashVal+key[i];
 hashVal %=tableSize;
 if(hashVal < 0)
 hashVal +=tableSize;
 return hashVal;
}
template <class T>
int HashTable<T>:: myhash(const T& x)
{
 string key=x.getName();
 return hash(key);
}
template <class T>
int HashTable<T>::insert(const T& x)
{
 list<T> &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 <class T>
int HashTable<T>::remove(const T& x)
{
 typename std::list<T>::iterator iter;
 list<T> &whichlist=lists[myhash(x)];
 iter=find(whichlist.begin(),whichlist.end(),x);
 if( iter !=whichlist.end())
 {
 whichlist.erase(iter);
 currentSize--;
 return 1;
 }
 return 0;
}
template <class T>
int HashTable<T>::contains(const T& x)
{
 list<T> whichlist;
 typename std::list<T>::iterator iter;
 whichlist=lists[myhash(x)];
 iter=find(whichlist.begin(),whichlist.end(),x);
 if( iter !=whichlist.end())
 return 1;
 return 0;
}
template <class T>
void HashTable<T>::make_empty()
{
 for(int i=0;i<lists.size();i++)
 lists[i].clear();
 currentSize=0;
 return 0;
}
template <class T>
void HashTable<T>::rehash()
{
 vector<list<T> > oldLists=lists;
 lists.resize(nextPrime(2*lists.size()));
 for(int i=0;i<lists.size();i++)
 lists[i].clear();
 currentSize=0;
 for(int i=0;i<oldLists.size();i++)
 {
 typename std::list<T>::iterator iter=oldLists[i].begin();
 while(iter !=oldLists[i].end())
 insert(*iter++);
 }
}
template <class T>
void HashTable<T>::display()const
{
 for(int i=0;i<lists.size();i++)
 {
 cout<<i<<": ";
 typename std::list<T>::const_iterator iter=lists[i].begin();
 while(iter !=lists[i].end())
 {
 cout<<*iter<<" ";
 ++iter;
 }
 cout<<endl;
 }
}
int nextPrime(const int n)
{
 int ret,i;
 ret=n;
 while(1)
 {
 int flag=1;
 for(i=2;i<sqrt(ret);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 <<(ostream& out,const Employee& e)
 {
 out<<"("<<e.name<<","<<e.salary<<") ";
 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<Employee> emp_table(13);
 emp_table.insert(e1);
 emp_table.insert(e2);
 emp_table.insert(e3);
 emp_table.insert(e4);
 cout<<"Hash table is: "<<endl;
 emp_table.display();
 if(emp_table.contains(e4)==1)
 cout<<"Tom is exist in hash table"<<endl;
 if(emp_table.remove(e1)==1)
 cout<<"Removing Tom form the hash table successfully"<<endl;
 if(emp_table.contains(e1)==1)
 cout<<"Tom is exist in hash table"<<endl;
 else
 cout<<"Tom is not exist in hash table"<<endl;
 //emp_table.display();
 exit(0);
}

作者：Poll的筆記

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