wikipedia上的解釋

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

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

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

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

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

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

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

/*哈希表*/

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

// 每個slot 為一個鏈表

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

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

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