基于哈希函數(shù)的查找算法設(shè)計(jì)及性能分析

賈 丹，張 興

(遼寧工業(yè)大學(xué)電子與信息工程學(xué)院，遼寧錦州121001)

查找是計(jì)算機(jī)程序設(shè)計(jì)中重要的操作，查找操作指的是如何根據(jù)給定的記錄關(guān)鍵字的值，在查找表中查找是否有和給定值相等的記錄存在．如果存在，則查找成功;否則，查找失?。?］．查找操作是非常常見(jiàn)的操作，廣泛用于管理系統(tǒng)的設(shè)計(jì)及檢索的實(shí)現(xiàn)．本文提出了基于哈希函數(shù)的查找算法，不需要進(jìn)行比較，直接定位到要查找的記錄，從而提高查找效率．

1 傳統(tǒng)的查找算法

1．1 數(shù)據(jù)結(jié)構(gòu)的定義

以圖書(shū)館中圖書(shū)信息的查詢?yōu)槔瑘D書(shū)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)定義如下:

Typedef struct

{char isbn［20］;//圖書(shū)的 ISBN 號(hào)

char name［40］;//圖書(shū)名字

char author［20］;//作者姓名

char press［20］;//出版社名字

float price;//價(jià)格

}book［］;

1．2 順序查找算法設(shè)計(jì)及性能分析

順序查找是最簡(jiǎn)單的查找方法，其對(duì)應(yīng)的類(lèi)C算法如下:

int sequen(book a，char number［20］)

{//在圖書(shū)信息表中順序查找ISBN號(hào)為number的圖書(shū)，如果查找成功，返回其位置，否則，返回0值．

a［0］．isbn=number;//查找的關(guān)鍵字放到監(jiān)督哨位置

i=n;//n代表圖書(shū)表的長(zhǎng)度

while(a［i］．isbn!=number)

－－i;

Return(i);

}

在該算法中，－－i這條語(yǔ)句是在分析算法時(shí)間復(fù)雜度時(shí)選擇的源操作語(yǔ)句，該語(yǔ)句重復(fù)頻度最大值為n，所以該算法的時(shí)間復(fù)雜度T(n)=O(n)，也就是隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和n的增長(zhǎng)率相同［2］．由上述分析可見(jiàn)，順序查找算法簡(jiǎn)單，適用范圍廣，但是查找效率低．

1．3 折半查找算法設(shè)計(jì)及性能分析

如果圖書(shū)信息是按ISBN號(hào)有序排列的，可以選擇另外一種高效的查找算法——折半查找，其對(duì)應(yīng)的類(lèi)C算法設(shè)計(jì)如下:

int binary(book a，char number［20］)

{//在圖書(shū)信息表中折半查找ISBN號(hào)為number的圖書(shū)，如果查找成功，返回其位置，否則，返回0值．low=1;hig=n;

while(low＜=hig)

{

mid=(low+hig)/2;

if(number==a［mid］．isbn)

return(mid);

else if(number＞a［mid］．isbn)

low=mid+1;

else hig=mid－1;

}

return(0);

}

折半查找算法中，單純通過(guò)選擇源操作語(yǔ)句頻度來(lái)分析算法的時(shí)間復(fù)雜度是比較困難的，可以通過(guò)折半查找判定樹(shù)來(lái)推導(dǎo)算法的時(shí)間復(fù)雜度．如圖1所示，對(duì)于長(zhǎng)度為n的有序表，折半查找在查找成功時(shí)和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)不會(huì)超過(guò)判定樹(shù)的深度，折半查找判定樹(shù)的深度為，因此，可以得到該算法的時(shí)間復(fù)雜度

2 基于哈希函數(shù)的查找算法

