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

　　25、Hash表(散列表)

　　(1)基本概念

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

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

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

　　(2)常用的構造散列函數的方法

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

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

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

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

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

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

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

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

　　(3)處理沖突的方法

　　[1]開放定址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)為散列函數，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=偽隨機數序列，稱偽隨機探測再散列。

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

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

　　[4]建立一個公共溢出區

　　(4)查找的性能分析

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

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

　　[1]散列函數是否均勻;

　　[2]處理沖突的方法;

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

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

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

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

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

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

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