Chapter 10 赫序函數 資料結構導論 - C語言實作.

Presentation on theme: "Chapter 10 赫序函數 資料結構導論 - C語言實作."— Presentation transcript:

1 Chapter 10 赫序函數 資料結構導論 - C語言實作

2 10.1 前言 要搜尋檔案中的特定資料，我們可以透過第九章所介紹的搜尋法，根據給定的鍵值來找尋所要的紀錄。
基本上，我們發現搜尋的過程中會利用到檔案中其他紀錄的鍵值來決定下一次搜尋的方向。 另外一種搜尋檔案中特定資料的方法則是透過赫序函數(Hashing Function)來搜尋資料。 資料結構導論 - C語言實作

3 10.1 前言 赫序搜尋法是透過一個數學函數來轉換 (或計算)一個鍵值所對應的位址。 由於這樣的做法可以直接地找到鍵值所對應的的記憶體位址。
不需要透過循序地搜尋所有的鍵值。 檔案中的個別紀錄也無須事先依鍵值排好序。 一個赫序函數 資料結構導論 - C語言實作

4 10.1 前言 在赫序函數轉換過程中，當一個位址同時被兩個或兩個以上的鍵值所對應時，我們稱此現象為碰撞(Collision)。
通常碰撞問題的解決方法可分成兩大類。第一類屬於「事先預防」的做法，另一類屬於「事後補救」的做法。 資料結構導論 - C語言實作

5 10.2 傳統的赫序函數 10.2.1利用除法計算之赫序函數 給定一個含有 m 個位址的位址空間(Address Space)，地址編號分別為 1，2，…，m與鍵值 k。 利用除法計算之赫序函數h如下所示： h(k)=(k mod m)＋1。 我們發現當m為偶數時較易發生碰撞的情況。 資料結構導論 - C語言實作

6 利用除法計算之赫序函數 給定鍵值集合 k =｛15, 27，51，80，95｝。令m=7，則利用 h(k)=(k mod 7)＋1，可以將鍵值34，58，72，95分別存放到第2，第7，第3，第4及第5號位址上。 h(15)=(15 mod 7)+1=2, h(27)=(27 mod 7)+1=7, h(51)=(51 mod 7)+1=3, h(80)=(80 mod 7)+1=4, h(88)=(88 mod 7)+1=5. 資料結構導論 - C語言實作

7 利用乘法計算之赫序函數 給定一個含有 m 個位址的位址空間(Address Space)，地址編號分別為 1，2，…，m與鍵值 k。 利用乘法(Multiplication Hashing)計算之赫序函數h如下所示： h(k)= ＋1 其中c是一個事先選定的常數而且 0＜c＜1。 此外ck mod 1代表 ck 這個乘法運算結果小數部份之值。 資料結構導論 - C語言實作

8 10.2.2 利用乘法計算之赫序函數 假設鍵值k =86，而且c=0.6。另外m=7。 h(86)= +1 = +1 = 5
利用乘法計算之赫序函數 假設鍵值k =86，而且c=0.6。另外m=7。 h(86)= = = 5 資料結構導論 - C語言實作

9 利用平方取中法之赫序函數 給定一個含有 m 個位址的位址空間(Address Space)，m＝99…9代表位址空間的大小，其中 m 為 t 位數的整數。 在利用平方取中法(Midsquare Method)之赫序函數h中會採用鍵值k的平方 k2 之中間t位數之值當作鍵值 k 所對應的位址。 資料結構導論 - C語言實作

10 10.2.3 利用平方取中法之赫序函數 給定鍵值 k1=34567與k2=1234。假設m=9999，我們知道 m 為4位數正整數
利用平方取中法之赫序函數 給定鍵值 k1=34567與k2=1234。假設m=9999，我們知道 m 為4位數正整數 h(k1) = k12 取中間4位數 = 取中間4位數 = 4877。 h(k2) = k22 取中間4位數 = 取中間4位數 = 2275。 資料結構導論 - C語言實作