在上述傳統(tǒng)的查找算法中，無(wú)論是順序查找還是折半查找，均需要待查找的關(guān)鍵字和查找表中記錄的關(guān)鍵字進(jìn)行比較來(lái)實(shí)現(xiàn)，并以比較次數(shù)來(lái)衡量算法的效率．哈希函數(shù)則是在記錄的關(guān)鍵字和存儲(chǔ)位置之間建立一個(gè)對(duì)應(yīng)關(guān)系H(key)，key是關(guān)鍵字，H(key)是記錄的存儲(chǔ)位置，當(dāng)進(jìn)行查找操作時(shí)，只需要根據(jù)輸入的關(guān)鍵字的值，通過(guò)哈希函數(shù)計(jì)算出存儲(chǔ)位置，而不需要進(jìn)行關(guān)鍵字的比較，從而提高查找效率．從理論上來(lái)說(shuō)，比較次數(shù)為0，但是由于有沖突的存在，還達(dá)不到ASL=0的理想狀態(tài)，但相對(duì)于傳統(tǒng)的查找方法，查找效率非常高．

2．1 哈希函數(shù)的選擇

哈希函數(shù)的設(shè)定有很多方法，例如，直接定址法、折疊法、數(shù)字分析法、平方取中法、隨機(jī)數(shù)法、除留余數(shù)法［4］等，經(jīng)過(guò)綜合分析圖書(shū)信息中數(shù)據(jù)的特點(diǎn)，本文選擇數(shù)字分析法和折疊法的一種結(jié)合方法來(lái)作為哈希函數(shù)．

通常ISBN號(hào)是13位的十進(jìn)制數(shù)字，假如有800條圖書(shū)記錄，則哈希表的表長(zhǎng)為1000就可以了，則可取3位十進(jìn)制數(shù)組成哈希地址．如何選取3位并使沖突盡可能地減少呢?以下是一組圖書(shū)的ISBN號(hào):

9787560625300

9787302314158

9787115333735

．．．．

9787302023685

9787302086567

9787115069719

首先采用數(shù)字分析法分析數(shù)字特點(diǎn)，前4位是9787的概率較高，第5、6、7位是115或302的概率較高，而第8～13位分布比較均勻，可以選擇其中任意3位做為哈希地址．為了進(jìn)一步減少?zèng)_突，綜合折疊法的思想，取第8～10位和第11～13位之和然后舍去進(jìn)位位作為哈希地址．哈希函數(shù)選定后，根據(jù)這個(gè)思想建立哈希表，并在哈希表的基礎(chǔ)上進(jìn)行查找［5］．

2．2 哈希函數(shù)的設(shè)計(jì)

哈希函數(shù)的構(gòu)造算法如下:

Int Hash(char a［］)

{//a為圖書(shū)的ISBN號(hào)，輸入a值，經(jīng)過(guò)轉(zhuǎn)換和運(yùn)算，輸出其存儲(chǔ)位置

char str1［4］ ={""};

strncat(str1，a+7，3);//取出 ISBN 號(hào)中的第 8～10位

char str2［4］ ={""};

strncat(str2，a+10，3);//取出 ISBN 號(hào)中的第 11～13位

int s1=atoi(str1);//將第8～10位轉(zhuǎn)換成為整數(shù)

int s2=atoi(str2);//將第11～13位轉(zhuǎn)換成為整數(shù)

return(s1+s2)%1000;//取二者之和然后舍去進(jìn)位位作為哈希地址

}

2．3 哈希沖突處理

哈希沖突指的是，對(duì)于不同的關(guān)鍵字，得到相同的哈希地址．即key1!=key2，Hash(key1)=Hash(key2)．比如，對(duì)于不同的圖書(shū)，ISBN號(hào)分別是9787723458736和9787734069125，采用上述的哈希函數(shù)，得到相同的哈希地址194．沖突是不可能完全避免的，只能盡可能地減少?zèng)_突，當(dāng)有沖突發(fā)生的時(shí)候，要選擇合適的方法處理沖突．處理沖突的方法有很多，常見(jiàn)的有開(kāi)放定址法、鏈地址法、再哈希法和建立一個(gè)公共溢出區(qū)等方法．由于本文設(shè)計(jì)的哈希函數(shù)分布比較均勻，可以選擇比較簡(jiǎn)單的開(kāi)放定址法中的線性探測(cè)再散列來(lái)處理沖突，具體的公式為:

