wikipedia上的解釋

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

下圖示意了哈希表（Hash Table）這種數據結構。

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

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

請讀者自己編寫程序構造這樣一個哈希表，并實現 search 、 insert 和 delete 操作。

如果用我們學過的各種數據結構來表示n個數據的集合，下表是 search 、 insert 和 delete 操作在平均情況下的時間復雜度比較。

根據以上算法，抽象數據結構如下：

/*哈希表*/

struct obj_container {
obj_hash_fn *hash_fn;//哈希函數
obj_callback_fn *cmp_fn;
int n_buckets; //分配多少個slot ?
int elements; //哈希表中元素數目
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;

接下來實現 search, link , unlink函數。

數據結構之哈希表