哈希表

哈希表

• 誕生的前提
  • 線上性表、樹等資料結構中，記錄在結構中的相對位置是随機的，和記錄的關鍵字之間不存在确定的關系，是以， 在結構中查找記錄時需要進行一系列和關鍵字的比較。此類的查找方法建立在"比較"的基礎上。
    • 在順序查找時，比較的結果為等于 與 不等于兩種可能；
    • 在折半查找中、二叉排序樹查找和B-樹查找時，比較的結果為小于、等于、和大于三種可能；
    • 查找的效率依賴于查找過程中所進行的比較次數。
• 定義：
  • 理想的情況，希望不經過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系f, 使每個關鍵字和結構中一個唯一的存儲位置相對應。因而在查找時，隻要根據這個對應關系f找到給定值K的像f(K)。若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上，由此，不需要進行比較便可直接取得所查記錄。這個對應關系f為哈希函數，按這個思想建立的表為哈希表。
• 了解：
  • 1、哈希函數是一個映像，是以哈希函數的設定比較靈活，隻要使的任何關鍵字由此所得的哈希函數值都落在表長允許範圍之内即可。
  • 2、對不同的關鍵字可能得到同一哈希位址，即key1不等于key2，但是f(key1)等于f(key2),這種現象稱為沖突。
  • 3、具有相同函數值的關鍵字對該哈希函數來說稱做同義詞。
  • 在一般情況下，沖突隻能盡可能地少，而不能完全避免。因為，哈希函數是從關鍵字集合到位址集合的映像。通常，關鍵字集合比較大，它的元素包括所有可能的關鍵字，而位址集合的元素僅為哈希表中的位址值。假設表長為n,則位址為0到n-1。
  • 在一般情況下，哈希函數是一個壓縮映像，這就不可避免産生沖突。（也就是說，關鍵字集合遠遠大于位址結合）
• 總結：
  • 根據設定的哈希函數H(key)和處理沖突的方法将一組關鍵字映像到一個有限的連續的位址集(區間)上，并以關鍵字在位址集中的“像”作為記錄在表中的存儲位置，這種表稱為哈希表，這一映像的過程稱為散列，所得存儲位置稱哈希位址或散列位址。
• 構造哈希的方法：
  • 1、直接定址法
  • 2、數字分析法
  • 3、平方取中法
  • 4、折疊法
  • 5、除留餘數法
  • 在實際工作中，選擇考慮的因素：
    • 1、 計算哈希函數所需時間(包括硬體指令的因素)；
    • 2、關鍵字的長度；
    • 3、哈希表的大小；
    • 4、關鍵字的分布情況；
    • 5、記錄的查找頻率。
• 處理哈希沖突的方法
  • 1、開放定址法
  • 2、再哈希法
  • 3、鍊位址法
  • 4、建立一個公共溢出區