什么是哈希表（Hash Table）

理解Hash
? ? ? ?哈希表(hash table)是從一個(gè)集合A到另一個(gè)集合B的映射(mapping)。
? ? ? ?映射是一種對(duì)應(yīng)關(guān)系，而且集合A的某個(gè)元素只能對(duì)應(yīng)集合B中的一個(gè)元素。但反過(guò)來(lái)，集合B中的一個(gè)元素可能對(duì)應(yīng)多個(gè)集合A中的元素。如果B中的元素只能對(duì)應(yīng)A中的一個(gè)元素，這樣的映射被稱為一一映射。這樣的對(duì)應(yīng)關(guān)系在現(xiàn)實(shí)生活中很常見(jiàn)，比如：

? ? ? ? ? A ?-> B? ? ??

? ? ? ? ? 人 -> 身份證號(hào)

? ? ? ? ? 日期 -> 星座
? ? ? ?上面兩個(gè)映射中，人 -> 身份證號(hào)是一一映射的關(guān)系。在哈希表中，上述對(duì)應(yīng)過(guò)程稱為hashing。A中元素a對(duì)應(yīng)B中元素b，a被稱為鍵值(key)，b被稱為a的hash值(hash value)。
? ? ? ?映射在數(shù)學(xué)上相當(dāng)于一個(gè)函數(shù)f(x):A->B。比如 f(x) = 3x + 2。哈希表的核心是一個(gè)哈希函數(shù)(hash function)，這個(gè)函數(shù)規(guī)定了集合A中的元素如何對(duì)應(yīng)到集合B中的元素。比如：
? ? ? ? ? A: 三位整數(shù) ? ?hash(x) = x % 10 ? ?B: 一位整數(shù)

? ? ? ? ? 104 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4

? ? ? ? ? 876 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6

? ? ? ? ? 192 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2
? ? ? ?上述對(duì)應(yīng)中，哈希函數(shù)表示為hash(x) = x % 10。也就是說(shuō)，給一個(gè)三位數(shù)，我們?nèi)∷淖詈笠晃蛔鳛樵撊粩?shù)的hash值。
? ? ? ?哈希表在計(jì)算機(jī)科學(xué)中應(yīng)用廣泛。比如在git中，文件內(nèi)容為鍵值，并用SHA算法作為hash function，將文件內(nèi)容對(duì)應(yīng)為固定長(zhǎng)度的字符串(hash值)。如果文件內(nèi)容發(fā)生變化，那么所對(duì)應(yīng)的字符串就會(huì)發(fā)生變化。git通過(guò)比較較短的hash值，就可以知道文件內(nèi)容是否發(fā)生變動(dòng)。
? ? ? ?再比如計(jì)算機(jī)的登陸密碼，一般是一串字符。然而，為了安全起見(jiàn)，計(jì)算機(jī)不會(huì)直接保存該字符串，而是保存該字符串的hash值(使用MD5、SHA或者其他算法作為hash函數(shù))。當(dāng)用戶下次登陸的時(shí)候，輸入密碼字符串。如果該密碼字符串的hash值與保存的hash值一致，那么就認(rèn)為用戶輸入了正確的密碼。這樣，就算黑客闖入了數(shù)據(jù)庫(kù)中的密碼記錄，他能看到的也只是密碼的hash值。上面所使用的hash函數(shù)有很好的單向性：很難從hash值去推測(cè)鍵值。因此，黑客無(wú)法獲知用戶的密碼。(之前有報(bào)道多家網(wǎng)站用戶密碼泄露的時(shí)間，就是因?yàn)檫@些網(wǎng)站存儲(chǔ)明文密碼，而不是hash值.)

