前言

　　　當(dāng)我們?cè)诰幊踢^程中，往往需要對(duì)線性表進(jìn)行查找操作。在順序表中查找時(shí)，需要從表頭開始，依次遍歷比較a[i]與key的值是否相等，直到相等才返回索引i；在有序表中查找時(shí)，我們經(jīng)常使用的是二分查找，通過比較key與a[i]的大小來折半查找，直到相等時(shí)才返回索引i。最終通過索引找到我們要找的元素。
　　　但是，這兩種方法的效率都依賴于查找中比較的次數(shù)。我們有一種想法，能不能不經(jīng)過比較，而是直接通過關(guān)鍵字key一次得到所要的結(jié)果呢？這時(shí)，就有了散列表查找（哈希表）。

1、什么是哈希表

　　　 要說哈希表，我們必須先了解一種新的存儲(chǔ)方式—散列技術(shù)。
　　　 散列技術(shù)是指在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每一個(gè)關(guān)鍵字都對(duì)應(yīng)一個(gè)存儲(chǔ)位置。即：存儲(chǔ)位置=f（關(guān)鍵字）。這樣，在查找的過程中，只需要通過這個(gè)對(duì)應(yīng)關(guān)系f 找到給定值key的映射f（key）。只要集合中存在關(guān)鍵字和key相等的記錄，則必在存儲(chǔ)位置f（key）處。我們把這種對(duì)應(yīng)關(guān)系f 稱為散列函數(shù)或哈希函數(shù)。
　　　 按照這個(gè)思想，采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)的存儲(chǔ)空間稱為哈希表。所得的存儲(chǔ)地址稱為哈希地址或散列地址。

2、哈希表查找步驟

　　　①、存儲(chǔ)數(shù)據(jù)時(shí)，將數(shù)據(jù)存入通過哈希函數(shù)計(jì)算所得哪那個(gè)地址里面。
　　　②、查找時(shí)，使用同一個(gè)哈希函數(shù)通過關(guān)鍵字key計(jì)算出存儲(chǔ)地址，通過該地址即可訪問到查找的記錄。

3、哈希沖突

　　在理想的情況下，每一個(gè) 關(guān)鍵字，通過哈希函數(shù)計(jì)算出來的地址都是不一樣的。但是在實(shí)際情況中，我們常常會(huì)碰到兩個(gè)關(guān)鍵字key1≠key2,但是f(key1) = f(key2), 這種現(xiàn)象稱為沖突，并把key1和key2稱為這個(gè)散列函數(shù)的同義詞。
　　沖突的出現(xiàn)會(huì)造成查找上的錯(cuò)誤，具體解決方法會(huì)在后文提到。

4、哈希函數(shù)的構(gòu)造方法

（1）、原則

　　①、計(jì)算簡(jiǎn)單；
　　②、散列地址分布均勻。

（2）、構(gòu)造方法

　　①、直接定址法：不常用
　　 　取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址：
　　 　即：Ｈ(key) = key 或 H(key) = a*key+b
　　　　優(yōu)點(diǎn)：簡(jiǎn)單，均勻，不會(huì)產(chǎn)生沖突；
　　　　缺點(diǎn)：需要實(shí)現(xiàn)直到關(guān)鍵字的分布情況，適合查找表比較小且連續(xù)的情況。
　　
　　②、數(shù)字分析法
　　　數(shù)字分析法用于處理關(guān)鍵字是位數(shù)比較多的數(shù)字，通過抽取關(guān)鍵字的一部分進(jìn)行操作，計(jì)算哈希存儲(chǔ)位置的方法。
　　　例如：關(guān)鍵字是手機(jī)號(hào)時(shí)，眾所周知，我們的１１位手機(jī)號(hào)中，前三位是接入號(hào)，一般對(duì)應(yīng)不同運(yùn)營(yíng)商的子品牌；中間四位是ＨＬＲ識(shí)別號(hào)，表示用戶號(hào)的歸屬地；最后四位才是真正的用戶號(hào)，所以我們可以選擇后四位成為哈希地址，對(duì)其在進(jìn)行相應(yīng)操作來減少?zèng)_突。
　　　數(shù)字分析法適合處理關(guān)鍵字位數(shù)比較大的情況，事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布均勻。
　　　
　　③、平方取中法
　　　具體方法很簡(jiǎn)單：先對(duì)關(guān)鍵字取平方，然后選取中間幾位為哈希地址；取的位數(shù)由表長(zhǎng)決定，適用于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。
　　
　　④、折疊法
　　 將關(guān)鍵字分成位數(shù)相同的幾部分（最后一部分位數(shù) 可以不同），然后求這幾部分的疊加和（舍去進(jìn)位），并按照散列表的表長(zhǎng)，取后幾位作為哈希地址。
　　 適用于關(guān)鍵字位數(shù)很多，而且關(guān)鍵字每一位上數(shù)字分布大致均勻。
　　
　　 ⑤、除留余數(shù)法
　　 此方法為最常用的構(gòu)造哈希函數(shù)方法。對(duì)于哈希表長(zhǎng)為m的哈希函數(shù)公式為：
　　 f(key) = key mod p (p <= m)
　　 此方法不僅可以對(duì)關(guān)鍵字直接取模，也可以在折疊、平方取中之后再取模。
　　 所以，本方法的關(guān)鍵在于選擇合適的p，若是p選擇的不好，就可能產(chǎn)生 同義詞；根據(jù)前人經(jīng)驗(yàn)，若散列表的表長(zhǎng)為m，通常p為小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。
　　
　　 ⑥、隨機(jī)數(shù)法
　　 選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值作為他的哈希地址。
　　 即：f(key) = random (key)
　　 當(dāng)關(guān)鍵字的長(zhǎng)度不等時(shí)，采用這個(gè)方法構(gòu)造哈希函數(shù)較為合適。當(dāng)遇到特殊字符的關(guān)鍵字時(shí)，需要將其轉(zhuǎn)換為某種數(shù)字。

