哈希表經常會在面試中問道。這是因為它的確很重要。哈希表有很多應用，比如memcached的核心就是在內存中維護一張大的哈希表。
哈希表是如何實現的？如何解決地址衝突？
便於大家理解，我們倒著講，先講實現後講概念。
哈希表有多種不同的實現方法，下面說的是由數組+鏈表組成的哈希表，也叫鏈地址法。
哈希表
先說點簡單易懂的。
首先分配一個指針數組，數組的每個元素是一個鏈表的頭指針。
每個鏈表稱為一個槽（Slot）。哪個數據應該放入哪個槽中由哈希函數決定，上圖中我們簡單地選取哈希函數h(x) = x % 11，這樣任意數據 都可以映射成0~10之間的一個數，就是槽的編號，將數據放入某個槽的操作就是鏈表的插入操作。
如果每個槽裡至多隻有一個數據，這種情況下search、insert和delete操作的時間複雜度都是O(1)。
如果有多個數據放到同一個槽中，這稱為碰撞（Collision），設計一個好的哈希函數可以把數據比較均勻地分佈到各個槽中，儘量避免碰撞。
如果能把n個數據比較均勻地分佈到m個槽中，每個糟里約有n/m個數據，則search、insert和delete和操作的時間複雜度都是O(n/m)，如果n和m的比是常數，則時間複雜度仍然是O(1)。
一般來說，要處理的數據越多，構造哈希表時分配的槽也應該越多，所以n和m成正比這個假設是成立的。
不同數據結構 的時間複雜度：
概念
哈希表（hash table）也叫散列表。
是根據關鍵碼值(Key value)而直接進行訪問的數據結構。
它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（又叫哈希函數），比如上面例子的h(x) = x % 11，存放記錄的數組叫做散列表。
哈希表的實現主要需要解決兩個問題，哈希函數和衝突解決。
哈希函數 對不同的輸出值得到一個固定長度的消息摘要。
哈希函數 當兩個不同的輸入值對應一個輸出值時，就會產生“碰撞”，這個時候便需要解決衝突。
常見的衝突解決方法有開放定址法，鏈地址法，建立公共溢出區等。實際的哈希表實現中，使用最多的是鏈地址法。
鏈地址法的基本思想是，為每個 Hash 值建立一個單鏈表，當發生衝突時，將記錄插入到鏈表中。 上面剛開始講的就是這種方式。