? ? ? ?注意，hash只要求從A到B的對(duì)應(yīng)為一個(gè)映射，它并沒(méi)有限定該對(duì)應(yīng)關(guān)系為一一映射。因此會(huì)有這樣的可能：兩個(gè)不同的鍵值對(duì)應(yīng)同一個(gè)hash值。這種情況叫做hash碰撞(hash collision)或者h(yuǎn)ash 沖突。比如網(wǎng)絡(luò)協(xié)議中的checksum就可能出現(xiàn)這種狀況，即所要校驗(yàn)的內(nèi)容與原文并不同，但與原文生成的checksum(hash值)相同。再比如，MD5算法常用來(lái)計(jì)算密碼的hash值。已經(jīng)有實(shí)驗(yàn)表明，MD5算法有可能發(fā)生碰撞，也就是不同的明文密碼生成相同的hash值，這將給系統(tǒng)帶來(lái)很大的安全漏洞。(參考hash collision）

Hash函數(shù)
　　Hash表也稱散列表，也有直接譯作哈希表，Hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它同數(shù)組、鏈表以及二叉排序樹(shù)等相比較有很明顯的區(qū)別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來(lái)進(jìn)行查找。這個(gè)源于Hash表設(shè)計(jì)的特殊性，它采用了函數(shù)映射的思想將記錄的存儲(chǔ)位置與記錄的關(guān)鍵字關(guān)聯(lián)起來(lái)，從而能夠很快速地進(jìn)行查找。
1.Hash表的設(shè)計(jì)思想
　　對(duì)于一般的線性表，比如鏈表，如果要存儲(chǔ)聯(lián)系人信息：　
? ? ? ?張三 13980593357
? ? ? ?李四 15828662334
? ? ? ?王五 13409821234
? ? ? ?張帥 13890583472
　　那么可能會(huì)設(shè)計(jì)一個(gè)結(jié)構(gòu)體包含姓名，手機(jī)號(hào)碼這些信息，然后把4個(gè)聯(lián)系人的信息存到一張鏈表中。當(dāng)要查找”李四 15828662334“這條記錄是否在這張鏈表中或者想要得到李四的手機(jī)號(hào)碼時(shí)，可能會(huì)從鏈表的頭結(jié)點(diǎn)開(kāi)始遍歷，依次將每個(gè)結(jié)點(diǎn)中的姓名同”李四“進(jìn)行比較，直到查找成功或者失敗為止，這種做法的時(shí)間復(fù)雜度為O(n)。即使采用二叉排序樹(shù)進(jìn)行存儲(chǔ)，也最多為O(logn)。假設(shè)能夠通過(guò)”李四“這個(gè)信息直接獲取到該記錄在表中的存儲(chǔ)位置，就能省掉中間關(guān)鍵字比較的這個(gè)環(huán)節(jié)，復(fù)雜度直接降到O(1)。Hash表就能夠達(dá)到這樣的效果。
　　Hash表采用一個(gè)映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲(chǔ)位置，從而在想要查找該記錄時(shí)，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲(chǔ)位置，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)，而通過(guò)Hash函數(shù)和關(guān)鍵字計(jì)算出來(lái)的存儲(chǔ)位置(注意這里的存儲(chǔ)位置只是表中的存儲(chǔ)位置，并不是實(shí)際的物理地址)稱作為Hash地址。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲(chǔ)，則當(dāng)想要找到“李四”的信息時(shí)，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可。下面討論一下Hash表設(shè)計(jì)中的幾個(gè)關(guān)鍵問(wèn)題。
2. Hash函數(shù)的設(shè)計(jì)
　　Hash函數(shù)設(shè)計(jì)的好壞直接影響到對(duì)Hash表的操作效率。下面舉例說(shuō)明：
　　假如對(duì)上述的聯(lián)系人信息進(jìn)行存儲(chǔ)時(shí)，采用的Hash函數(shù)為：姓名的每個(gè)字的拼音開(kāi)頭大寫字母的ASCII碼之和。
　　address(張三)=ASCII(Z)+ASCII(S)=90+83=173;
　 ? address(李四)=ASCII(L)+ASCII(S)=76+83=159;
　　address(王五)=ASCII(W)+ASCII(W)=87+87=174;
　　address(張帥)=ASCII(Z)+ASCII(S)=90+83=173;
　　假如只有這4個(gè)聯(lián)系人信息需要進(jìn)行存儲(chǔ)，這個(gè)Hash函數(shù)設(shè)計(jì)的很糟糕。首先，它浪費(fèi)了大量的存儲(chǔ)空間，空間利用率只有4/174，不到5%；另外，根據(jù)Hash函數(shù)計(jì)算結(jié)果之后，address(張三)和address(張帥)具有相同的地址，這種現(xiàn)象稱作沖突，對(duì)于174個(gè)存儲(chǔ)空間中只需要存儲(chǔ)4條記錄就發(fā)生了沖突，這樣的Hash函數(shù)設(shè)計(jì)是很不合理的。所以在構(gòu)造Hash函數(shù)時(shí)應(yīng)盡量考慮關(guān)鍵字的分布特點(diǎn)來(lái)設(shè)計(jì)函數(shù)使得Hash地址隨機(jī)均勻地分布在整個(gè)地址空間當(dāng)中。通常有以下幾種構(gòu)造Hash函數(shù)的方法：
　　1)直接定址法
　　取關(guān)鍵字或者關(guān)鍵字的某個(gè)線性函數(shù)為Hash地址，即address(key)=a*key+b;如知道學(xué)生的學(xué)號(hào)從2000開(kāi)始，最大為4000，則可以將address(key)=key-2000作為Hash地址。
　　2)平方取中法
　　對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算，然后取結(jié)果的中間幾位作為Hash地址。假如有以下關(guān)鍵字序列{421，423，436}，平方之后的結(jié)果為{177241，178929，190096}，那么可以取{72，89，00}作為Hash地址。
　　3)折疊法
　　將關(guān)鍵字拆分成幾部分，然后將這幾部分組合在一起，以特定的方式進(jìn)行轉(zhuǎn)化形成Hash地址。假如知道圖書的ISBN號(hào)為8903-241-23，可以將address(key)=89+03+24+12+3作為Hash地址。
　　4)除留取余法
　　如果知道Hash表的最大長(zhǎng)度為m，可以取不大于m的最大質(zhì)數(shù)p，然后對(duì)關(guān)鍵字進(jìn)行取余運(yùn)算，address(key)=key%p。
　　在這里p的選取非常關(guān)鍵，p選擇的好的話，能夠最大程度地減少?zèng)_突，p一般取不大于m的最大質(zhì)數(shù)。
? ? ? ?典型的除留取余法Hash函數(shù)是time33算法。PHP的數(shù)組就是把這個(gè)作為哈希函數(shù)。time33算法的核心如下：

