第10章 資料搜尋（Searching） 10-1 搜尋的基礎 10-2 循序搜尋法 – 未排序資料 10-3 已排序資料的搜尋法

Presentation on theme: "第10章 資料搜尋（Searching） 10-1 搜尋的基礎 10-2 循序搜尋法 – 未排序資料 10-3 已排序資料的搜尋法"— Presentation transcript:

1 第10章 資料搜尋（Searching） 10-1 搜尋的基礎 10-2 循序搜尋法 – 未排序資料 10-3 已排序資料的搜尋法
10-4 雜湊搜尋法 10-5 雜湊函數的碰撞問題

2 10-1 搜尋的基礎-說明 「搜尋」（Searching）是在資料中找尋特定的值，這個值稱為「鍵值」（Key）。例如：在電話簿以姓名找尋朋友電話號碼，姓名就是鍵值，或在書局以書號的鍵值找尋喜愛的書。 搜尋的目的是為了確定資料中是否存在與鍵值相同的資料。

3 10-1 搜尋的基礎-範例 搜尋的目的是為了確定資料中是否存在與鍵值相同的資料。例如：學生連絡資料的記錄，如下圖所示：
在上述記錄欄位的【學號】是鍵值，例如：搜尋學號為S003的學生，經搜尋找到學生郭富成，因為有此鍵值的學號，接著就可以找到學生姓名和電話號碼，然後與學生連絡。

4 10-1 搜尋的基礎-種類 資料搜尋方法依照搜尋資料可以分成兩種，如下所示：
沒有排序的資料：針對沒有排序的資料執行搜尋，需要從資料的第1個元素開始比較，從頭到尾以確認資料是否存在，例如：線性搜尋法。 已經排序的資料：搜尋不需要從頭開始一個個比較。例如：在電話簿找電話，相信沒有人是從電話簿的第一頁開始找，而是直接從姓名出現的頁數開始找，這是因為電話簿已經依照姓名排序好。例如：二元搜尋法和插補搜尋法。

5 10-2 循序搜尋法 – 未排序資料(說明) 「循序搜尋法」（Sequential Search）是從循序結構的第1個元素開始走訪整個結構，以陣列來說，就是陣列走訪，從頭開始一個一個比較元素是否是搜尋值，因為需要走訪整個陣列，陣列資料是否已經排序就沒有什麼關係。

6 10-2 循序搜尋法 – 未排序資料(範例) 例如：在整數陣列data[]搜尋整數90的鍵值，程式需要從陣列索引值0開始比較，在經過索引值1、2和3後，才在索引值4找到整數90，一共比較5次。 同理，如果搜尋整數4的鍵值，需要從索引值0一直找到10，才能夠確定鍵值是否存在，結果比較11次發現鍵值4不存在。

7 10-2 循序搜尋法 – 未排序資料(執行效率) 如果元素個數為n，循序搜尋法的執行效率是與元素個數成正比的O(n)。

8 10-3 已排序資料的搜尋法 二元搜尋法 插補搜尋法

9 10-3-1 二元搜尋法-說明 「二元搜尋法」（Binary Search）是一種分割資料的搜尋方法，搜尋資料需要是已經排序好的資料。
二元搜尋法的操作是先檢查排序資料的中間元素，如果與鍵值相等就是找到，如果小於鍵值，表示資料位在前半段，否則位在後半段。然後繼續分割成二段資料重覆上述操作，直到找到或已經沒有資料可以分割為止。

10 二元搜尋法-方法 例如：陣列的上下範圍分別是low和high，中間元素的索引值是(low + high)/2。在執行二元搜尋時的比較，可以分成三種情況，如下所示： 搜尋鍵值小於陣列的中間元素：鍵值在資料陣列的前半部。 搜尋鍵值大於陣列的中間元素：鍵值在資料陣列的後半部。 搜尋鍵值等於陣列的中間元素：找到搜尋的鍵值。

11 二元搜尋法-過程1 在已經排序好的整數陣列data[]找尋整數81的鍵值，第一步和陣列中間元素索引值(0+10)/2 = 5的值33比較，因為81大於33，所以搜尋陣列的後半段，如下圖所示：

12 二元搜尋法-過程2 搜尋範圍已經縮小剩下後半段，中間元素索引值(6+10)/2 = 8，其值為74。因為81仍然大於74，所以繼續搜尋後半段，如下圖所示： 再度計算中間元素索引值(9+10)/2 = 9，找到搜尋值81。

