通過哈希表進(jìn)行查找的特點(diǎn)是：不需要比較關(guān)鍵字，而是通過哈希函數(shù)計(jì)算出關(guān)鍵字的位置。一般來(lái)講，為了進(jìn)行高效率的查找，要求哈希函數(shù)簡(jiǎn)單均勻、空間利用率高、關(guān)鍵字之間的沖突少。

關(guān)于散列查找的實(shí)現(xiàn)需要著重考慮兩個(gè)問題：1，散列函數(shù)的設(shè)計(jì) 2，解決沖突問題

函數(shù)構(gòu)造方法

常用的方法有：
1，直接定址法：H(key)=axkey+b，特點(diǎn)：簡(jiǎn)單、無(wú)沖突，但造成存儲(chǔ)空間浪費(fèi)
2，數(shù)字分析法 3，平方取中法 4，折疊法 5，隨機(jī)數(shù)法
6，除留余數(shù)法：H(key)=key%p，p一般取小于等于表長(zhǎng)的質(zhì)數(shù)，表長(zhǎng)用m來(lái)表示，存儲(chǔ)元素的個(gè)數(shù)用n來(lái)表示
因?yàn)槌粲鄶?shù)法最為常用，下面以除留余數(shù)法來(lái)介紹解決沖突的方法

沖突的解決

沖突：如果有多個(gè)關(guān)鍵字通過哈希函數(shù)所計(jì)算出的結(jié)果相同，則稱這些關(guān)鍵字互相沖突，并將這些關(guān)鍵字稱為同義詞
1，開放定址法： Hi=(H(key)+di)%n，i=1,2,3…n-1 di表示第i次沖突的增量，Hi為第i次沖突后應(yīng)探測(cè)的地址
a，線性探測(cè)再散列：增量為，d1=1，d2=2，d3=3，… 特點(diǎn)，空間利用率高，但容易發(fā)生聚集現(xiàn)象
b，二次探測(cè)再散列：增量為，d1=1，d2=-1，d3=4，d4=-4，d5=9，d6=-9，…分別為正負(fù)1，2，3，4…的平方
c，偽隨機(jī)數(shù)探測(cè)再散列：增量di為偽隨機(jī)數(shù)
2，鏈地址法（拉鏈法）：
假設(shè)對(duì)n個(gè)數(shù)的哈希函數(shù)為H(key)=key%p。建立數(shù)組array[p]，數(shù)組下標(biāo)分別對(duì)應(yīng)所計(jì)算出的哈希值，將每個(gè)數(shù)存儲(chǔ)在它對(duì)應(yīng)的位置上。若發(fā)生沖突的話，將該沖突的數(shù)掛在它的同義詞后面（類似于圖的鄰接表存儲(chǔ)）
3，再哈希法：再設(shè)計(jì)一個(gè)哈希函數(shù)來(lái)解決沖突

平均查找長(zhǎng)度(ASL)

散列查找理論上平均查找長(zhǎng)度為常數(shù)1，即ASL=1，但由于沖突，所以ASL總是大于1的。引入裝填因子α，α=元素個(gè)數(shù)/表長(zhǎng)=n/m。
1，開放定址法
其中以線性探測(cè)在散列為例：
它的平均查找長(zhǎng)度，ASL(平均）=(1+1/(1-α))/2
ASL(成功）=（每個(gè)元素查找成功的比較次數(shù)相加）/元素個(gè)數(shù)
ASL(失敗）=（每個(gè)元素查找失敗的比較次數(shù)相加）/p
對(duì)于表長(zhǎng)m=14，元素個(gè)數(shù)n=11，哈希函數(shù)為H(key)=key%13，其中p=13的哈希表：

下標(biāo)012345678910111213

元素	\	1	2	3	4	5	6	7	8	9	10	11	\

ASL(成功）=（1+1+…+1)/11=1
ASL(失敗）=（1+12+11+…+3+2)/13=6
2，鏈地址法
ASL(平均）=1+α/2
ASL(成功）=（每個(gè)元素查找成功的比較次數(shù)相加）/元素個(gè)數(shù)
ASL(失敗）=（每個(gè)元素查找失敗的比較次數(shù)相加）/p
對(duì)于下圖：

元素個(gè)數(shù)n=12，哈希函數(shù)為H(key)=key%11，其中p=11。
ASL(成功）=（6x1+4x2+3+4)/12=7/4
ASL(失敗）=（4+2x3+1+1)/11=12/11(其中和空結(jié)點(diǎn)比較的次數(shù)計(jì)為0）

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的哈希表（散列查找）(c/c++)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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