2011年軟考程序員考試復(fù)習筆試知識點整理(21)

　　更多：2011年軟考程序員考試復(fù)習筆試知識點整理匯總

　　25、Hash表(散列表)

　　(1)基本概念

　　若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)(Hash function)，按這個思想建立的表為散列表。

　　對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。

　　若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function)，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突。

　　(2)常用的構(gòu)造散列函數(shù)的方法

　　散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快地定位。

　　[1]直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a•key + b，其中a和b為常數(shù)(這種散列函數(shù)叫做自身函數(shù))

　　[2]數(shù)字分析法： 一般取一些大一點的素數(shù)，效果更好點。

　　[3]平方取中法:計算關(guān)鍵值再取中間r位形成一個2^r位的表

　　[4]折疊法:把所有字符的ASCII碼加起來 (對于字符串)

　　[5]隨機數(shù)法：選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即H(key)=random(key),其中random為隨機函數(shù)。通常關(guān)鍵字長度不等時采用此法構(gòu)造哈希函數(shù)較恰當。

　　[6]除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生同義詞。

　　[7]針對字符串的一些常用方法，比如ELFHash和BKDRHash(更易于編寫，效率不錯)

　　(3)處理沖突的方法

　　[1]開放定址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)為散列函數(shù)，m為散列表長，di為增量序列，可有下列三種取法：

　　di=1,2,3,…, m-1，稱線性探測再散列;

　　di=1^2, -1^2, 2^2,-2^2,3^2, …, ±k^2,(k<=m/2)稱二次探測再散列;

　　di=偽隨機數(shù)序列，稱偽隨機探測再散列。

　　[2]再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計算時間。

　　[3]鏈地址法(拉鏈法)

　　[4]建立一個公共溢出區(qū)

　　(4)查找的性能分析

　　散列表的查找過程基本上和造表過程相同。一些關(guān)鍵碼可通過散列函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

　　查找過程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個因素：

　　[1]散列函數(shù)是否均勻;

　　[2]處理沖突的方法;

　　[3]散列表的裝填因子。

　　散列表的裝填因子定義為：α= 填入表中的元素個數(shù) / 散列表的長度

　　α是散列表裝滿程度的標志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大;α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。

　　實際上，散列表的平均查找長度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

　　軟考程序員考試歷年真題重點題總結(jié)及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)