|
|
GLIB散列數(shù)據(jù)結(jié)構(gòu)淺析
一．散列表的基本概念
散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
二．散列函數(shù)【hash function】的構(gòu)造方法
散列函數(shù)能使對(duì)一個(gè)數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快地定位，常用的構(gòu)造方法有：
1 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a??key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）
2 數(shù)學(xué)分析法
3 平方取中法
4 折疊法
5 隨機(jī)數(shù)法
6 除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p, p<=m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞
像第1種方法，要求關(guān)鍵字集合和地址集合具有相同的大小空間，一般用于數(shù)據(jù)記錄不多的情況；第6種方法則不同，一般情況下，地址集合所占用的空間明顯小于關(guān)鍵字集合，因此適合于大量數(shù)據(jù)的情況，但是它會(huì)帶來一個(gè)現(xiàn)象，即存在著多個(gè)關(guān)鍵字對(duì)應(yīng)著一個(gè)地址，這種現(xiàn)象用專業(yè)術(shù)語來講叫沖突。
三．處理沖突的方法
1 開放定址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)為散列函數(shù)，m為散列表長，di為增量序列，可有下列三種取法：
1) di=1,2,3,…, m-1，稱線性探測(cè)再散列；
2) di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)稱二次探測(cè)再散列;
3) di=偽隨機(jī)數(shù)序列，稱偽隨機(jī)探測(cè)再散列。
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ū)
其中關(guān)于開放地址法和拉鏈法的介紹請(qǐng)參考博文：http://hi.baidu.com/zkheartboy/b ... 9296159f3d0.hta> 。在Glib中，對(duì)hash沖突處理采用了第3種“拉鏈法”來處理，下圖所示。
四．Ghash表總體結(jié)構(gòu)
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
