0.散列表的定義
<0>定義：根絕鍵(Key)而直接訪問內(nèi)存位置的數(shù)據(jù)結構炭分。也就是說，它通過計算一個關于鍵值的函數(shù)霍比，將所需要查詢的數(shù)據(jù)映射到表中的一個位置來訪問記錄擂红，加快了查找速度。這個映射函數(shù)稱作散列函數(shù)祝谚，存放記錄的數(shù)組稱作散列表宪迟。
<1>一些基本的概念
(1)：若關鍵字為k，則其值存放在f(k)的存儲位置上交惯。由此次泽，不需要比較便可以直接取得所查的記錄。成哥這對應關系f為散列函數(shù)席爽，建立的表為散列表箕憾。
(2)：對不同關鍵子可能得到同意散列地址，即k1 != k2, 但是f(k1) == f(k2)拳昌，這種現(xiàn)象稱為沖突袭异。
(3)：若對于關鍵字集合中的任意一個關鍵字，經(jīng)散列函數(shù)映射到地址集合中任何一個地址的概率是相等的炬藤，則稱此類散列函數(shù)為均勻散列函數(shù)御铃，這使得關鍵字經(jīng)過散列函數(shù)得到的是一個“隨機的地址”碴里，從而減少了沖突。
1.散列表的抽象數(shù)據(jù)類型
類型名稱：符號表(SymbolTable)
數(shù)據(jù)對象集：符號表是"名字(Name)-屬性(Attribute)"對的集合
操作集：
1.SymbolTable InitializeTable(int TableSize);創(chuàng)建一個長度為TableSize的符號表
2.bool IsIn(SymbolTable Table, NameType Name);查找特定名字Name是否在符號表Table中
3.AttributeType Find(SymbolTable Table, NameType Name);獲取Table中指定名字Name對應的屬性
4.SymbolTable Modefy(SymbolTable Table, NameType Name, AttributeType Attr);將Table中指定名字Name的屬性修改為Attr
5.SymbolTable Insert(SymbolTable Table, NameType Name, AttributeType Attr);向Table中插入一個新名字Name及其屬性Attr
6.SymbolTable Delete(SymbolTable Table, NameType Name);從Table中刪除一個名字Name及其屬性
2.散列函數(shù)的構造方法
<0>：一個“好的”散列函數(shù)一般會考慮一下兩個因素：
(1)：計算簡單上真，以便提高運轉(zhuǎn)速度
(2)：關鍵詞對應的地址空間分布均勻咬腋，以盡量減少沖突
<2>：對于數(shù)字關鍵詞的散列函數(shù)構造
(1)：直接定址法：取關鍵詞的某個線性函數(shù)值為散列地址，即h(key) = a*k + b;
(2)：除留余數(shù)法：散列函數(shù)為：h(key) = key % p; 一般的p為TableSize或者質(zhì)數(shù)睡互。
(3)：數(shù)字分析法：分析數(shù)字關鍵字在各位上的變化情況根竿，取比較隨機的位作為散列地址；比如所有號碼的后四位作為地址就珠。
(4)：折疊法：把關機那次分割成位數(shù)相同的幾個部分寇壳，然后疊加：如56793542 ---->542 + 793 + 056 = ---->1391---->391
(5)：平方取中法：如56793542---->56793542 * 56793542 = 322550(641)2905764
<3>：字符關鍵詞的散列函數(shù)構造
(1)：一個簡單的散列函數(shù)----ASCII碼加和法：對字符型關鍵詞key定義散列函數(shù)如下：
(2)：簡單的改進-----前三個字符移位法：h(key) = (key[0] * 27^2 + key[1] * 27 + key[2] * 1) mod TableSize;
(3)：好的散列函數(shù)------移位法：涉及關鍵詞的所有n個字符，并且分布的很好：
<4>：裝填因子：設散列表空間大小位m妻怎，填入表中的元素個數(shù)是n壳炎，則a = n / m稱為列表的裝填因子。
3.沖突處理方法
<1>：常用處理沖突的思路：
(1)：換一個位置：開放地址法
(2)：同一位置的沖突對象組織在一起：鏈地址法
<2>：開放地址法：一旦產(chǎn)生沖突逼侦，就按某種規(guī)則去尋找另一空地址
若發(fā)生了第i次沖突匿辩，試探的下一個地址將增加di，基本公式是：
hi(key) = (h(key) + di) mod TableSize;
di決定了不同的解決沖突的方案：線性探測榛丢、平方探測铲球、雙散列
(1)：線性探測法：以增量序列1，2晰赞，...睬辐，（TableSize - 1）循環(huán)探測下一個存儲地址
(2)：平方探測法----二次探測：以增量序列1^2, - 1^2, 2^2, - 2^2, ... . q^2, - q^2，且
注意：平方探測法存在當HashTable還有空間時溯饵，但是并不能找到的特點。
有定理顯示：如果散列表的長度TableSize是某個4k + 3(k 是正整數(shù))形式的素數(shù)時锨用，平方探測法就能探測到整個散列表空間丰刊。、
Ps：在開放地址散列表中增拥，刪除操作要很小心啄巧。通常只能“懶惰刪除”，即需要增加一個“刪除標記(Deleted)”掌栅，而并不是真正的刪除它秩仆，一遍超找不到時會"斷鏈"。其空間可以在下次插入時重用猾封。
(3)：雙散列探測法(Double Hashing)：di為i*h2(key)澄耍，h2(key)是另外一個散列函數(shù)，探測序列：h2(key), 2h2(key), 3h2(key), ... .
i：對任意的key，h2(key) != 0
ii：探測序列還應該保證所有的散列存儲單元都應該能夠被探測到齐莲，選擇一下形式具有良好的效果：h2(key) = p - (key mod p);其中p痢站，TableSize都是素數(shù)
(4)：再散列
i：當散列表的元素太多時（即裝填因子a太大時），查找效率會下降选酗。實用的最大裝填因子：0.5 <= a <= 0.85
ii：當裝填因子過大時阵难，解決的方法是加倍擴大散列表，這這過程叫做“再散列”
iii：分離鏈式法：將相應位置上沖突的所有關鍵詞存儲在同一個單鏈表中芒填。
4.散列表的性能分析
<1>：平均查找長度(ASL)用來衡量散列表的查找效率：成功呜叫、不成功
<2>：關鍵詞的比較次數(shù)，取決于產(chǎn)生沖突的多少殿衰。影響產(chǎn)生沖突多少有以下三個因素：
(1)：散列函數(shù)是否均勻
(2)：處理沖突的方法
(3)：散列表的裝填因子a
