Chapter 14 搜尋 14.1 循序搜尋 14.2 二元搜尋 14.3 雜湊.

Presentation on theme: "Chapter 14 搜尋 14.1 循序搜尋 14.2 二元搜尋 14.3 雜湊."— Presentation transcript:

1 Chapter 14 搜尋 14.1 循序搜尋 14.2 二元搜尋 14.3 雜湊

2 14.1 循序搜尋 循序搜尋(sequential search)又稱為線性搜尋（linear search），適用在小檔案。這是一種最簡單的搜尋方法，從頭開始找一直到找到為止。

3 14.2 二元搜尋 二元搜尋(binary search)是找尋一個已排序的檔案最好的方法。
14.2 二元搜尋 二元搜尋(binary search)是找尋一個已排序的檔案最好的方法。 二元搜尋的觀念與二元樹十分類似，其比較是從所有記錄的中間點M開始，若欲搜尋的鍵值小於M，則從M之前的記錄繼續搜尋，否則搜尋M以後的記錄，如此反覆進行，直到鍵值被找到為止。

4 14.2 二元搜尋 舉例來說，假設在已排序數列12, 23, 29, 38, 44, 57, 64, 75, 82, 98，若欲以二元搜尋法找尋82，則先從數列的中間點M = [(left+right)/2] = [(1+10)/2] = 5（第5筆記錄）開始比對，如下所示：

5 14.2 二元搜尋

6 14.2 二元搜尋 二元搜尋每一次比較，檔案皆縮小一半，從1/2，1/4，1/8，1/16，...在第k次比較時，最多只剩下[n/2k] 。
14.2 二元搜尋 二元搜尋每一次比較，檔案皆縮小一半，從1/2，1/4，1/8，1/16，...在第k次比較時，最多只剩下[n/2k] 。 最壞的情況是搜尋到最後只剩下一個記錄n/2k = 1，所以 K = log2n，即最多的比較次數是log2n。

7 14.3 雜湊 在雜湊法中，鍵值（key value）或識別字（identifier）在記憶體的位址是經由函數（function）轉換而得的，如圖14-1。此種函數，一般稱之為雜湊函數（hashing funciton）或鍵值對應位址轉換（key to address transformation）。

8 14.3 雜湊 4.3.1 雜湊函數 一般常用的雜湊函數有下列四種方法：
14.3 雜湊 雜湊函數 一般常用的雜湊函數有下列四種方法： 平方後取中間值法（mid-square） 此種方法乃是將鍵值平方，然後視儲存空間的大小來決定取幾位數。 除法（division） 此種方法將鍵值利用模數運算（mod）後，其餘數即為此鍵值所對稱的位址，亦即 Fd(x) = x mod m 。

9 14.3 雜湊 數位分析法（digit analysis） 此種方法適合大的靜態資料 ，亦即所有的鍵值均事先知 道，然後檢查鍵值的所有數 位，分析每一數位是否分佈 均勻，將不均勻的數位刪除 ，然後根據儲存空間的大小 來決定數位的數目。

10 14.3 雜湊 很容易可觀察在7個鍵值中1、2、3位（由左邊算起）的數值顯得太不均勻，故刪除第1，2，3位數，再觀察第8位也太多8，故刪除。
14.3 雜湊 很容易可觀察在7個鍵值中1、2、3位（由左邊算起）的數值顯得太不均勻，故刪除第1，2，3位數，再觀察第8位也太多8，故刪除。 假設有1000個儲存空間，而且挑選每一鍵值的4，6，7位做為再儲存的位址，分別為523, 937, 382, 497, 616, 954, 236。

11 14.3 雜湊 上述提及利用四種方法將鍵值（或識別字）轉換其對應的儲存位址，這些儲存位址，一般稱之為雜湊表（Hash table）。
14.3 雜湊 上述提及利用四種方法將鍵值（或識別字）轉換其對應的儲存位址，這些儲存位址，一般稱之為雜湊表（Hash table）。 在雜湊表內將儲存空間劃分為b個桶（bucket），分別為HT(0)，HT(1)，...，HT(b-1) 。 每個桶具S個記錄，亦即由S個槽（slot）所組合而成。因此雜湊函數是把鍵值轉換；對應到雜湊表的0至b-1桶中。

12 14.3 雜湊 在C語言中所有合乎規定變數名稱共有 ，此處假設變數名稱只有六位數是合法的。
14.3 雜湊 在C語言中所有合乎規定變數名稱共有 ，此處假設變數名稱只有六位數是合法的。 而變數名稱不一定要設六位，只要低於或等於六位即可，因此總共有 × × × × ×375 即 。

