一、數組和連結清單的弊端
1、對于所有可能的關鍵字集合U，如果用數組來存儲U中的關鍵字，則需要配置設定的存儲單元至少等于U中關鍵字的個數。這種方法的弊端很明顯，實際中U可能很大，計算機的記憶體畢竟有限，用數組去存儲這麼大一個集合不切實際
2、對于連結清單來說也是同樣的道理，對每個關鍵字需要配置設定一個節點來存儲，這樣空間上就會受到限制
3、還有，實際出現的關鍵字集合K有可能遠遠小于U，這樣用數組或連結清單來存儲整個全集U，就會有大部分元素（節點）沒有被使用到，那麼這些空間就是嚴重的浪費
4、最後，數組和連結清單在查找插入删除操作上各有不足。
比如，數組的查找效率非常高，時間複雜度為O(1)，而它的插入和删除操作就非常麻煩
連結清單剛好相反，插入删除友善，查找則需要O(N)的時間複雜度
二、散清單的思想
把全集U的每一個關鍵字通過一個散列函數(Hash Function)h映射到表T{0, 1, ... , m-1}的某個下标，表T{0, 1, ... , m-1}可以簡單的了解為有m個元素的數組 h：U—>{0, 1, ... , m-1}
我們用散清單的一個關鍵目的就是為了節省存儲空間，是以一般情況下m要遠遠小于|U|。
這裡就有一個問題，兩個不同的關鍵字通過h計算可能會得到同一個哈希值(函數值)，例如上圖的k2 != k5，但h(k2) == h(k5)，我們稱這種情形為沖突或碰撞(collision)。
我們選擇散列函數h的時候，要盡可能地減少沖突次數。要做到這一點，就需要散列函數h盡可能的"随機"，即函數值分布盡可能均勻，不要集中在某個區間。
同時也要明白，把一個大集合U硬塞到一個小數組T{0, 1, ... , m-1}，是不可能避免沖突的。
那麼，解決沖突主要有兩種方法，一是連結法，二是開放位址法，這裡着重介紹第一種。
三、通過連結法解決沖突
在連結法中，我們把映射到同一下标的關鍵字存儲在一個連結清單中，數組中儲存指向該連結清單的指針（有可能為空）。
裝載因子α=N / m，N為所有關鍵字的個數，m為數組的元素個數。α表示的是每個連結清單中平均存儲的元素個數。
顯然，連結法的最壞情形是所有關鍵字都映射到一個下标上，這樣所有關鍵字都被存儲到一個連結清單中，其性能退化為和連結清單，還得加上散列函數h的開銷。
是以，連結法的性能依賴于散列函數的選擇，我們要選擇盡量使關鍵字均勻分布在數組的各個元素上的散列函數。
四、散列函數
1、除法散列法
通過取k除以m的餘數，将關鍵字k映射到含有m個元素的數組的一個下标上。
h(k) = k % m
一個不太接近2的整數幂的素數，通常是m的一個較好的選擇
2、乘法散列法
構造散列函數的乘法散列法包含兩個步驟：
①用關鍵字k乘上常數A（0<A<1），并提取kA的小數部分
②用m乘以這個小數部分，再向下取整
h(k) = floor(kA % 1)
A = (√5 -1) / 2 ≈ 0.618是個比較理想的值
開放位址法是