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

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

? ? ? ? ? 人 -> 身份證號

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

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

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

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

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

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

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

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

哈希沖突解決辦法

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

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

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

#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();
};

　　然后定義哈希表的構造方法

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

　　第三步。
　　定義一個查找根據(jù)key查找結點的方法，首先是用Hash函數(shù)計算頭地址，然后根據(jù)頭地址向下一個個去查找結點，如果結點的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;
}

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

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

關于哈希表的性能

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