式中，Hi代表經(jīng)過(guò)i次沖突后得到的下一個(gè)哈希地址，Hash(key)代表哈希函數(shù)的值，di是一個(gè)增量序列［6］，在線性探測(cè)再散列中，di=i，m代表哈希表的表長(zhǎng)．

當(dāng)設(shè)計(jì)好哈希函數(shù)，選擇好相應(yīng)的處理沖突的方法后，就可以將一組記錄根據(jù)ISBN的值將其映像到一個(gè)有限的連續(xù)的地址區(qū)間上，并用關(guān)鍵字在地址區(qū)間中的“像”作為記錄在表中的存儲(chǔ)位置，此時(shí)用于存儲(chǔ)記錄的表就稱(chēng)之為哈希表．例如，根據(jù)上述的哈希函數(shù)，筆者將ISBN為9787560625300的記錄存儲(chǔ)在表中的第925位置上．

2．4 哈希查找算法的設(shè)計(jì)

int hashsearch(book a，char number［20］)

{//在圖書(shū)信息哈希表中按上述設(shè)計(jì)的哈希函數(shù)和處理沖突的方法查找ISBN號(hào)為number的圖書(shū)，如果查找成功，返回其位置，否則，返回0值．

k=Hash(number)//首先求出ISBN號(hào)為number的哈希函數(shù)的值，即哈希地址

i=1;

while(a［k］．isbn!=number＆＆(a［k］．isbn!=null)//在哈希地址中未找到查找記錄且未找到空記錄

{k=(Hash(key)+di)%m;//計(jì)算經(jīng)過(guò)沖突后的下一個(gè)哈希地址

i++:

}

if(a［k］．isbn==number)return(k);//查找成功

else return 0;//找到一個(gè)空記錄，查找失敗

}

3 性能分析

通過(guò)對(duì)以上3種查找算法的分析，可以得到表1所示的性能對(duì)比結(jié)果．可見(jiàn)，隨著待查找記錄個(gè)數(shù)n的增長(zhǎng)，順序查找與折半查找算法執(zhí)行時(shí)間的增長(zhǎng)率分別與n和log2n的增長(zhǎng)率成正比，但是哈希查找算法執(zhí)行時(shí)間的增長(zhǎng)率與n無(wú)關(guān)，是查找效率非常高的查找算法．

表1 3種查找算法的性能對(duì)比

4 結(jié)束語(yǔ)

查找是計(jì)算機(jī)程序設(shè)計(jì)中最為普遍的操作，查找的效率也是計(jì)算機(jī)領(lǐng)域一直關(guān)注的問(wèn)題．本文以圖書(shū)信息檢索為例，在傳統(tǒng)的順序查找和折半查找基礎(chǔ)上，提出了哈希查找的思想，結(jié)合數(shù)字分析法和折疊法建立了哈希函數(shù)，采用線性探測(cè)再散列解決沖突．與傳統(tǒng)的方法相比，查找效率更高．

［1］嚴(yán)蔚繁，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)［M］．北京:清華大學(xué)出版社，2008．

［2］王云鵬．線性時(shí)間選擇算法時(shí)間復(fù)雜度深入研究［J］．軟件開(kāi)發(fā)與設(shè)計(jì)，2009(14):3－5．

［3］AnanyLevitin．Introduction to The Design and Analysis of Algorithms［M］．北京:清華大學(xué)出版社，2004．

［4］葉軍偉．哈希函數(shù)構(gòu)造方法及其適用情況［J］．科技致富向?qū)В?014(8):278－279．

［5］鄒又姣，馬文平，冉占軍，等．改進(jìn)的多變量哈希函數(shù)［J］．計(jì)算機(jī)科學(xué)，2013，6(40):45－49．

［6］肖麗．哈希查找中散列函數(shù)的運(yùn)用［J］．技術(shù)研發(fā)，2009，8(16):18－20．