uint?HashTable::hash(const?char*?key)
{
????uint?hash=0;
????for?(;?*key;?++key)
????{
????????hash=hash*33+*key;
????}
????return?hash%HASHSIZE;
}

? ? ? ? 5)數(shù)字分析法
? ? ? ? 假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。 ? ? ??
? ? ? ? 例如有某些人的生日數(shù)據(jù)如下：
? ? ? ? ? 年. 月. 日
? ? ? ? ? 75.10.03
? ? ? ? ? 85.11.23
? ? ? ? ? 86.03.02
? ? ? ? ? 86.07.12
? ? ? ? ? 85.04.21
? ? ? ? ? 96.02.15
? ? ? ? 經(jīng)分析,第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會(huì)增加，所以盡量不取前三位，取后三位比較好
? ? ? ?6)隨機(jī)數(shù)法
? ? ? ?選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即
? ? ? ?H(key)=random(key) ,其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長(zhǎng)度不等時(shí)采用此法。
3.Hash表大小的確定
　　Hash表大小的確定也非常關(guān)鍵，如果Hash表的空間遠(yuǎn)遠(yuǎn)大于最后實(shí)際存儲(chǔ)的記錄個(gè)數(shù)，則造成了很大的空間浪費(fèi)，如果選取小了的話，則容易造成沖突。在實(shí)際情況中，一般需要根據(jù)最終記錄存儲(chǔ)個(gè)數(shù)和關(guān)鍵字的分布特點(diǎn)來(lái)確定Hash表的大小。還有一種情況時(shí)可能事先不知道最終需要存儲(chǔ)的記錄個(gè)數(shù)，則需要?jiǎng)討B(tài)維護(hù)Hash表的容量，此時(shí)可能需要重新計(jì)算Hash地址。

哈希沖突解決辦法

? ? ? ?如果遇到?jīng)_突，哈希表一般是怎么解決的呢？具體方法有很多，百度也會(huì)有一堆，最常用的就是開(kāi)放定址法和鏈地址法。
1.開(kāi)放定址法
　　如果遇到?jīng)_突的時(shí)候怎么辦呢？就找hash表剩下空余的空間，找到空余的空間然后插入。就像你去商店買東西，發(fā)現(xiàn)東西賣光了，怎么辦呢？找下一家有東西賣的商家買唄。
　　由于我沒(méi)有深入試驗(yàn)過(guò)，所以貼上在書上的解釋：

? ? ? ?
2.鏈地址法
?　 上面所說(shuō)的開(kāi)發(fā)定址法的原理是遇到?jīng)_突的時(shí)候查找順著原來(lái)哈希地址查找下一個(gè)空閑地址然后插入，但是也有一個(gè)問(wèn)題就是如果空間不足，那他無(wú)法處理沖突也無(wú)法插入數(shù)據(jù)，因此需要裝填因子(空間/插入數(shù)據(jù))>=1。
　　那有沒(méi)有一種方法可以解決這種問(wèn)題呢？鏈地址法可以，鏈地址法的原理時(shí)如果遇到?jīng)_突，他就會(huì)在原地址新建一個(gè)空間，然后以鏈表結(jié)點(diǎn)的形式插入到該空間。我感覺(jué)業(yè)界上用的最多的就是鏈地址法。下面從百度上截取來(lái)一張圖片，可以很清晰明了反應(yīng)下面的結(jié)構(gòu)。比如說(shuō)我有一堆數(shù)據(jù){1,12,26,337,353...}，而我的哈希算法是H(key)=key mod 16，第一個(gè)數(shù)據(jù)1的哈希值f(1)=1，插入到1結(jié)點(diǎn)的后面，第二個(gè)數(shù)據(jù)12的哈希值f(12)=12，插入到12結(jié)點(diǎn)，第三個(gè)數(shù)據(jù)26的哈希值f(26)=10，插入到10結(jié)點(diǎn)后面，第4個(gè)數(shù)據(jù)337，計(jì)算得到哈希值是1，遇到?jīng)_突，但是依然只需要找到該1結(jié)點(diǎn)的最后鏈結(jié)點(diǎn)插入即可，同理353。哈希表的拉鏈法實(shí)現(xiàn)如下圖所示：