13 二元搜尋法-搜尋過程 整個二元搜尋過程可以使用陣列索引值繪出執行過程的二元搜尋樹，節點內容為陣列索引值，如下圖所示：

14 二元搜尋法-執行效率 二元搜尋法的平均和最差的執行效率很容易算出，因為每次都分為二半，其執行效率為O(Log n)。

15 插補搜尋法-說明 循序和二元搜尋法都不是在電話簿或百科全書查閱資料的方法，因為我們通常是依照姓名或分類直接翻至相關章節或頁碼的前後，然後才決定是從前端、中間或後端開始搜尋，這種搜尋法稱為「插補搜尋法」（Interpolation Search）。

16 插補搜尋法-原理 插補搜尋法以資料分佈情況計算出可能位置的索引值，來縮小搜尋的範圍，而不像二元搜尋法固定分割一半來縮小範圍。例如：一個直角三角形，如下圖所示：

17 插補搜尋法-索引公式 將圖形標上座標，並且假設三角形是一個分佈平均的資料，我們可以推導出插補搜尋法計算可能位置的索引值公式，如下圖所示：

18 插補搜尋法-執行效率 插補搜尋法的執行效率是： O(Log(Log n))。

19 10-4 雜湊搜尋法 雜湊搜尋法的基礎 雜湊函數

20 雜湊搜尋法的基礎-說明 對於龐大資料的搜尋而言，搜尋效率的增進仍然無法滿足實際的需求，在實作上，我們需要一種更好的搜尋方法，這就是「雜湊搜尋法」（Hashing Search）。 雜湊搜尋法的原理是儘量減少搜尋範圍到只有一個，換句話說，搜尋操作只需檢查一個位置，就可以回答找到或沒有找到。

21 雜湊搜尋法的基礎-範例1 例如：一個結構陣列data[] 的編號欄位是鍵值，其範圍從1到9，如果使用循序搜尋法搜尋鍵值7的【張無忌】記錄，一共需要經過4次比較才能找到，如下圖所示：

22 雜湊搜尋法的基礎-範例2 陣列hashTable[]是預先建立好的索引資料。搜尋鍵值只需檢查指標陣列索引值的內容是否為-1，搜尋範圍縮小到只有1個位置，這個指標陣列就是「雜湊表」（Hash Tables），如下圖所示：

23 雜湊函數-說明 雜湊搜尋法的資料搜尋是透過雜湊表來執行搜尋，所以雜湊搜尋法最主要的工作是建立「雜湊表」（Hashing Tables），而建立雜湊表的方式則是由使用的雜湊函數而定，雜湊函數是一種數學運算，其目的是減少資料範圍，將搜尋鍵值轉換成索引位置，如下圖所示：

24 10-4-2 雜湊函數-除法(說明) 除法（Division Method）
除法的雜湊函數是將資料除以常數，然後使用餘數作為索引位置，其公式如下所示： 索引位置 = 鍵值 mod M 上述M是除數，可以取得鍵值除以此除數的餘數。

25 10-4-2 雜湊函數-除法(範例) 例如：搜尋的鍵值清單，如下所示：
11, 15, 49, 78, 53, 26, 22 上述鍵值範圍是11~78，所以一共需要68個元素才能建立雜湊表，現在使用10餘數運算的雜湊函數，其結果如下所示： 1, 5, 9, 8, 3, 6, 2

26 雜湊函數-除法(圖例) 經過轉換後，只需值1~9的範圍就可以建立雜湊表，如下圖所示：

27 10-4-2 雜湊函數-中間平方法 中間平方法（Mid-Square Method）
中間平方法是將鍵值乘以自己或某個常數，然後取中間幾位數字做為索引位置。例如：取中間三位數的中間平方法，如下所示： (136)2 = →120 (2642)2 = →016 上述中間平方法只取中間三個數字來作為雜湊表的索引位置。

28 10-4-2 雜湊函數-數位分析法1 數位分析法（Digit Analysis Method）
數位分析法適用在數值鍵值的雜湊搜尋。例如：電話號碼資料，如下所示： 上述電話號碼資料如果作為雜湊表的索引位置，需要的記憶體空間將是一個天文數字。如果現在可用的記憶體空間只有1000個，我們需要找出一個縮小索引位置的方法。

29 雜湊函數-數位分析法2 電話號碼的區域號碼都相同，所以不用考慮，接著三個號碼的變化也不大，可以省略。最後四位數字只保留三位數，因為這幾支電話號碼中，最後四碼的第二位數多半是5，所以也將之省略，最後得到的轉換規則，如下表所示：

