赫序

靜態赫序(static hashing)

靜態赫序組件

• 赫序表(Hash table，ht):將識別字或鍵值存進固定大小的表格

    赫序表被存於記憶體的連續位置-桶子(buckets)中，每個位置有s個槽(slots) 
  

• 赫序函式(Hashing function) f:決定識別字在赫序表的位置

• 鍵值密度:(key density):n/T

    n:所有鍵值的數量
    T:所有可能鍵值的總數量
  

• 承載密度(loading density) α :n=(sb)

    b:桶子數
    s:桶子槽數
  

• 同義字(synonyms):兩個鍵值i1,i2具有f(i1)=f(i2)特性

溢位和碰撞

• 溢位(overflow):當新的鍵值進入到已滿的桶子

• 碰撞(collision):兩個不同的識別字進入到同一個桶子

    當桶子大小為1時，溢位和碰撞是同時發生的
  

赫序函數的作法

• 直接函數(Direct)

• 減去函數(Subtraction)

• 模數函數(Modulo-Division)

  地址=鍵值取表格大小的餘數

    121267/307=395  …. 2
    =>Hash(121267)=2
  

• 中間平方函數((Mid-square))

  平方後取中間值

    9452*9452=89340304 
    =>Hash(9452)=340
  

• 摺疊函數(Folding)

  取出每一段相加求出求出赫序地址，除了最後一段外，其餘長度全部相等

  • 移位摺疊(Shift folding)
    
  • 邊界摺疊(Folding at the boundaries)
    

• 數字抽取函數(Pseudo Random)

    ex:選擇第 1, 3 及 4 個數字
    379452 =>394
    121267 =>112
    378845 =>388
    160252 =>102
  

• 虛擬亂數函數(Pseudo Random)

  將鍵值設為亂數產生器的種子

    y=(ax+c) mod b   
    y: 地址
    x: 鍵值
    b: 赫序表格大小
    a、c、b 都是質數
  

• 旋轉函數(Rotation)

  通常不是單獨使用

  

• 字串鍵值轉整數函式

  int transform(char *key){
    /* 將任意長度的字串鍵值轉成一個非負自然數 */  
    int number=0;
    while (*key)       number += *key++;
    return number;
    }
  

溢位處理(Overflow Handling)

開放定值法法 (open addressing)

• 線性探測(Linear probing)

  尋找最接近並未使用的桶子，較容易發生群集
  線性探測的平均次數大約是(2-α)/(2-2α) (α是承載密度)

  

• 二次探測(quadratic probing)

  二次探測可降低尋找次數

    順序:h(k)、(h(k)+i2)%b、 (h(k)-i2)%b，1≦ i ≦(b-1)/2
  

• 再赫序(rehashing)

• 隨機探測(rehashing)

    檢查順序:h(k)、(h(k)+s(i))%b、 1≦ i ≦(b-1)。
    s(i)是一個虛擬亂數，其值介於1到b-1
  

鏈結法(Chaining)

• 尋找次數大約在(1+α/2) (α是承載密度)

• 除法赫序函數搭配鏈結法可以產生最佳的效能

• 最差情況還是O(n)

• 同義字放入二元搜尋數中，最差情況的比較次數可減至O(log n)。

動態赫序(dynamic hashing)

靜態赫序會有太小空間不足，太大空間浪費問題，動態赫序可容許動態改變檔案大小

目錄

無目錄