　　下面解析一下如何用C++實(shí)現(xiàn)鏈地址法。
　　第一步。
　　肯定是構(gòu)建哈希表。
　　首先定義鏈結(jié)點(diǎn)，以結(jié)構(gòu)體Node展示，其中Node有三個(gè)屬性，一個(gè)是key值，一個(gè)value值，還有一個(gè)是作為鏈表的指針。還有作為類的哈希表。

#define?HASHSIZE?10
typedef?unsigned?int?uint;
typedef?struct?Node
{
????const?char*?key;
????const?char*?value;
????Node?*next;
}Node;


class?HashTable
{
private:
????Node*?node[HASHSIZE];
public:
????HashTable();
????uint?hash(const?char*?key);
????Node*?lookup(const?char*?key);
????bool?insert(const?char*?key,const?char*?value);
????const?char*?get(const?char*?key);
????void?display();
};

　　然后定義哈希表的構(gòu)造方法

HashTable::HashTable()
{
????for?(int?i?=?0;?i?<?HASHSIZE;?++i)
????{
????????node[i]?=?NULL;
????}
}

　　第二步。
　　定義哈希表的Hash算法，在這里我使用time33算法。

uint?HashTable::hash(const?char*?key)
{
????uint?hash=0;
????for?(;?*key;?++key)
????{
????????hash=hash*33+*key;
????}
????return?hash%HASHSIZE;
}

　　第三步。
　　定義一個(gè)查找根據(jù)key查找結(jié)點(diǎn)的方法，首先是用Hash函數(shù)計(jì)算頭地址，然后根據(jù)頭地址向下一個(gè)個(gè)去查找結(jié)點(diǎn)，如果結(jié)點(diǎn)的key和查找的key值相同，則匹配成功。

Node*?HashTable::lookup(const?char*?key)
{
????Node?*np;
????uint?index;
????index?=?hash(key);
????for(np=node[index];np;np=np->next){
????????if(!strcmp(key,np->key))
????????????return?np;
????}
????return?NULL;
}

　　定義一個(gè)插入結(jié)點(diǎn)的方法，首先是查看該key值的結(jié)點(diǎn)是否存在，如果存在則更改value值就好，如果不存在，則插入新結(jié)點(diǎn)。這里與示意圖中有點(diǎn)區(qū)別，新結(jié)點(diǎn)插入到鏈表頭。

bool?HashTable::insert(const?char*?key,const?char*?value)
{
????uint?index;
????Node?*np;
????if(!(np=lookup(key))){
????????index?=?hash(key);
????????np?=?(Node*)malloc(sizeof(Node));
????????if(!np)?return?false;
????????np->key=key;
????????np->next?=?node[index];
????????node[index]?=?np;
????}
????np->value=value;
????return?true;
}

? ? 顯示Hash表中的key和value。

void?HashTable::display()
{
	Node*?temp;
	for?(int?i?=?0;?i?<?HASHSIZE;?++i)
	{
		if(!node[i]){
			printf("[]n");
		}else{
			printf("[");
			for?(temp=node[i];?temp;?temp=temp->next)
			{
				printf("[%s][%s]?",temp->key,temp->value?);
			}
			printf("]n");
		}
	}
}

#include?"HashList3.h"

int?main(int?argc,?char?const?*argv[])
{
	HashTable?*ht?=?new?HashTable();
	const?char*?key[]={"a","b"};
	const?char*?value[]={"value1","value2"};
	for?(int?i?=?0;?i?<?2;?++i)
	{
		ht->insert(key[i],value[i]);
	}
	ht->display();
	return?0;
}

關(guān)于哈希表的性能

　　由于哈希表高效的特性，查找或者插入的情況在大多數(shù)情況下可以達(dá)到O(1)，時(shí)間主要花在計(jì)算hash上，當(dāng)然也有最壞的情況就是hash值全都映射到同一個(gè)地址上，這樣哈希表就會(huì)退化成鏈表，查找的時(shí)間復(fù)雜度變成O(n)，但是這種情況比較少，只要不要把hash計(jì)算的公式外漏出去并且有人故意攻擊（用興趣的人可以搜一下基于哈希沖突的拒絕服務(wù)攻擊），一般也不會(huì)出現(xiàn)這種情況。哈希表退化成鏈表如下圖所示：