30 10-4-2 雜湊函數-折疊法1 折疊法（Folding Method）
折疊法是將鍵值分成幾個部分，除了最後一個部分外，其餘部分都是相同長度。例如：將一個長整數 分成5個部分，如下所示：

31 10-4-2 雜湊函數-折疊法2 折疊方式有很多種，常用的方法，如下所示：
位移折疊法（Shift Folding）：在分成幾個部分後，直接靠左或靠右相加後，就是索引位置，如下所示：

32 雜湊函數-折疊法3 邊界折疊法（Folding at the Boundaries）：在分成幾個部分後，並不是分割邊界，而是將左邊邊界折起來後相加，所以P2和P4是反轉資料，如下所示：

33 10-5 雜湊函數的碰撞問題 線性探測法 重雜湊法 鏈結法

34 10-5 雜湊函數的碰撞問題-說明 雜湊函數是使用數學運算來處理鍵值，以便計算出雜湊表的索引位置，不過任何雜湊函數都不能保證鍵值在執行運算後，得到的索引位置是唯一。 例如：數字14、24和34除以10的餘數都是4，這種將數個鍵值轉換成同一個索引位置的情況稱為「碰撞」（Collisions），換句話說，在同一個索引位置，就不知道可以找尋到哪一個鍵值？

35 10-5 雜湊函數的碰撞問題-解決方法 如果雜湊函數產生碰撞問題，在建立雜湊表時就需要解決碰撞問題，以便雜湊搜尋法能夠找到正確的鍵值。常用的碰撞問題解決方法，如下所示： 線性深測法（Linear Probing）。 重雜湊法（Rehashing）： 鏈結法（Chaining）。

36 線性探測法-原則 「線性探測法」（Linear Probing）當碰撞情形發生時，如果該索引位置已經有鍵值，就使用下列原則來處理，如下所示： 如果鍵值欲存放的索引位置已經有鍵值存在時，將鍵值儲存在下一個索引位置。 如果原位置的下一個索引位置仍然已有鍵值，再將鍵值儲存在下一個索引位置，重覆操作直到找到一個空位置。 上述碰撞問題的處理稱為線性探測法或「線性開放地址法」（Linear Open Addressing）。

37 10-5-1 線性探測法-範例 例如：搜尋的鍵值清單，如下所示： 雜湊函數是使用除法的餘數運算，如下所示：
37, 25, 11, 29, 34, 46, 44, 35 雜湊函數是使用除法的餘數運算，如下所示： 索引位置 = 鍵值 mod 10

38 線性探測法-建立步驟1,2 Step 1：首先建立大小10的一維陣列雜湊表，大小是雜湊函數的除數10，並且將雜湊表的所有元素都清除成-1，如下圖所示： Step 2：處理鍵值37，經過雜湊函數計算後，得到陣列索引值是37 mod 10 = 7，所以把鍵值37存入雜湊表的索引值7，如下圖所示：

39 線性探測法-建立步驟3,4 Step 3：接著處理鍵值25，經計算得索引值25 mod 10 = 5，所以將鍵值25存入雜湊表索引值5，如下圖所示： Step 4：重複操作執行鍵值：11、29、34和46，經雜湊函數得到索引值：1、9、4和6，將鍵值存入雜湊表後，如下圖所示：

40 線性探測法-建立步驟5 Step 5：接著處理鍵值44，經雜湊函數計算得到索引值為4，不過索引值4已經有元素存在，碰撞發生了。依前述原則，接著檢查索引值5，元素存在，繼續檢查索引值6仍然有元素存在，重覆檢查直到索引值8是空的，所以將鍵值44存入雜湊表，如下圖所示：

41 線性探測法-建立步驟6 Step 6：最後處理鍵值35，經計算得索引值5，碰撞又發生了，找到索引值9仍然沒有空的索引位置。但是在雜湊表還有索引值0、2和3是空的，可以使用技巧將雜湊表的頭尾連接起來，如下： temp = (temp+1) %10 公式計算下一個索引位置。經運算可以把鍵值35儲存在索引值0，完成雜湊表的建立，如下圖所示：

42 線性探測法-雜湊搜尋法 雜湊搜尋法是在雜湊表搜尋鍵值，一樣需要使用雜湊函數來計算出索引位置。例如：搜尋鍵值34，首先使用雜湊函數計算出索引值為34 mod 10 = 4，經比較雜湊表索引值4，找到此鍵值。

43 10-5-1 線性探測法-標頭檔 01: /* 程式範例: Ch10-6-1.h */
02: #define MAX_LEN 10 /* 最大陣列尺寸 */ 03: int hashTable[MAX_LEN];/* 雜湊表宣告 */ 04: /* 抽象資料型態的操作函數宣告 */ 05: extern void createHashTable(int len, int *array); 06: extern void printHashTable(); 07: extern int lineHashSearch(int key); 08: extern int hashFunc(int key);

44 線性探測法-執行效率 雜湊搜尋法的執行效率在不考慮建立雜湊表的時間和沒有碰撞情形發生的理想情況下，執行效率可以達到O(1)。

45 重雜湊法-問題 重雜湊法可以解決線性深測法儲存位置過於集中的問題，這是線性探測法解決碰撞問題時，造成的特殊情況，可以看出索引值4儲存的鍵值可能是索引值1、2和3發生碰撞而儲存的鍵值，或是雜湊函數運算結果是4。索引值6可能是由索引值5和6碰撞而決定。 這樣的結果將造成搜尋時，比較的次數快速的增加，而且這些鍵值連續的現象將愈演愈烈，因為碰撞的機會大幅增加，所以鍵值越連越多，這種情況稱為「叢聚現象」（Cluster），如下圖所示：

46 重雜湊法-說明 重雜湊法是使用多個雜湊函數來建立雜湊表，當第1個函數產生碰撞時，就使用第2個雜湊函數，如果第2個函數也產生碰撞時，就使用第3個雜湊函數，如此可以減少碰撞發生的機率，降低儲存位置過於集中的問題。

47 10-5-2 重雜湊法-範例 例如：使用和上一節相同的鍵值清單，如下所示： 雜湊函數一共有三個，都是使用除法的不同餘數運算，如下所示：
37, 25, 11, 29, 34, 46, 44, 35 雜湊函數一共有三個，都是使用除法的不同餘數運算，如下所示： (1) 索引位置 = 鍵值 mod 10 (2) 索引位置 = 鍵值 mod 2 (3) 索引位置 = 鍵值 mod 3的線性探測法 換句話說，如果第1個雜湊函數發生碰撞時，就使用第2個雜湊函數，如果第2個雜湊函數發生碰撞時，就使用第3個雜湊函數。

48 重雜湊法-建立過程 重雜湊法使用雜湊函數計算索引位置的完整過程，如下表所示：

49 重雜湊法-雜湊表 完整雜湊表的內容，如下圖所示：

50 10-5-3 鏈結法-問題 雖然重雜湊法可以解決線性深測法儲存位置過於集中的問題，不過線性探測法的雜湊搜尋仍然有兩個問題，如下所示：
擴充困難：如果雜湊表的儲存空間有n個元素，在存入n+1個元素時，就會發生鍵值無法存入的問題。 鍵值刪除問題：除非重建整個雜湊表，否則刪除有碰撞情況的鍵值，在雜湊搜尋時就有可能再也找不到。

51 鏈結法-說明 鏈結法是使用類似第8-2-2節的圖形鄰接串列表示法來建立雜湊表，這是使用一個結構陣列的指標，分別指向各鍵值的串列，如果有碰撞發生，只是將鍵值的節點插入串列，就可以解決線性探測法遇到的問題。

52 10-5-3 鏈結法-標頭檔 01: /* 程式範例: Ch10-6-3.h */
02: #define MAX_LEN /* 最大陣列尺寸 */ 03: struct Node { /* 節點結構宣告 */ 04: int data; /* 鍵值 */ 05: struct Node *next; /* 指下一個節點的指標 */ 06: }; 07: typedef struct Node *Table; 08: struct Node hashTable[MAX_LEN]; 09: /* 抽象資料型態的操作函數宣告 */ 10: extern void createHashTable(int len, int *array); 11: extern void printHashTable(); 12: extern int chainHashSearch(int key); 13: extern int hashFunc(int key);

53 10-5-3 鏈結法-範例 例如：搜尋的鍵值清單，如下所示： 雜湊函數是使用除法的餘數運算，如下所示：
37, 25, 11, 29, 34, 46, 44, 35 雜湊函數是使用除法的餘數運算，如下所示： 索引位置 = 鍵值 mod 10

54 鏈結法-雜湊表

55 鏈結法-雜湊搜尋 雜湊表各鍵值的搜尋次數（即比較次數），如下表所示：