第九章　搜尋 9-1 搜尋簡介 9-2 常見的搜尋方法 9-3 雜湊搜尋法

搜尋的分類 和排序法一樣，若依資料量大小來區分，搜尋可分為： 1.內部搜尋：資料量較小的檔案，可以直接全部載入記憶體中進行搜尋。 2.外部搜尋：資料量大的檔案，無法一次載入記憶體處理，而需使用到輔助記憶體來分次處理。

以搜尋過程中被搜尋的表格或資料是否異動，區分為靜態搜尋(Static Search)及動態搜尋(Dynamic Search)。 靜態搜尋是指資料在搜尋過程中，該搜尋資料不會有增加、刪除、或更新等行為，例如符號表搜尋就屬於一種靜態搜尋。 動態搜尋則是指所搜尋的資料，在搜尋過程中會經常性地增加、刪除、或更新。例如B-tree搜尋就屬於一種動態搜尋。

常見的搜尋方法 循序搜尋法 二元搜尋法 內插搜尋法 費氏搜尋法

循序搜尋法 又稱線性搜尋法，是一種最簡單的搜尋法。 優點是檔案在搜尋前不需要作任何的處理與排序，缺點為搜尋速度較慢。 如果資料沒有重覆，找到資料就可中止搜尋的話，在最差狀況是未找到資料，需作n次比較，最好狀況則是一次就找到，只需1次比較。

循序法分析 1. 時間複雜度：如果資料沒有重覆，找到資料就可 中止搜尋的話，在最差狀況是未找到資料，需作 n次比較，時間複雜度為O(n)。 2. 在平均狀況下，假設資料出現的機率相等，則需 (n+1)/2次比較。 3. 當資料量很大時，不適合使用循序搜尋法。但如 果預估所搜尋的資料在檔案前端則可以減少搜尋 的時間。

範例程式：ch09_01.java

二元搜尋法 二分搜尋法是將資料分割成兩等份，再比較鍵值與中間值的大小，如果鍵值小於中間值，可確定要找的資料在前半段的元素，否則在後半部。 如此分割數次直到找到或確定不存在為止。

例如以下已排序數列 2、3、5、8、9、11、12、16、18 ，而所要搜尋值為11時： 首先跟第五個數值 9 比較： 因為11＞9，所以和後半部的中間值 12 比較： 因為 11＜12，所以和前半部的中間值 11比較： 因為 11=11，表示搜尋完成，如果不相等則表示找不到。

二元法分析 時間複雜度：因為每次的搜尋都會比上一次少一 半的範圍，最多只需要比較[log2n]+1或[log2(n+1)] (參考書本的表示方式)，時間複雜度為O(log n)。 2. 二分法必須事先經過排序，且資料量必須能直接在 記憶體中執行。 3. 此法適合用於不需增刪的靜態資料。

範例程式：ch09_02.java

內插搜尋法 它是依照資料位置的分佈，利用公式預測資料的所在位置，再以二分法的方式漸漸逼近。 使用內插法是假設資料平均分佈在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。 其內插法的公式為： Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low )

插補搜尋法的步驟如下： 將記錄由小到大的順序給予1,2,3…n的編號。 令low=1，high=n 令Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) 若key<keyMid且high≠Mid-1則令high=Mid-1 若key＝keyMid表示成功搜尋到鍵值的位置 若key>keyMid且low≠Mid+1則令low=Mid+1

內插法分析 1. 一般而言，內插搜尋法優於循序搜尋法，而如果資 料的分佈愈平均，則搜尋速度愈快，甚至可能第一 次就找到資料。此法的時間複雜度取決於資料分佈 的情況而定，平均而言優於O(log n)。 2. 使用內插搜尋法資料需先經過排序。

範例程式：ch09_03.java

費氏搜尋法 費氏搜尋法(Fibonacci Search)又稱費伯那搜尋法，此法和二分法一樣都是以切割範圍來進行搜尋，不同的是費氏搜尋法不以對半切割而是以費氏級數的方式切割。 費氏級數F(n)的定義如下： F0=0 ,F1=1 Fi=Fi-1+Fi-2，i≧2

費氏樹搜尋原則 費氏樹的左右子樹均亦為費氏樹。 當資料個數n決定，若想決定費氏樹的階層k值為何，我們必須找到一個最小的k值，使得費氏級數的Fib(k+1)≧n+1。 費氏樹的樹根定為一費氏數，且子節點與父節點的差值絕對值為費氏數。 當k2時，費氏樹的樹根為Fib(k)，左子樹為(k-1)階費氏樹(其樹根為Fib(k-1))，右子樹為(k-2)階費氏樹(其樹根為Fib(k)+Fib(k-2))。 若n+1值不為費氏數的值，則可以找出存在一個m使用Fib(k+1)-m=n+1，m=Fib(k+1)-(n+1)，最後費氏樹的各節點再減去差值m即可，並把小於1的節點去掉即可。

k費氏樹示意圖

費氏法分析 1.平均而言，費氏搜尋法的比較次數會少於二元搜尋法，但在最壞的情況下則二元搜尋法較快。其平均時間複雜度為O(log2N) 2.費氏搜尋演算法較為複雜，需額外產生費氏樹。

雜湊搜尋法 雜湊法不僅被用於資料的搜尋外，在資料結構的領域中，您還能將它應用在資料的建立、插入、刪除與更新。 符號表依其特性可分為二類：靜態表(Static Table)和「動態表」(Dynamic Table)。 「雜湊表」(Hash Table)則是屬於靜態表格中的一種，我們將相關的資料和鍵值儲存在一個固定大小的表格中。

