wikipedia上的解釋

http://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8

下圖示意了哈希表（Hash Table）這種數(shù)據(jù)結(jié)構(gòu)。

如上圖所示，首先分配一個(gè)指針數(shù)組，數(shù)組的每個(gè)元素是一個(gè)鏈表的頭指針，每個(gè)鏈表稱為一個(gè)槽（Slot） 。哪個(gè)數(shù)據(jù)應(yīng)該放入哪個(gè)槽中由哈希函數(shù)決定，在這個(gè)例子中我們簡單地選取哈希函數(shù)h(x) = x % 11，這樣任意數(shù)據(jù)x都可以映射成0~10之間的一個(gè)數(shù)，就是槽的編號(hào)，將數(shù)據(jù)放入某個(gè)槽的操作就是鏈表的插入操作。

如果每個(gè)槽里至多只有一個(gè)數(shù)據(jù)，可以想像這種情況下 search 、 insert 和 delete 操作的時(shí)間復(fù)雜度都是O(1)，但有時(shí)會(huì)有多個(gè)數(shù)據(jù)被哈希函數(shù)映射到同一個(gè)槽中，這稱為碰撞（Collision） ，設(shè)計(jì)一個(gè)好的哈希函數(shù)可以把數(shù)據(jù)比較均勻地分布到各個(gè)槽中，盡量避免碰撞。如果能把n個(gè)數(shù)據(jù)比較均勻地分布到m個(gè)槽中，每個(gè)糟里約有n/m個(gè)數(shù)據(jù)，則 search 、 insert 和 delete 和操作的時(shí)間復(fù)雜度都是O(n/m)，如果n和m的比是常數(shù)，則時(shí)間復(fù)雜度仍然是O(1)。一般來說，要處理的數(shù)據(jù)越多，構(gòu)造哈希表時(shí)分配的槽也應(yīng)該越多，所以n和m成正比這個(gè)假設(shè)是成立的。

請(qǐng)讀者自己編寫程序構(gòu)造這樣一個(gè)哈希表，并實(shí)現(xiàn) search 、 insert 和 delete 操作。

如果用我們學(xué)過的各種數(shù)據(jù)結(jié)構(gòu)來表示n個(gè)數(shù)據(jù)的集合，下表是 search 、 insert 和 delete 操作在平均情況下的時(shí)間復(fù)雜度比較。

根據(jù)以上算法，抽象數(shù)據(jù)結(jié)構(gòu)如下：

/*哈希表*/

struct obj_container {
obj_hash_fn *hash_fn;//哈希函數(shù)
obj_callback_fn *cmp_fn;
int n_buckets; //分配多少個(gè)slot ?
int elements; //哈希表中元素?cái)?shù)目
int version;
/*!variable size */
struct bucket buckets[0]; /*! lengthen tailq, each bucket is a linkedlist */
};

// 每個(gè)slot 為一個(gè)鏈表

struct bucket_entry {
SPD_LIST_ENTRY(bucket_entry)entry;
int version;
struct obj *pobj; /* pointer to internal data */
}bucket;

接下來實(shí)現(xiàn) search, link , unlink函數(shù)。

數(shù)據(jù)結(jié)構(gòu)之哈希表