前言

      散列表（HashTable）又稱為哈希表，是一種快速的數(shù)據(jù)查找結(jié)構(gòu)，它通常是為一個(gè)（組）要記錄的數(shù)據(jù)設(shè)計(jì)一個(gè)哈希函數(shù)H(x)，依據(jù)這個(gè)函數(shù)進(jìn)行給數(shù)據(jù)定位，如果是閉散列，那就是直接存到數(shù)組的H(x)下標(biāo)處，如果是開散列，就是存到指針數(shù)組H(x)下標(biāo)的鏈表處。在OI中某些Pascaler為了避開鏈表而采用的閉散列鄙人認(rèn)為相當(dāng)糟糕，至于原因會(huì)在后面解釋。所以本文只談開散列。

哈希表的組織方式：
      我們首先要確定一個(gè)哈希函數(shù)H(x)，x是要記錄的對(duì)象，我們以H(x)來確定對(duì)象的記錄的鏈的位置。
      還需要一個(gè)指針數(shù)組來存放每個(gè)鏈的頭指針。由于要使用鏈表，所以還要有一個(gè)class/struct作為鏈表的基本單位。

哈希表的一般實(shí)現(xiàn)：
首先是鏈表的基本元素：

template<class T>
struct t_node
{
    public:
        T key;
        //other info
        t_node* next;
};

然后是HashTable類的骨架（我在這里把它封裝成類了）：

template<class T>
class hashtable
{
    public:
        hashtable();
        int hash(const T &sr);
        void insert();
        t_node *find(const T &sr);
        //add more functions
    private:
        t_node *ht[t_size];//you should define t_size as sth before
        //add more things
};

接下來是構(gòu)造函數(shù)：

hashtable<T>::hahstable()
{
    memset(ht,0,sizeof(ht));
}

先略去哈希函數(shù)，介紹插入函數(shù)：

void hashtable<T>::insert(const T &sr)
{
    int loc = hash(sr);
    if (ht[loc] == 0)
    {
        //此處為空，插入一個(gè)新鏈表
        ht[loc] = new t_node();
        ht[loc]-> key = T;
    }
    else
    {
        t_node *now = ht[loc];
        while (true)
        {
            if (now->key == sr)
            {
                //元素已經(jīng)存在。 
                return;
            }
            else if (now->next == 0)
            {
                //鏈里面沒有該元素，就地插入
                now->next = new t_node();
                now->next->key = T; 
                return;
            }
            else now = now->next;
        }
    }
}

然后是查找：

t_node *hashtable<T>::find(const T &st)
{
    int loc = hash(sr);
    if (ht[loc] == 0)
    {
        //此處為空，木有~ 返回空指針 
        return 0;
    }
    else
    {
        t_node *now = ht[loc];
        while (true)
        {
            if (now->key == sr)
            {
                //找到了 
                return now;
            }
            else if (now->next == 0)
            {
                //遍歷完了整個(gè)鏈還是木有。。 
                return 0;
            }
            else now = now->next;//看這個(gè)鏈的下一個(gè)元素 
        }
    }
}

當(dāng)然可以根據(jù)具體情況做各種改動(dòng)，如果要極限追求效率可以在t_node里面把key改為指針，然后使用自己編寫的內(nèi)存分配函數(shù)代替new。


最簡(jiǎn)單的哈希函數(shù)：
其實(shí)最簡(jiǎn)單的哈希表1就是H(x)=x，意思是若記錄對(duì)象是整數(shù)，就直接采用這個(gè)整數(shù)為下標(biāo)（char類型也可視為整數(shù)），這個(gè)就是數(shù)組，但它也可以看作哈希表。
最簡(jiǎn)單的哈希表2就是H(x)=1，意思是不管是什么元素都放到同一個(gè)下標(biāo)，這個(gè)就是鏈表，也可視為一種哈希表。

大整數(shù)的哈希函數(shù)：
當(dāng)記錄對(duì)象是大整數(shù)的時(shí)候，若再用H(x)=x，數(shù)組的范圍將會(huì)承受不起，所以這時(shí)候要考慮哈希函數(shù)的設(shè)計(jì)問題，又有很多種設(shè)計(jì)方法，最廣泛的一種就是H(x)=x%k，k通常是一個(gè)質(zhì)數(shù)。

一般的哈希函數(shù)：
我們也許會(huì)記錄一些class或者struct之類的東西，這時(shí)候我們可以選取里面的某些關(guān)鍵變量進(jìn)行一種運(yùn)算來確定下標(biāo)。

沖突的處理：
再好的哈希函數(shù)也很難避免沖突，所謂沖突就是說H(a)=H(b)的情況，而開散列的處理方法是在數(shù)組后面掛的是鏈表，這樣沖突的元素可以直接掛在鏈表的末端，而閉散列沒有鏈表，一般是重復(fù)Hn(x)或者往H(x)+a(a=1,2,3..)尋找，這會(huì)使哈希表變得一塌糊涂，而且沖突還可能引發(fā)別的沖突，而且也不便于估計(jì)哈希數(shù)組的范圍，所以鄙人不提倡使用閉散列的組織方式。
順便說一句：好的哈希函數(shù)是盡量減少和平衡沖突，盡量使得每個(gè)鏈的長(zhǎng)度分布得平均，好的哈希函數(shù)的設(shè)計(jì)要靠長(zhǎng)久的經(jīng)驗(yàn)積累，絕非一日之功。

哈希表的本質(zhì)思想：
散列表本質(zhì)思想就是把數(shù)組與鏈表的優(yōu)勢(shì)結(jié)合起來，數(shù)組的訪問復(fù)雜度是O(1)，鏈表的插入復(fù)雜度是O(1)，然而數(shù)組的插入復(fù)雜度和鏈表的訪問復(fù)雜度都比較高，所以就產(chǎn)生了散列表。我們可以把這個(gè)思想運(yùn)用到許多地方，這本是我想說的重點(diǎn)，但鄙人才疏學(xué)淺，不知如何表達(dá)，日后整理一下代碼說明吧。