無論是順序檔案的順序查找法和折半查找法、索引檔案查找法以及在B-樹B+樹中進行的查找方法,都是基于關鍵字值比較的查找方法,查找的時間效率主要取決于查找過程中進行的比較次數。
那麼,能否有一種不經過任何關鍵字值的比較或者經過很少次的關鍵字值的比較就能夠達到目的方法?
答案是肯定的,要需要建立記錄的關鍵字與記錄的存儲位置之間的關系,這就是本文要說的散列檔案。
基本概念
1、散列函數
A = H(k)
其中,k 為記錄的關鍵字,H(k)稱為散列函數,或哈希(Hash)函數,或雜湊函數。函數值A為k對應的記錄在檔案中位置。
2、散列沖突
對于不同的關鍵字ki與kj,經過散列得到相同的散列位址,即有
H(ki) = H(kj)
這種現象稱為散列沖突
3、散列檔案
根據構造的散列函數與處理沖突的方法将一組關鍵字映射到一個有限的連續位址集合上,并以關鍵字在該集合中的“象”作為記錄的存儲位置,按照這種方法組織起來檔案稱為散列檔案或哈希檔案 ,或稱雜湊檔案 ;建立檔案的過程稱為哈希造表或者散列,得到的存儲位置稱為散列位址或者雜湊位址。
散列函數的構造
1、原則
1、散列函數的定義域必須包括将要存儲的全部關鍵字;若散清單允許有m個位置時,則函數的值域為[0 … m–1](位址空間);
2、利用散列函數計算出來的位址應能盡可能均勻分布在整個位址空間中;
3、散列函數應該盡可能簡單,應該在較短的時間内計算出結果;
2、建立散列檔案的步驟
1、确定散列的位址空間(位址範圍);
2、構造合适的散列函數;
3、選擇處理沖突的方法。
3、散列函數的構造方法
1、 直接定址法
2、 數字分析法
3、 平方取中法
4、疊加法
5、基數轉換法
6、除留餘數法
除留餘數發如下:
H(k) = k MOD p
其中,若m為位址範圍大小(或稱表長),則p可為小于等于m的素數。
沖突的處理方法
所謂處理沖突,是在發生沖突時,為沖突的元素找到另一個散列位址以存放該元素。如果找到的位址仍然發生沖突,則繼續為發生沖突的這個元素尋找另一個位址,直到不再發生沖突。
沖突的處理方法有如下幾種:
開放位址法(閑散列方法)
開放位址法有如下特點:
1、“線性探測法”容易産生元素“聚集”的問題。
2、“二次探測法”可以較好地避免元素“聚集”的問題,但不能探測到表中的所有元素(至
少可以探測到表中的一半元素)。
3、隻能對表項進行邏輯删除(如做删除标記),而不能進行實體删除。使得表面上看起來很滿的散清單實際上存在許多未用位置。
聚集指的是散列位址不同的元素争奪同一個後繼散列位址的現象。
産生聚集的主要原因如下:
1、散列函數選擇得不合适;
2、負載因子過大;
負載因子是衡量散清單的飽滿程度的名額,計算公式如下:
一般情況下,a<1,a越大,散清單越滿。
再散列法
Di = Hi(k) , i=1, 2, 3, …
其中,Di為散列位址,Hi(k)為不同的散列函數,
即在散列的基礎上再散列一次。
鍊位址法
将所有散列位址相同的記錄連結成一個線性連結清單。若散列範圍為[0…m-1],則定義指針數組bucket[0…m-1]分别存放m個連結清單的頭指針,如下圖:
該方法的特點如下:
1、處理沖突簡單,不會産生元素“聚集”現象,平均查找長度較小 ;
2、适合建立散清單之前難以确定表長的情況 ;