雜湊法(Hashing)就是將本身的鍵值，經由特定的數學函數運算或使用其他的方法，轉換成相對應的資料儲存位址。 而雜湊所使用的數學函數就稱為「雜湊函數」(Hashing function)。

雜湊法簡介 雜湊函數的相關名詞 bucket(桶)：雜湊表中儲存資料的位置，每一個位置對應到唯一的一個位址(bucket address)。桶就好比一筆記錄。 slot(槽)：每一筆記錄中可能包含好幾個欄位，而slot指的就是「桶」中的欄位。 collision(碰撞)：若兩筆不同的資料，經過雜湊函數運算後，對應到相同的位址時，稱為碰撞。 溢位：如果資料經過雜湊函數運算後，所對應到的bucket已滿，則會使bucket發生溢位。

雜湊表：儲存記錄的連續記憶體。雜湊表是一種類似資料表的索引表格，其中可分為n個bucket，每個bucket又可分為m個slot，如下圖所示： ↑ 07-772-6604 May 0003 07-772-5525 Jacky 0002 07-772-1234 Allen 0001 → 電話 姓名 索引 bucket slot slot

載入密度(Loading Factor):所謂載入密度是指識別字的使用數目除以雜湊表內槽的總數： 同義字(Synonym):當兩個識別字I1及I2，經雜湊函數運算後所得的數值相同，即f(I1)=f(I2)，則稱I1與I2對於f這個雜湊函數是同義字。 載入密度(Loading Factor):所謂載入密度是指識別字的使用數目除以雜湊表內槽的總數： 如果α值愈大則表示雜湊空間的使用率越高，碰撞或溢位的機率會越高。 n(識別字的使用數目) α(載入密度)= s(每一個桶內的槽數)b(桶的數目)

完美雜湊(perfect hashing):指沒有碰撞又沒有溢位的雜湊函數。 通常在設計雜湊函數應該遵循底下幾個原則： 1. 降低碰撞及溢位的產生。 2. 雜湊函數不宜過於複雜，越容易計算越佳。 3. 儘量把文字的鍵值轉換成數字的鍵值，以利雜湊函 數的運算。 4. 所設計的雜湊函數計算而得的值，儘量能均勻地分 佈在每一桶中，不要太過於集中在某些桶內，這樣 就可以降低碰撞，並減少溢位的處理。

常見的雜湊函數 除法 最簡單的雜湊函數是將資料除以某一個常數後，取餘數來當索引。 例如在一個有13個位置的陣列中，只使用到7個位址，值分別是12,65,70,99,33,67,48。 那我們就可以把陣列內的值除以13，並以其餘數來當索引，我們可以用下例這個式子來表示： h(key)=key mod B

一般而言，會建議各位在選擇B時，B最好是質數。 而上例所建立出來的雜湊表為： 索引 資料 65 1 2 67 3 4 5 70 6 7 33 8 99 9 48 10 11 12 在這個例子中，我們所使用的B=13。 一般而言，會建議各位在選擇B時，B最好是質數。 而上例所建立出來的雜湊表為：

中間平方法 中間平方法和除法相當類似，它是把資料乘以自己，之後再取中間的某段數字做索引。 在下例中我們用中間平方法，並將它放在100位址空間，其操作步驟如下： 將12,65,70,99,33,67,51平方後如下： 取佰位數及十位數作為鍵值，分別為 144,4225,4900,9801,1089,4489,2601 14、22、90、80、08、48、60

數位分析法 數位分析法適用於資料不會更改，且為數字型態的靜態表。 電話 索引 07-772-2234 234 07-772-4525 525 07-774-2604 604 07-772-4651 651 07-774-2285 285 07-772-2101 101 07-774-2699 699 07-772-2694 694

碰撞問題 線性探測法 平方探測 再雜湊 鏈結串列

線性探測法 線性探測法是當發生碰撞情形時，若該索引已有資料，則以線性的方式往後找尋空的儲存位置，一找到位置就把資料放進去。 線性探測法通常把雜湊的位置視為環狀結構，如此一來若後面的位置已被填滿而前面還有位置時，可以將資料放到前面。

範例程式：ch09_04.java

平方探測 在平方探測中，當溢位發生時，下一次搜尋的位址是(f(x)+i2) mod B與(f(x)-i2) mod B，即讓資料值加或減i的平方，例如資料值key，雜湊函數f： 第一次尋找：f(key) 第二次尋找：(f(key)+12)%B 第三次尋找：(f(key)-12)%B 第四次尋找：(f(key)+22)%B 第五次尋找：(f(key)-22)%B ． 第n次尋找：(f(key)±((B-1)/2)2)%B，其中，B必須為4j+3型的質數，且1≦i≦(B-1)/2

再雜湊 再雜湊就是一開始就先設置一系列的雜湊函數，如果使用第一種雜湊函數出現溢位時就改用第二種。 如果第二種也出現溢位則改用第三種，一直到沒有發生溢位為止。 例如h1為key%11，h2為key*key，h3為key*key%11，h4……。

鏈結串列 如果發生溢位就把相同位址之鍵值鍵結在串列首的後面，形成一個鍵結串列，直到所有的可用空間全部用完為止。如下圖：

範例程式：ch09_05.java

雜湊法整合範例 在上例中我們直接把原始資料值存在雜湊表中，如果現在要搜尋一個資料，只需將它先經過雜湊函數的處理後，直接到對應的索引值串列中尋找，如果沒找到表示資料不存在。 如此一來可大幅減少讀取資料及比對資料的次數，甚至可能一次的讀取比對就找到想找的資料。

範例程式：ch09_06.java