5.1 散列
定義
理想的散清單是一個包含有關鍵字的具有固定大小的數組。關鍵字就是帶有相關值的字元串。表的大小記作Table-Size，關鍵字被映射到從0到TableSize - 1這個範圍中的某個數。
散列函數
映射
關鍵字被映射到0到TableSize - 1這個範圍中的某個數，并且被放到适當單元中。這個映射就叫做散列函數。
理想散列函數
理想情況下它應該運算簡單并且應該保證任何兩個不同的關鍵字映射到不同的單元。
沖突
當兩個關鍵字映射到同一個值的時候，稱為沖突，需要選擇函數來解決沖突。
5.2 散列函數
key mod size
使用
關鍵字為整數，一般合理方法就是直接傳回“key mod size”。
缺點
關鍵字一般都為字元串
字元ASCII碼的和 mod size
使用
将關鍵字字元串中字元的ASCII碼值加起來。
缺點
char的值最多為127，如果8個字元長，關鍵字ASCII和在0到1016之間，如果size過大，就不能映射到後面。
關鍵字至少三個字元時
使用
缺點
英文不是随機的，三個字母的不同組合中的28%才能被真正用到。
一個好的散列函數
使用
用32代替27，因為32作乘法是移動五位二進制
缺點
如果關鍵字特别長，該散列函數計算起來将會花費過多的時間。
5.3 分離連結法
思想
将散列到同一個值的所有元素保留到一個表中。
缺點
需要指針，給新單元配置設定位址需要時間。
5.4 開放定址法
線性探測法
思想
F(i) = i
缺點
占據的單元容易形成區塊，稱為聚集。當表有多于一半被填滿的話，線性探測法的效率就會很低。
平方探測法
思想
F(i) = i^2，當沖突時，其下一個位置為1、4、9。。。
規律
如果表有一半是空的，并且表的大小是素數，那麼保證總能插入一個新元素。
缺點
會造成二次聚集，雖然排除了一次聚集，但是散列到同一位置上的那些元素将探測相同的備選單元。
雙散列、再散列、可擴散列
思想
将第二個散列函數
散列的應用
符号表
編譯器跟蹤源代碼中聲明的變量
圖論
節點的名字映射到數字，友善查找
二叉搜尋樹和散列
如map和unordered_map，前者紅黑樹實作，後者散清單實作，前者可以排序，後者操作更快
相同點
可以實作Insert和Find
不同點
二叉搜尋樹更友善排序，如找出最小元素等。
二叉搜尋樹的插入和查找操作為O(logN)，而散列為O(1)