散清單.md

• • 散清單
  • 散列函數
  • 基于拉鍊法的散清單
  • 基于線性探測法的散清單

散清單

• 目的：如果所有的鍵都是小整數，可以用一個數組來實作無序的符号表，将鍵作為數組的索引而數組中鍵

  i

  處存儲的就是它對應的值。
• 查找算法步驟
  1. 用散列函數将查找的函數轉化為數組的一個索引。理想情況下，不同的減可以轉換為不同的索引值。
  2. 處理碰撞沖突，分為拉鍊法和線性探測法。
• 散清單是算法在時間和空間上的均衡處理方式。

散列函數

• 散列函數特點：散列函數應該易于計算并且能夠均勻分布所有的鍵，即對于任意的鍵，所給出的散列值應得呈随機性。
• 散列函數與鍵的類型有關。
  1. 正整數：正整數散列最常用的方式為除留餘數法。選擇一個

     M

     的素數的數組，對于任意正整數

     k

     ，計算

     k%M

     。如果不是素數，可能無法獲得均勻的散列值。
  2. 浮點數：如果鍵值是0到1之間，可以将鍵值乘以素數M後，四舍五入得到一個0到M-1之間的索引值。但這樣會使鍵的高位起作用更大，低位鍵值不影響散列值。解決辦法是，鍵值用二進制表示後使用除留餘數法。
  3. 字元串：字元串散列同樣使用除留餘數法，将字元串考慮為大整數即可。Java的

     charAt()

     函數能夠傳回一個非負16位整數。如果R是比任何字元都大的整數，相當于，将字元串當做一個N位的R進制值，将它除以M求餘。Horner方法，用N次乘法、加法和取餘來計算一個字元串的散列值。隻要R足夠小，不造成溢出。

     java int hash = 0; for (int i = 0; i < s.length(); i++) hash = (R * hash + s.charAt(i)) % M

  4. 組合鍵：如果鍵的類型包含多個整形變量，我們可以和String類型一樣将他們混合起來。例如，被查找的類型是Date，其中整型域：day(兩位數)、month(兩位數)和year(四位數)，散列值是：

     Java int hash = (((day * R + month) % M) * R + year) % M;

     • 隻要R足夠小不造成溢出，也可以得到0到M-1之間的散列值。同時選取适當素數M值，例如31，來省去括号内的

       %M

       計算。
• Java約定：即散列值的硬性規則。由于每種資料類型都需要相應的散列函數，于是Java讓所有資料類型都繼承了一個能夠傳回32bit整數的hashCode()方法。是以若

  a.equals(b)

  的值為

  ture

  ，那麼對應的hashCode值也應相同，若hashCode值不同，隻能說明看似相同的資料，實則為不同資料類型。但同hashCode值，兩個對象可能不同。
• 将hashCode的傳回值轉化為數組索引：若我們想使用短的索引值，而不是32bit整數的散列值，這裡利用

  hashCode()

  方法和除留餘數法結合，産生0到M-1的整數。

private int hash(Key x){
      return (x.hashCode() & ) % M;
  }
           

• 自定義的hashCode()方法：可以按照将hashCode的傳回值轉化為短整數的方法，進行變換。将對象的每個變量的hashCode()傳回值轉化為32位整數并計算得到散列值。

public class Transaction{
    ...
    private final String who;
    private final Date when;
    private final double amount;

    public int hashCode(){
    int hash = ;
    hash =  * hash + who.hashCode();
    hash =  * hash + when.hashCode();
    hash =  * hash + ((Double) amount).hashCode();
    return hash;
    }
    ...
} 
           

• 軟緩存:如果散列值的計算很耗時，可以将計算的散列值存儲在每個鍵的散列值函數裡，即利用hash變量存儲hashCode()的傳回值。

基于拉鍊法的散清單

基于線性探測法的散清單