iT邦幫忙

0

【資料結構】赫序

赫序

靜態赫序(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)

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

目錄

無目錄


1 則留言

0
OscarCS
iT邦新手 5 級 ‧ 2021-01-10 12:26:26

你這個圖好像是逢甲黃志銘老師上課的ppt 對吧 /images/emoticon/emoticon01.gif

我要留言

立即登入留言