搜尋與雜湊

以下介紹循序搜尋、二元搜尋、內插搜尋與費氏搜尋，都是使用比較方式進行搜尋，未經排序的資料只能使用循序搜尋，已經排序的資料可以使用二元搜尋、內插搜尋與費氏搜尋來提升執行效率，但排序演算法比循序搜尋還要費時，對於搜尋次數很少的資料建議使用循序搜尋，如果資料不會變動且需要不斷地被搜尋，就可以考慮先排序再進行二元搜尋、內插搜尋或費氏搜尋。

從頭到尾依序找尋陣列內，指定數值是否存在，稱作「循序搜尋」。陣列內數值不需要事先排序，假設十個學生的成績陣列，如下圖，以循序搜尋方式找尋成績為59分的學生。

(b)程式執行結果

檢查score[ 0 ]= 44 是否等於59

檢查score[ 1 ]= 88 是否等於59

檢查score[ 2 ]= 78 是否等於59

檢查score[ 3 ]= 67 是否等於59

檢查score[ 4 ]= 92 是否等於59

檢查score[ 5 ]= 62 是否等於59

檢查score[ 6 ]= 59 是否等於59

找到59分

循序搜尋效率分析

第2到6行程式碼是程式執行效率的關鍵，迴圈執行n次，演算法效率為O(n)，n為被搜尋的資料數量。

二元搜尋(Binary Search)不斷將問題的搜尋範圍進行縮小，每次縮小一半，因而獲得較高的效率，但搜尋前需要將資料進行排序才能使用二元搜尋。二元搜尋比循序搜尋找到該資料的執行時間要短，也就是有較好的執行效率。使用「已排序成績陣列中是否包含成績為59分的學生」為例，進行二元搜尋概念的說明。

從頭到尾依序找尋稱作「循序搜尋」，但對已經由小到大排序好的資料可以使用「二分搜尋」方式加快找尋速度，因為已經排序可以從中間開始找，若要找的元素比中間元素值大，則往右邊找，若要找的元素比中間元素值小，則往左邊找，依此類推直到找到為止。

假設已排序的十個學生的成績陣列，如下圖，以二分搜尋方式找尋成績為59分的學生。

這樣的演算法需要一個成績陣列，事先將成績陣列由小到大排序好，一個迴圈(while)用於檢查「目前成績」是否等於59分，若找到一個成績等於59分，則輸出「找到59分的學生」，否則若「目前成績」大於59分，59分可能在「目前成績」為左半部，「目前成績」為左半部陣列元素取位於中間元素的成績，若「目前成績」小於59分，59分可能在「目前成績」為右半部，「目前成績」為右半部成績陣列取位於中間元素的成績。若找不到可以比較的「目前成績」，則輸出「找不到59分的學生」。

(b)執行結果

檢查score[ 5 ]= 78 是否等於59

right更新為 4

left更新為 0

mid更新為 2

檢查score[ 2 ]= 62 是否等於59

right更新為 1

left更新為 0

mid更新為 0

檢查score[ 0 ]= 45 是否等於59

right更新為 1

left更新為 1

mid更新為 1

找到59分

二元搜尋效率分析

執行第9到13行程式碼，是程式執行效率的關鍵，不斷縮小搜尋範圍為原來的一半，只需要約log(n)次的縮小範圍就能確定是否能找到，程式效率為O(log(n))，n為被搜尋的資料數量。

內插搜尋(Interpolation Search)不斷將問題的搜尋範圍進行縮小，每次依照比例進行縮小搜尋範圍，因而獲得較高的效率，但搜尋前需要將資料進行排序才能使用內插搜尋。內插搜尋比循序搜尋的執行時間要短，也就是有較好的執行效率。若資料平均分布的情況下，內插搜尋也比二元搜尋的執行時間要短，也就是執行效率較佳。

內插搜尋是二分搜尋的變形，二分搜尋每次都從中間開始找，那有沒有可能不從中間開始找，根據要找尋資料的數值，與兩端點數值的比例，使用內插法找尋最合適的索引值。若要找的元素比最合適索引值的元素值大，則往該索引值的右邊找；若要找的元素比最合適索引值的元素值小，則往該索引值的左邊找，依此類推直到找到為止。

這樣的演算法需要一個成績陣列，事先將成績陣列由小到大排序好，「目前成績」為內插法最合適的索引值所對應的元素值。一個迴圈(while)用於檢查「目前成績」是否等於59分，若找到成績等於59分，則輸出「找到59分的學生」，否則若「目前成績」大於59分，59分可能在「目前成績」為左半部，「目前成績」為左半部取內插法最合適索引值的成績；若「目前成績」小於59分，59分可能在「目前成績」為右半部，「目前成績」為右半部取內插法最合適索引值的成績。若找不到可以比較的「目前成績」，則輸出「找不到59分的學生」。

(b)執行結果

x為 3

檢查score[ 3 ]= 67 是否等於59

right更新為 2

left更新為 0

x更新為 1

找到59分

(c)程式效率分析

執行第10到14行程式碼，是程式執行效率的關鍵，不斷縮小搜尋範圍，平均而言，只需要約log(log(n)) 次的縮小範圍就能確定是否能找到，程式效率為O(log(log(n)))，n為被搜尋的資料數量。若資料分布不平均時，演算法效率為O(n)，例如：1,2,3,4,5,10000000，搜尋10存不存在時，演算法效率為O(n)。

費氏搜尋 (Fibonacci Search)不斷將問題的搜尋範圍進行縮小，每次依照費式數列進行縮小搜尋範圍，因而獲得較高的效率，但搜尋前需要將資料進行排序才能使用費氏搜尋。費氏搜尋比循序搜尋與二元搜尋的執行時間要短，也就是有較好的執行效率。

對已經由小到大排序好的資料可以使用「費式搜尋」方式加快找尋速度，每次都從費式數列所指定的索引值開始找，首先計算費式數列，再使用費式數列為索引值，減少內插搜尋需要除法與乘法運算計算索引值。若要找的元素比費式數列索引值所指定的元素值大，則往該費式數列索引值的右邊找；若要找的元素比費式數列索引值所指定的元素值小，則往該費式數列索引值的左邊找，依此類推直到找到為止。

假設費式數列第一項為0，第二項為1，第三項以後為前兩項相加，獲得費式數列為0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…，如果將此費式數列儲存到陣列F，如下圖。

假設搜尋陣列索引值為F[k]的元素，如果目標值比F[k]的元素小，表示搜尋左半部，此時使用F[k]-F[k-1]為下一個索引值；如果目標值比F[k]的元素大，表示搜尋右半部，此時使用F[k]+F[k-1]為下一個索引值，避免內插法計算下一個索引值的乘法與除法運算。

使用「已排序成績陣列中是否包含成績為59分的學生」為例，進行費式搜尋概念的說明。

假設已排序的12個學生的成績陣列，如下圖，在成績陣列的第一個元素為一個很小的數值，總共有13個元素，以費式搜尋方式找尋成績為59分的學生。

這樣的演算法需要一個成績陣列，事先將成績陣列由小到大排序好，「目前成績」為費式數列的索引值所對應的元素值。一個迴圈(while)用於檢查「目前成績」是否等於59分，若找到成績等於59分，則輸出「找到59分的學生」，否則若「目前成績」大於59分，59分可能在「目前成績」為左半部，「目前成績」為左半部取費式數列索引值的成績；若「目前成績」小於59分，59分可能在「目前成績」為右半部，「目前成績」為右半部取費式數列索引值的成績。若找不到可以比較的「目前成績」，則輸出「找不到59分的學生」。

(b)執行結果

檢查score[ 5 ]= 63 是否等於 59

檢查score[ 2 ]= 22 是否等於 59

檢查score[ 4 ]= 60 是否等於 59

檢查score[ 3 ]= 59 是否等於 59

找到score[ 3 ]= 59

(c)程式效率分析

執行第10到19行程式碼，是程式執行效率的關鍵，不斷縮小搜尋範圍，只需要約log(n)次的縮小範圍就能確定是否能找到，程式效率為O(log(n))，n為被搜尋的資料數量。

循序搜尋、二元搜尋、內插搜尋與費氏搜尋都是使用比較方式進行搜尋，雜湊不是使用比較方式進行搜尋，雜湊先將輸入的資料使用雜湊函式轉換成儲存的位址，再將資料存放在該位址，搜尋時也是先將輸入的資料使用雜湊函式轉換成儲存的位址，再檢查該位址的資料，來確定資料是否存在。

雜湊可用於密碼加密，密碼使用雜湊加密成另一個字串，將加密過後的字串儲存在密碼檔內，使用者輸入密碼後也使用相同的雜湊加密成一個字串，將加密過後的字串與密碼檔比較判斷是否相同，就可以知道密碼是否正確，無法從雜湊過後的字串倒推回原密碼字串。如果駭客拿走系統的密碼檔，密碼也是雜湊過後的字串，無法得知原來的密碼。

使用雜湊函式將資料轉換成位址，接著將資料儲存在該位址上，不需要使用比較進行搜尋，可以在很快的時間內找到資料。雜湊函式(hash)的表示式如下。

位址 = hash(資料)

9-2-1. 雜湊函式

雜湊函式要能夠減少碰撞(Collision)，也就是將不同的資料轉換到相同的位址，這樣稱作碰撞。如果發生碰撞就要啟動碰撞處理機制，在下一節會說明。如果所有資料經過雜湊函式轉換後都沒有發生碰撞，則稱作完美雜湊(Perfect Hashing)。雜湊函式執行效率要好，每一個資料都需要經過雜湊函式轉換成位址，如果雜湊函式效率不佳，會造成整個雜湊程式效率的瓶頸，以下舉例幾個常見雜湊函式。

9-2-2. 碰撞處理

如果兩個不同的資料經過雜湊函式轉換到相同位址，稱作碰撞(Collision)。如果發生碰撞就要啟動碰撞處理，碰撞處理分成開放位址(Open Addressing)與鏈結法(Separate Chaining)。

一、開放位址

開放位址分成線性探索(Linear Probing)與平方探索(Quadratic Probing)。線性探索表示當發生碰撞時找尋轉換後位址的下一個位址(hash(x)+1)，如果沒有碰撞就將資料放入，如果有發生碰撞就再找下一個位址(hash(x)+2)，一直找到可以儲存的空間為止，稱作線性探索。

線性探索因為發生碰撞，就在相鄰的下一個位址找到空的空間來儲存資料，如果多個輸入值雜湊後到相鄰的位址上，相鄰位址的附近區塊會越來越擠，就會造成一次聚集(primary clustering)。平方探索不會永遠在相鄰位址找可以擺放的空間，會越找越遠的位址找可以擺放的空間，減少一次聚集的可能性。

(二)鏈結法

若發生碰撞就使用鏈結串列串接在後面，當有多個元素雜湊到同一個位址，找尋速度會降低，因為找尋串接起來的元素需要一個一個比較才能知道該元素是否存在。

例如：雜湊函式為hash(x) = x % 8，使用鏈結法解決碰撞問題。假設依序輸入資料9, 13, 8, 1, 16, 17，則雜湊的過程如下。

若x=9，則hash(x)=1

若x=13，則hash(x)=5

若x=8，則hash(x)=0

若x=1，則hash(x)=1

若x=16，則hash(x)=0

若x=17，則hash(x)=1

輸入的資料量與雜湊表大小的比值，稱作load factor(α=n/m)，n為輸入的資料量，m為雜湊表大小。load factor(α)不能超過1，load factor(α)大於等於1時，無法再放入新的元素。當load factor(α)小於0.5時適合使用開放位址處理碰撞，大於等於0.5時容易發生碰撞，插入與找尋資料需要比較更多元素，造成程式效率下降。

寫一個雜湊功能的程式，首先建立長度為m的雜湊表，使用除法(Division method)建立雜湊函式，發生碰撞時使用線性探索(Linear Probing)找出儲存位址。將n個數值依序輸入雜湊表，保證n小於m，並顯示輸入過程中雜湊表的狀態。搜尋數值1與2是否存在雜湊表內，若該數值存在，則顯示該數值所在位址，否則回傳None。例如長度為8的雜湊表，依序輸入5個數值，分別為9、13、8、1與16。

輸入說明

輸入正整數n，表示接下來有n行，每行輸入一個數字，將輸入的數字插入雜湊表。

輸出說明

顯示插入的過程中雜湊表串列的狀態，最後搜尋數值1與2是否存在雜湊表內。

輸入範例

5

9

13

8

1

16

輸出範例

[None, 9, None, None, None, None, None, None]

[None, 9, None, None, None, 13, None, None]

[8, 9, None, None, None, 13, None, None]

[8, 9, 1, None, None, 13, None, None]

[8, 9, 1, 16, None, 13, None, None]

2

None

(a)解題想法

建立一個HashTable的類別，在函式__init__，新增m個元素的串列，用於建立雜湊表，函式hash為雜湊函式，使用除法(Division method)建立雜湊函式。函式insert用於插入數值到雜湊表，使用線性探索(Linear Probing)解決碰撞問題。函式isExist檢查元素是否存在。函式search找尋元素是否存在，若存在回傳位址，否則回傳None。函式v用於印出雜湊表。