資料存取技術--赫序函數搜尋法 (Hashing Function Search)

Presentation on theme: "資料存取技術--赫序函數搜尋法 (Hashing Function Search)"— Presentation transcript:

1 資料存取技術--赫序函數搜尋法 (Hashing Function Search)
赫序(Hashing)是一種相當有效率的資料存取技術，從檔案存取到資料庫管理系統(Database Management System)，高階程式語言的翻譯程式與編譯程式，計算機的作業系統(Operating System)，以致於許多系統程式為求簡單快速地運用有限的儲存資源達成資料運作(Data manipulate)的功能，都是應用這種技術。

2 赫序函數搜尋法的意義 所謂「赫序函數」，簡單地說，就是可以將鬆散而無序的資料換算成密集的、有對應關係的整數值之簡單函數。
有人稱赫序函數為一種由關鍵字至位址(Key-to-address)的轉換函數。

3 赫序函數搜尋法之資料儲存與擷取 首先，欲將資料儲存在檔案時，用赫序函數我們可以計算出每一資料錄之關鍵字所對應的整數值，而該整數即為預備作為存放該資料錄之位址。 其次，在以赫序函數儲存資料的檔案中，欲找尋特定之資料錄，即可以該資料錄之關鍵字，運用相同之赫序函數計算出對應的整數值，而該整數即為存放該資料錄之位址。

4 赫序函數搜尋法─範例(餘數法)

5 赫序函數搜尋法之要領 設定一種以資料錄關鍵值決定儲存位址的赫序函數。 每一筆資料錄依設定的赫序函數決定儲存位址。
搜尋時，由特定的資料錄之關鍵值求算赫序函數值即可推算儲存位址，找出特定的資料錄。 赫序函數的計算時間得遠小於在資料表中比對資料錄的時間。

6 幾種簡單的赫序函數 1. 餘數法 將資料錄關鍵值除以固定數之餘數為儲存位址
H(K) = (K mod N) + 1 K代表資料錄關鍵值 N代表儲存位址容納資料錄的數量 {10, 13, 19, 52, 31}之儲存位址分別是1, 4, 5, 3, 2

7 幾種簡單的赫序函數 2. 平方取中間數法 計算出鍵值K的平方，然後截取中間N位儲存位址
H(K) = H(1234) = G(1234 ×1234) = G( ) = 227

8 幾種簡單的赫序函數 3. 折疊法 將鍵值K以L為長度切割成許多段落，然後將這些段落相加得儲存位址
K = , L = 2 H( ) = = 109

9 赫序函數的碰撞(Collision) 當兩個以上的資料錄藉由赫序函數計算而得的整數值相同時，意即兩者都將使用相同的儲存位置，此時，即產生碰撞問題。 {10, 13, 19, 53, 31}之儲存位址分別是 1, 4, 5, 4, 2 “13”與“53”都要選擇4號位置作儲存碰撞問題 處理碰撞問題的方法--基本上，「先入為主」，後來者即需往後面的位置找尋空位！ 線性移位法 跳蛙式移位法

10 赫序函數的碰撞─線性移位法 若預備作為存放資料錄之位址已先有資料佔用，則往下找尋空的位置，將該資料錄存入。
若是到達儲存位置的末端依舊無空位，則轉向儲存位置的前端繼續找尋空的位置。

11 赫序函數的碰撞─線性移位法 K=43 N=10 H(K) = (K mod N) + 1 = 4 43

12 赫序函數的碰撞─跳蛙式移位法 若預備作為存放資料錄之位址已先有資料佔用，則改試下一個位置（意即下移一步），若也被佔用，則跳過新位置之下一個，而以其下下一個（意即下移二步）為新位置，若這個新位置也被佔用，則下移四步為新位置，依此類推。 若是到達儲存位置的末端依舊無空位，則依步數轉向儲存位置的前端繼續找尋空的位置。

13 赫序函數的碰撞─跳蛙式移位法 K=43 N=10 H(K) = (K mod N) + 1 = 4 43