為了解決動態(tài)查找的問題
散列查找法的兩項(xiàng)基本工作：

• 計(jì)算位置：構(gòu)造散列函數(shù)確定關(guān)鍵詞存儲位置
• 解決沖突：應(yīng)用某種策略，解決多個(gè)關(guān)鍵詞位置相同的問題
  時(shí)間復(fù)雜度幾乎為O(1)

散列表（哈希表）

• 類型名稱：符號表（SymbolTable）
• 數(shù)據(jù)對象集：符號表是”名字(Name)-屬性(Attribute)“對的集合
• 裝填因子：散列表大小/填入散列表元素的個(gè)數(shù)

散列函數(shù)

數(shù)字關(guān)鍵詞的散列函數(shù)構(gòu)造

• 直接定址法
  h(key) = a * key + b
• 除留余數(shù)法
  h(key) = key % p（p = Tablesize，一般取素?cái)?shù)）
• 數(shù)字分析法
  取比較隨機(jī)的幾位數(shù)字組成散列地址
• 折疊法
  把關(guān)鍵詞分成位數(shù)相同的幾個(gè)部分，然后疊加
• 平方取中法
  大數(shù)平方，取中間幾位作為地址

字符關(guān)鍵詞的散列函數(shù)構(gòu)造

• ASCII碼加和法
  h(key) = 每個(gè)字符ASCII碼加和 mode Tablesize
• 前三個(gè)字符移位法
  h(key) = (key[0] * 27 ^ 2 + key[1] * 27 ^ 1 + key[2] * 27 ^ 0)mod Tablesize
• 移位法

散列表查找性能分析

• 成功平均查找長度（ASLs）
• 不成功平均查找長度（ASLu）

影響散列表性能因素

• 散列函數(shù)是否均勻
• 處理沖突的方法
• 散列表的裝填因子α

再散列

• 當(dāng)裝填因子過大，查找效率下降，裝填因子最好在0.5-0.85之間
• 解決的方法是加倍擴(kuò)大散列表，即再散列（Rehashing）

處理沖突的方法

開放地址法（Open Addressing）

hi(key) = (h(key) + di) mod Tablesize

• 線性探測 di = i
• 平方探測 di = ±i^2（如果表的大小設(shè)計(jì)為4k+3形式的素?cái)?shù)，平方探測法可以探測到整個(gè)散列表空間）
• 雙散列 di = i*h2(key)

分離鏈接法

• 沖突的關(guān)鍵詞存放在同一個(gè)單鏈表中