更多:2011年軟考程序員考試復(fù)習(xí)筆試知識點(diǎn)整理匯總
25、Hash表(散列表)
(1)基本概念
若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄,則必定在f(K)的存儲位置上。由此,不需比較便可直接取得所查記錄。稱這個(gè)對應(yīng)關(guān)系f為散列函數(shù)(Hash function),按這個(gè)思想建立的表為散列表。
對不同的關(guān)鍵字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述,根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集(區(qū)間)上,并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置,這種表便稱為散列表,這一映象過程稱為散列造表或散列,所得的存儲位置稱散列地址。
若對于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字,經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的,則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function),這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個(gè)“隨機(jī)的地址”,從而減少?zèng)_突。
(2)常用的構(gòu)造散列函數(shù)的方法
散列函數(shù)能使對一個(gè)數(shù)據(jù)序列的訪問過程更加迅速有效,通過散列函數(shù),數(shù)據(jù)元素將被更快地定位。
[1]直接定址法:取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a•key + b,其中a和b為常數(shù)(這種散列函數(shù)叫做自身函數(shù))
[2]數(shù)字分析法: 一般取一些大一點(diǎn)的素?cái)?shù),效果更好點(diǎn)。
[3]平方取中法:計(jì)算關(guān)鍵值再取中間r位形成一個(gè)2^r位的表
[4]折疊法:把所有字符的ASCII碼加起來 (對于字符串)
[5]隨機(jī)數(shù)法:選擇一個(gè)隨機(jī)函數(shù),取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址,即H(key)=random(key),其中random為隨機(jī)函數(shù)。通常關(guān)鍵字長度不等時(shí)采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。
[6]除留余數(shù)法:取關(guān)鍵字被某個(gè)不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模,也可在折疊、平方取中等運(yùn)算之后取模。對p的選擇很重要,一般取素?cái)?shù)或m,若p選的不好,容易產(chǎn)生同義詞。
[7]針對字符串的一些常用方法,比如ELFHash和BKDRHash(更易于編寫,效率不錯(cuò))
(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=偽隨機(jī)數(shù)序列,稱偽隨機(jī)探測再散列。
[2]再散列法:Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函數(shù),即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)散列函數(shù)地址,直到?jīng)_突不再發(fā)生,這種方法不易產(chǎn)生“聚集”,但增加了計(jì)算時(shí)間。
[3]鏈地址法(拉鏈法)
[4]建立一個(gè)公共溢出區(qū)
(4)查找的性能分析
散列表的查找過程基本上和造表過程相同。一些關(guān)鍵碼可通過散列函數(shù)轉(zhuǎn)換的地址直接找到,另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突,需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中,產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過程。所以,對散列表查找效率的量度,依然用平均查找長度來衡量。
查找過程中,關(guān)鍵碼的比較次數(shù),取決于產(chǎn)生沖突的多少,產(chǎn)生的沖突少,查找效率就高,產(chǎn)生的沖突多,查找效率就低。因此,影響產(chǎn)生沖突多少的因素,也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素:
[1]散列函數(shù)是否均勻;
[2]處理沖突的方法;
[3]散列表的裝填因子。
散列表的裝填因子定義為:α= 填入表中的元素個(gè)數(shù) / 散列表的長度
α是散列表裝滿程度的標(biāo)志因子。由于表長是定值,α與“填入表中的元素個(gè)數(shù)”成正比,所以,α越大,填入表中的元素較多,產(chǎn)生沖突的可能性就越大;α越小,填入表中的元素較少,產(chǎn)生沖突的可能性就越小。
實(shí)際上,散列表的平均查找長度是裝填因子α的函數(shù),只是不同處理沖突的方法有不同的函數(shù)。
相關(guān)推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |