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