欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標(biāo)題: GLIB散列數(shù)據(jù)結(jié)構(gòu)淺析【原】 [打印本頁]

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

歡迎光臨 (http://www.raoushi.com/bbs/)