11 10.2.4 利用疊合法之赫序函數 給定一個含有 m 個位址的位址空間(Address Space)與鍵值k。
利用疊合法之赫序函數 給定一個含有 m 個位址的位址空間(Address Space)與鍵值k。 利用疊合法(Folding Method)之赫序函數是將鍵值 k 切割成若干長度相等的區塊，將之相加，再 mod m(意即除以m取餘數)而得。 資料結構導論 - C語言實作

12 10.2.4 利用疊合法之赫序函數 假設鍵值 k=286267536，且位址空間大小 m=1000。
利用疊合法之赫序函數 假設鍵值 k= ，且位址空間大小 m=1000。 首先將鍵值 k 切成單位長度為3的3個區塊：286，267，536 接著將三個區段的值相加： = 1089。 h(k) = 1089 mod 1000 = 89。 為了減少利用疊合法計算的赫序函數之碰撞機率，可以將所切割的各區塊，在相加之前先將奇數號的區塊翻轉過來，再進行加總。 資料結構導論 - C語言實作

13 10.2.4 利用疊合法之赫序函數 設鍵值 k=286267536，且 m=1000。
利用疊合法之赫序函數 設鍵值 k= ，且 m=1000。 首先將鍵值 k 切成單位長度為3的3個區塊：286，267，536 將奇數號的區塊翻轉過來後的結果：682，267，635 接著將三個區段的值相加： = 1584。 h(k) = 1584 mod 1000 = 584。 資料結構導論 - C語言實作

14 利用基數法之赫序函數 利用基數法之赫序函數主要是將給定基數數系p的鍵值k視為某一基數數系q的數值，再將該數值轉換回原本鍵值所在的基數數系q。 接著，取出轉換回原本鍵值所在的基數數系p之數值的某些位數之數值當做赫序函數的運算結果。 也就是說在基數法之赫序函數運作中，我們必須先設定兩個互質的數值，分別是原本鍵值的進制系統p以及另一個轉換用的進制系統q，其中 q＞p，且 q 與 p 互質。 資料結構導論 - C語言實作

15 10.2.5 利用基數法之赫序函數 假設基數法計算之赫序函數所使用的基數p與q分別為10與11，
利用基數法之赫序函數 假設基數法計算之赫序函數所使用的基數p與q分別為10與11， 此外轉換過的數值之後4位數會被取出當成赫序函數的運算結果。 給定鍵值k=(530478)10，我們把它當成是11進制的值然後再將其轉換成10進制的另一個數值。 資料結構導論 - C語言實作

16 10.2.5 利用基數法之赫序函數 (530478)11 轉換十進制的處理程序如下所列：
利用基數法之赫序函數 (530478)11 轉換十進制的處理程序如下所列： (530478)11=5*115+3*114+4*112+7*111＋8*110 = (849747)10。 接著取後4位數當作赫序函數值；也就是說 h(k) = 9747。 資料結構導論 - C語言實作

17 利用位數分析法之赫序函數 利用位數分析法(Digit Analysis)之赫序函數主要透過比較十進位制的各個鍵值之不同位數，採用分佈較均勻的若干個位數值做為每一個鍵值的赫序函數值。 資料結構導論 - C語言實作

18 10.2.6 利用位數分析法之赫序函數 假設有五位學生的學號(學號是由6個位數的數值 d6d5d4d3d2d1 所構成)，
利用位數分析法之赫序函數 假設有五位學生的學號(學號是由6個位數的數值 d6d5d4d3d2d1 所構成)， 他們的學號分別是： SID1＝914331， SID2＝914145， SID3＝913224， SID4＝905310， SID5＝921307， 假設位址空間大小 m＝100，也就是說我們只能挑選兩位數當做每一個學號的赫序函數值，因為位址的編號是從0到99。 資料結構導論 - C語言實作

