前言
散列表（HashTable）又稱為哈希表，是一種快速的數據查找結構，它通常是為一個（組）要記錄的數據設計一個哈希函數H(x)，依據這個函數進行給數據定位，如果是閉散列，那就是直接存到數組的H(x)下標處，如果是開散列，就是存到指針數組H(x)下標的鏈表處。在OI中某些Pascaler為了避開鏈表而采用的閉散列鄙人認為相當糟糕，至於原因會在後面解釋。所以本文只談開散列。
哈希表的組織方式：
我們首先要確定一個哈希函數H(x)，x是要記錄的對象，我們以H(x)來確定對象的記錄的鏈的位置。
還需要一個指針數組來存放每個鏈的頭指針。由於要使用鏈表，所以還要有一個class/struct作為鏈表的基本單位。
哈希表的一般實現：
首先是鏈表的基本元素：
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
};
接下來是構造函數：
hashtable<T>::hahstable()
{
memset(ht,0,sizeof(ht));
}
先略去哈希函數，介紹插入函數：
void hashtable<T>::insert(const T &sr)
{
int loc = hash(sr);
if (ht[loc] == 0)
{
//此處為空，插入一個新鏈表
ht[loc] = new t_node();
ht[loc]-> key = T;
}
else
{
t_node *now = ht[loc];
while (true)
{
if (now->key == sr)
{
//元素已經存在。
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)
{
//遍歷完了整個鏈還是木有。。
return 0;
}
else now = now->next;//看這個鏈的下一個元素
}
}
}
當然可以根據具體情況做各種改動，如果要極限追求效率可以在t_node裡面把key改為指針，然後使用自己編寫的內存分配函數代替new。
最簡單的哈希函數：
其實最簡單的哈希表1就是H(x)=x，意思是若記錄對象是整數，就直接采用這個整數為下標（char類型也可視為整數），這個就是數組，但它也可以看作哈希表。
最簡單的哈希表2就是H(x)=1，意思是不管是什麼元素都放到同一個下標，這個就是鏈表，也可視為一種哈希表。
大整數的哈希函數：
當記錄對象是大整數的時候，若再用H(x)=x，數組的范圍將會承受不起，所以這時候要考慮哈希函數的設計問題，又有很多種設計方法，最廣泛的一種就是H(x)=x%k，k通常是一個質數。
一般的哈希函數：
我們也許會記錄一些class或者struct之類的東西，這時候我們可以選取裡面的某些關鍵變量進行一種運算來確定下標。
沖突的處理：
再好的哈希函數也很難避免沖突，所謂沖突就是說H(a)=H(b)的情況，而開散列的處理方法是在數組後面掛的是鏈表，這樣沖突的元素可以直接掛在鏈表的末端，而閉散列沒有鏈表，一般是重復Hn(x)或者往H(x)+a(a=1,2,3..)尋找，這會使哈希表變得一塌糊塗，而且沖突還可能引發別的沖突，而且也不便於估計哈希數組的范圍，所以鄙人不提倡使用閉散列的組織方式。
順便說一句：好的哈希函數是盡量減少和平衡沖突，盡量使得每個鏈的長度分布得平均，好的哈希函數的設計要靠長久的經驗積累，絕非一日之功。
哈希表的本質思想：
散列表本質思想就是把數組與鏈表的優勢結合起來，數組的訪問復雜度是O(1)，鏈表的插入復雜度是O(1)，然而數組的插入復雜度和鏈表的訪問復雜度都比較高，所以就產生了散列表。我們可以把這個思想運用到許多地方，這本是我想說的重點，但鄙人才疏學淺，不知如何表達，日後整理一下代碼說明吧。
作者“時雨の記-RainCode”
