所有圖檔來自資料結構與算法基礎（青島大學-王卓）的PPT，順便安利一波，老師的課講的很好，牆裂推薦！
散清單
一、概念
1、散清單的定義
散清單，是根據關鍵碼值而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。
散列函數：H(key) = Addr .
例：
如上，給定散列函數H(key) = key，若給定key = 9，則由散列函數算出位址為 9，也就是9應該存在散清單的9号位置。
2、散清單的相關概念
- 沖突：不同的關鍵碼映射到同一個散列位址。即key1 != key2，但H(key1) == H(key2)。
- 同義詞：具有相同散列函數值的關鍵字。
二、散列函數的構造方法
常用的散列函數：
1、直接定址法
2、除留餘數法
p一般取散清單的長度。
3、其他
- 數字分析法：分析一組資料，比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差别很大，如果用後面的數字來構成散列位址，則沖突的幾率會明顯降低。是以數字分析法就是找出數字的規律，盡可能利用這些資料來構造沖突幾率較低的散列位址。
- 平方取中法：取關鍵字平方後的中間幾位作為散列位址。
- 折疊法：将關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列位址。
- 随機數法：選擇一随機函數，取關鍵字作為随機函數的種子生成随機值作為散列位址，通常用于關鍵字長度不同的場合。
三、處理沖突的方法
1、開放定址法（開位址法）
基本思想：有沖突時就去找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将資料元素存進去。
2、鍊位址法（拉鍊法）
基本思想：相同散列位址的記錄鍊成一個單連結清單，m個散列位址就是m個單連結清單，然後用一個數組将m個單連結清單的表頭指針存儲起來，形成一個動态的結構。
例子：
鍊位址法建立散清單的步驟：
四、散清單的查找
注：ASL，是查找算法的查找成功時的平均查找長度的縮寫，是為确定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值。