19 10.2.6 利用位數分析法之赫序函數 利用統計分析的方式來進行位數分析必須針對所有學號在個別位數出現的數值從0到9的個數加以分析。
利用位數分析法之赫序函數 利用統計分析的方式來進行位數分析必須針對所有學號在個別位數出現的數值從0到9的個數加以分析。 發現第一個位數D1出現0的次數是1，因為SID4＝905310的第一位數是0。 第一個位數D1出現1的次數是1，因為SID1＝914331的第一位數是1。 資料結構導論 - C語言實作

20 利用位數分析法之赫序函數 資料結構導論 - C語言實作

21 利用位數分析法之赫序函數 接著我們將介紹一個用以評估個別位數的數值分佈程度的方法。令數字的分佈曲度(Skewness) SNi＝ ，其中 aij 表示在第i位數 Di 出現數值是 j 的個數。 SN1＝│1-1│＋│1-1│＋│0-1│＋│0-1│＋│1-1│＋ │1-1│＋│0-1│＋│1-1│＋│0-1│＋│0-1│＝5。 SN2＝│1-1│＋│1-1│＋│1-1│＋│1-1│＋│1-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＝5。 SN3＝│0-1│＋│1-1│＋│1-1│＋│3-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＝9。 資料結構導論 - C語言實作

22 10.2.6 利用位數分析法之赫序函數 在數字的分佈曲度的評估中，SKi之值愈小者表示Di 的分佈愈均勻。
利用位數分析法之赫序函數 SN4＝│0-1│＋│1-1│＋│0-1│＋│1-1│＋│2-1│＋│1-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＝7。 SN5＝│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│0-1│＋│5-1│＝13。 也就是說我們可以得到SN1＝SN2＝5，SN3＝9，SN4＝7，SN5＝9，SN6＝13的結果。 在數字的分佈曲度的評估中，SKi之值愈小者表示Di 的分佈愈均勻。 我們發現分佈最均勻的兩個位數分別是第一位數與第二位數。 所以我們會選擇每一個鍵值的(D2，D1) 當做赫序函數值。也就是說 h(SID1)＝31，h(SID2)＝45，h(SID3)＝24，h(SID4)＝10且(SID5)＝07。 資料結構導論 - C語言實作

23 關於碰撞的因應之道 亂數法 當赫序函數的兩個鍵值發生碰撞時，可以將產生碰撞的鍵值以亂數(Random Method)赫序函數再重新計算一個新址。 假設亂數種子 i = (i＋c) mod m，假設 i 為亂數產生程式的種子(亦即起始值)，而 c 與 m 互質。 令 c＝5，m＝11，且一開始的時候，i＝3，則產生的亂數為 8，2，7，1，6，0，5，10，4，9，3。 算出的亂數值可以依序的送入random(i)函數來計算出h(k)＋random(i)的記憶體空間位址。 資料結構導論 - C語言實作

24 循序定址法 赫序函數的兩個鍵值ki與kj發生對應到相同記憶體空間，也就是說h(ki)＝α＝h(kj)，表示鍵值 ki 與kj 發生碰撞。 最簡單的做法是沿著位址 α 的下面，循序地尋找一個空的位置來讓 kj 棲身。 這樣的做法我們稱為循序定址法(Linear Probing)或是線性開放定址法(Linear Open Addressing)。 資料結構導論 - C語言實作

25 10.3.2 循序定址法 基本上循序定址法的規則可以下列公式表示： (h(k)+s) mod m，0≦ s ≦m-1。
循序定址法 基本上循序定址法的規則可以下列公式表示： (h(k)+s) mod m，0≦ s ≦m-1。 圖10.2中灰色填滿的位址表示已經有鍵值資料儲存在內。則透過 (h(k)＋2) mod 10的循序定址方式會永遠找不到空的位置來放 k。 圖10.2 不合適的循序定址法之範例 資料結構導論 - C語言實作

26 10.3.3 二次式探勘定址法 二次式探勘定址法可以寫成： (h(k)＋s2) mod m 或 (h(k)-s2) mod m，
二次式探勘定址法 二次式探勘定址法可以寫成： (h(k)＋s2) mod m 或 (h(k)-s2) mod m， 其中 1≦ s ≦ (m-1)/2。 資料結構導論 - C語言實作

