一印蔬、基本概念
哈希表（hash table）是一種根據(jù)關(guān)鍵字直接訪問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)勋桶，通過(guò)哈希表，數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關(guān)鍵字之間建立起某種對(duì)應(yīng)關(guān)系侥猬，建立這種對(duì)應(yīng)關(guān)系的函數(shù)稱為哈希函數(shù)例驹。
哈希表
二、哈希表的構(gòu)造方法
假設(shè)要存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)是n陵究，設(shè)置一個(gè)長(zhǎng)度為m(m > n)的連續(xù)存儲(chǔ)單元眠饮，分別以每個(gè)數(shù)據(jù)元素的關(guān)鍵字Ki(0<=i<=n-1)為自變量，通過(guò)哈希函數(shù)hash(Ki)铜邮，把Ki映射為內(nèi)存單元的某個(gè)地址hash(Ki),并將數(shù)據(jù)元素存儲(chǔ)在內(nèi)存單元中。
從數(shù)學(xué)的角度看，哈希函數(shù)實(shí)際上是關(guān)鍵字到內(nèi)存單元的映射松蒜，因此我們希望通過(guò)哈希函數(shù)通過(guò)盡量簡(jiǎn)單的運(yùn)算使得哈希函數(shù)計(jì)算出的哈希地址盡量均勻的被映射到一系列的內(nèi)存單元中扔茅，構(gòu)造哈希函數(shù)有三個(gè)要點(diǎn)：（1）運(yùn)算過(guò)程要盡量簡(jiǎn)單高效，以提高哈希表的插入和檢索效率秸苗；（2）哈希函數(shù)應(yīng)該具有較好的散列型召娜，以降低哈希沖突的概率；第三惊楼，哈希函數(shù)應(yīng)具有較大的壓縮性玖瘸，以節(jié)省內(nèi)存。
（1）直接地址法：以關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址檀咙，可以表示為hash(K)=aK+C;優(yōu)點(diǎn)是不會(huì)產(chǎn)生沖突雅倒，缺點(diǎn)是空間復(fù)雜度可能會(huì)較高，適用于元素較少的情況
（2）除留余數(shù)法：它是由數(shù)據(jù)元素關(guān)鍵字除以某個(gè)常數(shù)所留的余數(shù)為哈希地址弧可，該方法計(jì)算簡(jiǎn)單蔑匣，適用范圍廣，是經(jīng)常使用的一種哈希函數(shù)棕诵，可以表示為：
hash(K=K mod C)該方法的關(guān)鍵是常數(shù)的選取裁良，一般要求是接近或等于哈希表本身的長(zhǎng)度，研究理論表明校套，該常數(shù)選素?cái)?shù)時(shí)效果最好
（3）數(shù)字分析法：該方法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字來(lái)作為哈希地址的方法价脾，這樣可以盡量避免沖突，但是該方法只適合于所有關(guān)鍵字已知的情況笛匙，對(duì)于想要設(shè)計(jì)出更加通用的哈希表并不適用
三彼棍、哈希沖突的解決方案
在構(gòu)造哈希表時(shí)，存在這樣的問(wèn)題：對(duì)于兩個(gè)不同的關(guān)鍵字膳算，通過(guò)我們的哈希函數(shù)計(jì)算哈希地址時(shí)卻得到了相同的哈希地址座硕，我們將這種現(xiàn)象稱為哈希沖突
哈希沖突
哈希沖突主要與兩個(gè)因素有關(guān)
（1）填裝因子，填裝因子是指哈希表中已存入的數(shù)據(jù)元素個(gè)數(shù)與哈希地址空間的大小的比值涕蜂，a=n/m ; a越小华匾，沖突的可能性就越小，相反則沖突可能性較大机隙；但是a越小空間利用率也就越小蜘拉，a越大，空間利用率越高有鹿，為了兼顧哈希沖突和存儲(chǔ)空間利用率旭旭，通常將a控制在0.6-0.9之間，而.net中的HashTable則直接將a的最大值定義為0.72 （雖然微軟官方MSDN中聲明HashTable默認(rèn)填裝因子為1.0葱跋，但實(shí)際上都是0.72的倍數(shù)）
（2）與所用的哈希函數(shù)有關(guān)持寄，如果哈希函數(shù)得當(dāng)源梭，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少?zèng)_突的產(chǎn)生稍味，但一個(gè)良好的哈希函數(shù)的得來(lái)很大程度上取決于大量的實(shí)踐废麻。
哈希沖突通常是很難避免的，解決哈希沖突有很多種方法模庐，通常分為兩大類：
1.開(kāi)放地址法：他是一類以發(fā)生哈希沖突的哈希地址為自變量烛愧，通過(guò)某種哈希函數(shù)得到一個(gè)新的空閑內(nèi)存單元地址的方法，開(kāi)放地址法的哈希沖突函數(shù)通常是一組
image.png
2.鏈表法：當(dāng)未發(fā)生沖突時(shí)掂碱，直接存放數(shù)據(jù)怜姿，當(dāng)沖突產(chǎn)生時(shí)，把產(chǎn)生沖突的數(shù)據(jù)元素另外存放在單鏈表中
image.png