13 14.3 雜湊 假設有n個，則稱n/T為識別字密度（identifier density），而稱α= n/(sb)為裝載密度（loading density）或裝載因子（loading factor）。 假使有識別字k1和k2，經過雜湊函數轉換，若此二個識別字對應到相同的桶中，此時稱之為碰撞（collision）或同義字（synonyms）。若桶中的S槽還未用完，則凡是該桶的同義字均可對應至該桶中。

14 14.3 雜湊 如果識別字對應至一個已滿的桶中時，此稱之為溢位（overflow）。如果桶的大小S只有一個槽，則碰撞與溢位必然會同時發生。
14.3 雜湊 如果識別字對應至一個已滿的桶中時，此稱之為溢位（overflow）。如果桶的大小S只有一個槽，則碰撞與溢位必然會同時發生。 假設雜湊表HT 中b = 27桶，每桶有2個槽，即S = 2，而且某程式中所用的變數n = 10個識別字。

15 14.3 雜湊 裝載因子α= 10/27×2≒0.19。 雜湊函數必須能夠將所有的識別字對應到1-27的整數中，假設以1-27整數來代替英文字母A-Z及底線(_)，則將雜湊函數定義為f(x) =識別字X的第一個字母。

16 14.3 雜湊 例如HD、E、K、H、J、B2、B1、B3、B5與M分別對應到8、5、11、8、10、2、2、2、2、及13號桶中，其中B1、B2、B3、B5分別對應到2號桶中，是同義字亦即產生碰撞。 HD與H亦是同義字，其對應到8號桶中，圖14-2是HD、E、K、H、J、B2與B1對應到雜湊表的情形。

17 14.3 雜湊 在圖14-2當B3再進入雜湊表時，就發生溢位。假使每個桶中只有一個槽，則產生的溢位的機率就增加了。

18 14.3 雜湊 14.3.2 解決溢位的方法（overflow handling）
14.3 雜湊 解決溢位的方法（overflow handling） 線性探測（linear probing）： 是把雜湊位址視為環狀的空間，當溢位發生時，以線性方式從下一號桶開始探測，找尋一個空的儲存位址將資料存入。 若找完一個循環還沒有找到空間，則表示位置已滿。如將HD、E、H、B2、B1、B3、B5、K、A、Z與ZB，放入具有每一桶只有一個槽的雜湊表中，其結果如圖14-3所示：

19 14.3 雜湊

20 14.3 雜湊 由於f(x) = X的第一字母，所以f(HD) = 8，f(E) = 5，亦即HD、E分別放在雜湊表中第8號與第5號桶中，f(H) = 8，此時8號桶已有HD，故發生碰撞及溢位，利用線性探測即往8號桶下找一空白的桶號，發現9號是空的，所以9號桶為H。

21 14.3 雜湊 f(B2) = 2放入2號桶，f(B1)與f(B3) = 2，由於2號桶已存B2，故往下找各別存於3與4號桶，當B5再轉進來時就存於6號桶。f(K) = 11放入11號桶，f(A) = 1放入1號桶，f(Z) = 26放入26號桶，f(ZB)亦是26只好從1號桶往下找一空間放入7號。 由上例應該明瞭線性探測如何處理溢位的情形。線性探測又稱為線性開放位址（linear open addressing）。

22 14.3 雜湊 利用線性探測以解決溢位間題，極易造成鍵值聚集在一塊，增加搜尋的時間，如欲尋找ZB則必須尋找HT(26)、HT(1)、...、HT(7)，共須八次比較。

23 14.3 雜湊 重覆雜湊（rehashing）： 乃是先設計好一套的雜湊函數f1，f2，f3，...，fm，當溢位發生時先使用f1，若再發生溢位則使用f2，.....一直到沒有溢位發生。

24 14.3 雜湊 平方探測（quadratic probing）： 此法是用來改善線性探測之缺失，避免相近的鍵值聚集在一塊。當f(x)的位址發生溢位時，下一次是探測(f(x)+i2) % b與(f(x) - i2) % b，其中1 < i < (b-1)/2，b是具有4j+3型式的質數。

25 14.3 雜湊 鏈結串列（chaining）： 是將雜湊空間建立成b個串列，起初只有b個串列首，故放起始位址，並不存放資料，相同位址的鍵值，將形成一個鍵值結串列如圖14-4所示。 B5，B3，B1，B2放在第2個串列，H與HD收在第8個串列，以及ZB與Z放在第26個串列上。

26 14.3 雜湊