27 圖10.3 利用串列法解決ki，kj，kr，ks碰撞之問題
串列法 在赫序函數產生碰撞時，我們可以利用一塊可用儲存空間 (Free Storage Area) 做為碰撞之鍵值的儲存空間。 當有碰撞產生時，就將這個產生碰撞的鍵值放到可用儲存空間的空位置裡。這樣的做法稱作串列法(List Method)。 圖10.3 利用串列法解決ki，kj，kr，ks碰撞之問題 資料結構導論 - C語言實作

28 10.3.5 重複赫序法 當赫序函數的兩個鍵值發生碰撞現象產生時，我們可以利用事先準備好的其它赫序函數計算出不同的位址。
重複赫序法 當赫序函數的兩個鍵值發生碰撞現象產生時，我們可以利用事先準備好的其它赫序函數計算出不同的位址。 若還是發生碰撞狀況，則再找出另一個赫序函數來計算。也就是說，我們需要事先準備t個赫序函數 h1，h2，…，ht 這樣的處理方式我們稱作重複赫序法(Rehashing Method)。 資料結構導論 - C語言實作

29 10.4 赫序函數之建議與評估 一般而言，我們在選擇一個赫序函數必須要考慮下列幾個因素 靜態資料或動態資料 資料存取的頻率 赫序函數的複雜度
10.4 赫序函數之建議與評估 一般而言，我們在選擇一個赫序函數必須要考慮下列幾個因素 靜態資料或動態資料 資料存取的頻率 赫序函數的複雜度 鍵值長度 鍵值基數 (Radix) 位址空間的大小 資料結構導論 - C語言實作

30 10.5 動態赫序函數 10.5.1 Larson的動態赫序函數 Larson在1978年提出了動態赫序函數的檔案結構。
10.5 動態赫序函數 Larson的動態赫序函數 Larson在1978年提出了動態赫序函數的檔案結構。 在Larson所提出的方法中利用了串列樹(Link-Tree)的架構，建構了一個稱之為索引的輔助區域，用來偵測當檔案有新記錄加入時，其所指定儲存的區段當時是否已經放滿了記錄？若是，則需將該區段一分為二。 至於這些需要儲存的記錄，應被放置於那一個區段？則會透過動態赫序函數來根據紀錄的主鍵值加以決定。 資料結構導論 - C語言實作

31 10.5 動態赫序函數 圖10.5 一個動態赫序函數之例子 資料結構導論 - C語言實作

32 10.5 動態赫序函數 1 圖10.6 加入 "17" 之結果 資料結構導論 - C語言實作

33 10.5 動態赫序函數 1 1 圖10.7 從圖10.6中刪除 "9" 後的結果 資料結構導論 - C語言實作

34 10.5 動態赫序函數 圖10.8 從圖10.7中合併區段0與區段2 後的結果 資料結構導論 - C語言實作

35 10.5.2 延展赫序函數 在一九七九年Fagin、Nievergelt和Pippenger提出的延展赫序函數。
延展赫序函數 在一九七九年Fagin、Nievergelt和Pippenger提出的延展赫序函數。 在延展赫序函數中利用一個索引來紀錄使用的區塊個數。 在索引結構中若所含的深度(Depth)數為d，則整個區域將有2d個節點，而每一個節點均儲存一個區段位址。 當加入或刪除紀錄時透過索引中的節點來決定紀錄所在的區塊位置。 圖10.5 一個動態赫序函數之例子 資料結構導論 - C語言實作

36 延展赫序函數 圖10.8 一個延展赫序函數 資料結構導論 - C語言實作

37 延展赫序函數 圖10.9 區段0分裂後的結果 資料結構導論 - C語言實作

38 延展赫序函數 圖 從圖10.9中加入鍵值7的紀錄後的結果 資料結構導論 - C語言實作

39 延展赫序函數 圖 從圖10.10中加入鍵值27的紀錄後的結果 資料結構導論 - C語言實作