為什麼會有哈希表這種數據結構呢？讓我們用一個通俗的例子來理解：
大家一定都查過字典吧，我們知道，《新華字典》是按照讀音排序的，可以理解為一個以讀音為key，按升序排列的資料庫。對於讀音已知的字，可以通過「二分查找法」，很快地查找到要找的字，其時間複雜度為O(log2n)。
但是，對於不知道讀音的字怎麼辦呢？如果使用「順序查找」，一頁一頁地翻字典，假設一本新華字典600頁，每翻查一頁的時間開銷為0.5分鐘，那麼，每查到一個字耗費的時間t的數學期望值E(t) = 600 * 0.5min / 2 =150min，也就是查一個字需要兩個半小時！當然，這是難以接受的！
為了解決這個問題，《新華字典》的編輯們，很快就想出了解決辦法，那就是在字典的前面加入一個「檢字表」，如「四角號碼檢字表」「部首檢字表」等，其特點是以每個字的字形為依據，計算出一個索引值，並映射到對應的頁數。比如「法」字，按四角號碼檢字法，其索引值為34131，再根據這個數值，就可以找到相應的字了。在這種情況下，查找算法的時間複雜度接近於O(1)。換句話說，字典再厚，也不會明顯地影響到查字典的效率了。
好，讓我們回到計算機的世界中來。
哈希表的最大特點，是數據存儲位置（偏移量）和數據記錄的內容相關，存在著一個函數換算關係：
Offset = Hash (Key)
其中，Offset為數據存儲的偏移量，Hash為散列函數(Hash Function)，Content為數據記錄內容的關鍵字(Hash Key)。假設，我們要建立一張EEWorld全球訪問量統計表，每條記錄包含下面的數據結構：
struct access_record_t {
unsigned index_i; /* Index*/
charcountry_name[MAX_COUNTRY_NAME_LEN]; /* 國家/地區名 */
unsigned long long access_count;/* 訪問量 */
};
我們可以用一個一維數組access_record存儲這張表，其中access_record[index_i]為編號為index_i的國家的記錄，也就是說，數據的存儲位置由index_i值唯一確定。例如，中國大陸的index_i值為86，那麼，access_record[86].access_count即為EEWorld在中國大陸地區的訪問量。
然而，我們知道，「China」比起數字86來，明顯更接近自然語言，對於人腦的記憶來說更方便，所以，我們能不能想一個辦法，做一個從國家/地區名到數字索引的映射呢？這就涉及到散列函數(Hash Function)了。
我們說到了散列函數(Hash Function)。它又名哈希函數，是計算機科學中一個重要的課題。什麼是散列函數呢？其實，這個概念並沒有一個嚴格的定義。一般說來，散列函數滿足以下的條件：
1、對輸入值運算，得到一個固定長度的摘要(Hash value)；
2、不同的輸入值可能對應同樣的輸出值；
以下的函數都可以認為是一個散列函數：
f(x) = x mod 16; (1)
f(x) = (x2 + 10) * x; (2)
f(x) = (x | 0×0000FFFF) XOR (x >> 16); (3)
不過，僅僅滿足上面這兩條的函數，作為散列函數，還有不足的地方。我們還希望散列函數滿足下面幾點：
1、散列函數的輸出值儘量接近均勻分布；
2、x的微小變化可以使f(x)發生非常大的變化，即所謂「雪崩效應」(Avalanche effect)；
上面兩點用數學語言表示，就是：
1， 輸出值y的分布函數F(y)=y/m, m為散列函數的最大值。或記為y~U[0, m]
2，|df(x)/dx| >> 1；
從上面兩點，大家看看，前面舉例的三個散列函數，哪個更好呢？對了，是第三個：
f(x) = (x | 0×0000FFFF) XOR (x >> 16);
它很完美地滿足「好的散列函數」的兩個附加條件。
那麼，為什麼散列函數要帶有這兩個附加條件呢？原來，這是為了減少「哈希衝突」（Hashcollision），也就是兩個不同輸入產生了相同輸出值的情況。根據抽屜原理，Hash算法不可能沒有衝突(collision)，但是，由於衝突會造成一些問題，可能會影響到應用Hash函數的某些算法的效率，所以，我們需要儘量避免之。這樣，對Hash算法的選擇，就是很重要的了。密碼學中的著名摘要算法的MD5和SHA1，以及另一種用於字符串摘要計算的Jenkins Hash算法，都是很經典的Hash算法，有興趣的同學可以閱讀參考。
順便延伸閱讀一下，對計算機信息安全感興趣的同學，一定聽說過密碼學家王小雲教授。王教授成名的貢獻，就是發現了大大加速找出MD5和SHA1等Hash算法衝突的方法。譬如，根據「生日攻擊」理論，對於Hash value為160bit的SHA1算法，找出一個Hash衝突需要280次運算，而王小雲找出了一個269次運算就能找出衝突的算法，也就是提高了211=2048倍的效率！所以說，王教授的成果大大動搖了現代密碼學的基礎。
Hash表中，數據存儲的位置，是通過Hash函數計算得到的。那麼，如果兩條數據記錄的Hash值發生衝突，應該怎麼辦呢？
在Hash表的建立時，會發生Hash值衝突的情況。實際上，如果記錄Hash值的範圍多於Hash表的條數，根據抽屜原理，一定會發生衝突。對於衝突的處理，我們一般有這幾種方法：
1，對Hash表中每個Hash值建立一個衝突表，即將衝突的幾個記錄以表的形式存儲在其中；
2，改變規則重新計算一次Hash值；
3，建立一個公用的區域存放衝突的表項；
在工程上，考慮到實現算法的複雜度，方法1用得是最多的。對於方法1，又有兩種不同的實現，一種方法是對每個Hash值，建立一個Hash桶(Bucket)，桶的容量是固定的，也就是只能處理固定次數的衝突，如1048576個Hash桶，每個桶中有4個表項(Entry)，總計4M個表項。另一種方法是，不限制Hash桶的容量，以鍊表形式將衝突的記錄掛接在一個Hash桶中。
這兩種實現各有什麼利弊呢？首先，讓我們看看第一種實現：在這種情況下，由於Hash桶容量的限制，所以，有可能發生Hash表填不滿的情況，也就是，雖然Hash表裡面還有空位，但是新建的表項由於衝突過多，而不能裝入Hash表中。不過，這樣的實現也有其好處，就是查表的最大開銷是可以確定的，因為最多處理的衝突數是確定的，所以算法的時間複雜度為O(1)+O(m)，其中m為Hash桶容量。
而另一種實現，由於Hash桶的容量是無限的，因此，只要沒有超出Hash表的最大容量，就能夠容納新建的表項。但是，一旦發生了Hash衝突嚴重的情況，就會造成Hash桶的鍊表過長，大大降低查找效率。在最壞的情況下，時間複雜度退化為O(n)，其中n為Hash表的總容量。當然，這種情況的概率小之又小，幾乎是可以忽略的。
Hash表的一個應用例子，是在網關(Gateway)中。以網絡防火牆為例，它是根據源IP，目的IP，源埠，目的埠，協議號構成的五元組來標識一條網絡數據流的，並且根據五元組來建立會話表項(session entry)。為了查找便捷，一般都使用Hash表來實現這個會話表，以提高轉發的效率。事實上，對於大量表項的查找，逐項查找是不允許的，一般都使用Hash表來實現。不誇張的說，我們可以說，在你生活的每一天，都免不了同Hash表打交道，比如，查字典。
最後，我想說，數據結構的萬紫千紅中，我獨愛Hash表這一種。