1.散列表

散列技術(shù)是在記錄的存儲位置和它的關(guān)鍵詞之間建立一個確定的對應(yīng)關(guān)系f，使得每個關(guān)鍵字key對應(yīng)一個存儲位置f（key）

• 散列技術(shù)最適合的求解問題是查找與給定值相等的記錄
• 相同關(guān)鍵字可以

2.散列函數(shù)

• 散列函數(shù)的計算時間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵詞比較時間

• 散列地址分布均勻

• 直接定址法 f(key)=a*key+b
  簡單均勻，也不會產(chǎn)生沖突，適合查找表較小且連續(xù)的情況

• 除留余數(shù)法 f(key)=key mod p (p<=m)

• 處理散列沖突的方法

  • 線性探測法
    一旦發(fā)生了沖突，就去尋找下一個空的散列地址，只要散列足夠大，空的散列地址總能找到，并將記錄存入
  • 二次探測法
    雙向?qū)ふ铱赡艿目瘴恢?，同事增加平方運算，不讓關(guān)鍵詞都聚集在某一塊區(qū)域
    還可以使用偽隨機數(shù)，如果設(shè)置隨機種子相同，每次得到的數(shù)列是相同的

• 再散列函數(shù)法
  每當(dāng)發(fā)生散列地址沖突時，就換一個散列函數(shù)計算，總有一個可以把沖突解決掉