第5章 散列表（雜湊表）

散列表

散列表（Hash table，也叫雜湊表）【也被稱：雜湊對映、對映、字典和關聯陣列】，是根據鍵（key）而直接訪問在記憶體儲存位置的資料結構。它透過計算一個關於鍵值的函式，將所需查詢的資料對映到表中一個位置來訪問記錄，這加快了查詢速度。這個對映函式稱為雜湊函式，存放記錄的陣列稱為散列表。

散列表應用的例子有很多，經常被用在大海撈針式的查詢。

案例1，為了查詢電話簿中某人的號碼，可以建立一個按照人名首字母順序排列的表（即建立人名x到首字母F（x）的一個函式關係），在首字母為W的表中查詢“王”姓的電話號碼，顯然比直接查詢就要快得多。這裡使用人名作為關鍵字，“取首字母”是這個例子中雜湊函式的函式法則F（），存放首字母的表對應散列表。關鍵字和函式法則理論上可以任意確定。

案例2：你再訪問像http：//www。baidu。com這樣的網站時，計算機必須將http：//www。baidu。com轉換為IP地址。無論你訪問哪個網址，其網址必須轉換為IP地址。其實這就是將網址對映為IP地址，可以用散列表實現。

案例3：記名投票管理中，每人只能投一票，利用散列表可以避免重複投票。有人來投票，你問他叫啥，並將他的姓名與投票者名單比對，如果名字在名單中，就將他拒之門外；否則將他的姓名新增到名單當中，並讓他投票。

案例4：將散列表應用於網頁快取。

基本概念

* 若關鍵字為k，則其值存放在f（k）的儲存位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為雜湊函式，按這個思想建立的表為散列表。

* 對不同的關鍵字可能得到同一雜湊地址，即k1≠k2，而f（k1）=f（k2），這種現象稱為衝突（英語：Collision）。具有相同函式值的關鍵字對該雜湊函式來說稱做同義詞。綜上所述，根據雜湊函式f（k）和處理衝突的方法將一組關鍵字對映到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的“像”作為記錄在表中的儲存位置，這種表便稱為散列表，這一對映過程稱為雜湊造表或雜湊，所得的儲存位置稱雜湊地址。

* 若對於關鍵字集合中的任一個關鍵字，經雜湊函式映象到地址集合中任何一個地址的機率是相等的，則稱此類雜湊函式為均勻雜湊函式（Uniform Hash function），這就是使關鍵字經過雜湊函式得到一個“隨機的地址”，從而減少衝突。

散列表的填裝因子 = 散列表包含的元素數 / 位置總數；填裝因子度量的是散列表中有多少位置是空的；填裝因子越低，發生衝突的可能性越小，散列表的效能越高。經驗規則：一旦填裝因子大於0。7，就調整掃列表的長度。

雜湊函式

雜湊函式是這樣一種函式，即無論你給它什麼資料，它都還給你一個數字；

雜湊函式總是將同樣的輸入對映到相同的索引；

雜湊函式將不同的輸入對映到不同的索引；

雜湊函式知道陣列有多大，只返回有效的索引。

練習