（3）、參考因素

　　　在實(shí)際應(yīng)用過程中，應(yīng)該視不同的情況采用不同的哈希函數(shù)。下列是一些參考因素：
　　　　①計(jì)算哈希地址所需的時(shí)間；
　　　　②關(guān)鍵字的長(zhǎng)度；
　　　　③哈希表的大小；
　　　　④關(guān)鍵字的分布情況；
　　　　⑤查找的頻率。
　　　選擇哈希函數(shù)時(shí)，我們應(yīng)該綜合以上因素，選擇合適的構(gòu)建哈希函數(shù)的方法。

５、哈希沖突的解決

　　　前文提到，哈希沖突不能避免，所以我們需要找到方法來解決它。
　　　哈希沖突的解決方案主要有四種：開放地址法；再哈希；鏈地址法；公共溢出區(qū)法。

（1）、開放地址法　　

　　 開放地址法就是指：一旦發(fā)生了沖突就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的散列地址總能找到，并將記錄存入。
　　 公式：Hi=(H(*key) + Di) mod m (i = 1,2,3,….,k k<=m-1)
　　 其中：H（key）為哈希函數(shù)；m為哈希表表長(zhǎng)；Di為增量序列，有以下3中取法:
　　 　　①Di = 1,2,3,…,m-1, 稱為線性探測(cè)再散列；
　　 　　②Di = 12，－１2，２2，－２2，。。。，±ｋ2，（ｋ<= m/2)稱為二次探測(cè)再散列
　　 　　③Di = 偽隨機(jī)數(shù)序列，稱為偽隨機(jī)數(shù)探測(cè)再散列。
　　 　　例如：在長(zhǎng)度為12的哈希表中插入關(guān)鍵字為38的記錄：
　　 　　
　　 　　從上述線性探測(cè)再散列的過程中可以看出一個(gè)現(xiàn)象：當(dāng)表中i、i+1位置上有記錄時(shí)，下一個(gè)哈希地址為i、i+1、i+2的記錄都將填入i+3的位置，這種本不是同義詞卻要爭(zhēng)奪同一個(gè)地址的現(xiàn)象叫“堆積“。即在處理同義詞的沖突過程中又添加了非同義詞的沖突；但是，用線探測(cè)再散列處理沖突可以保證：只要哈希表未填滿，總能找到一個(gè)不發(fā)生沖突的地方。

（2）、再哈希法

　　 　　公式：Hi = RHi（key） i = 1，2，…，k
　　 　　RHi均是不同的哈希函數(shù)，意思為：當(dāng)繁盛沖突時(shí)，使用不同的哈希函數(shù)計(jì)算地址，直到不沖突為止。這種方法不易產(chǎn)生堆積，但是耗費(fèi)時(shí)間。

（3）、鏈地址法

　　 　　將所有關(guān)鍵字為同義字的記錄存儲(chǔ)在一個(gè)單鏈表中，我們稱這種單鏈表為同義詞子表，散列表中存儲(chǔ)同義詞子表的頭指針。
　　 　　如關(guān)鍵字集合為{19，14，23，01，68，20，84，27，55，11，10，79}，按哈希函數(shù)H（key） = key mod 13；
　　 　　
　　 　　鏈地址法解決了沖突，提供了永遠(yuǎn)都能找到地址的保證。但是，也帶來了查找時(shí)需要遍歷單鏈表的性能損耗。

（4）、公共溢出區(qū)法

　　 　　即設(shè)立兩個(gè)表：基礎(chǔ)表和溢出表。將所有關(guān)鍵字通過哈希函數(shù)計(jì)算出相應(yīng)的地址。然后將未發(fā)生沖突的關(guān)鍵字放入相應(yīng)的基礎(chǔ)表中，一旦發(fā)生沖突，就將其依次放入溢出表中即可。
　　 　　在查找時(shí)，先用給定值通過哈希函數(shù)計(jì)算出相應(yīng)的散列地址后，首先 首先與基本表的相應(yīng)位置進(jìn)行比較，如果不相等，再到溢出表中順序查找。

7、總結(jié)

　　１、哈希表就是一種以鍵值對(duì)存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。
　　2、哈希表是一個(gè)在空間和時(shí)間上做出權(quán)衡的經(jīng)典例子。如果沒有內(nèi)存限制，那么可以
直接將鍵作為數(shù)組的索引。那么所查找的時(shí)間復(fù)雜度為Ｏ(1);如果沒有時(shí)間限制，那么我們可以使用無序數(shù)組并進(jìn)行順序查找，這樣只需要很少的內(nèi)存。哈希表使用了適度的時(shí)間和空間來在這兩個(gè)極端之間找到了平衡。只需要調(diào)整哈希函數(shù)算法即可在時(shí)間和空間上做出取舍。
　　 　　
　　 　　
　　 　　
　　 　　

總結(jié)

以上是生活随笔為你收集整理的什么是哈希表？为什么要使用哈希表？哈希表的实现原理？哈希冲突怎么解决？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。