動態雜湊 (Dynamic Hashing).

Presentation on theme: "動態雜湊 (Dynamic Hashing)."— Presentation transcript:

1 動態雜湊 (Dynamic Hashing)

2 動態雜湊函數 利用所謂的「索引」的輔助區域，配合雜湊函數的設計： 則是不需要索引輔助的動態雜湊函數：
如Litwin的虛擬雜湊、Larson動態雜湊和Fagin等人的延展雜湊等。 則是不需要索引輔助的動態雜湊函數： 如Litwin的Trie雜湊。

3 Larson的動態雜湊函數

4 定義 在1978年，Larson以串列樹(Link-Tree)的架構，提出了動態雜湊函數的檔案結構
在Larson的方法中，一開始會先有一個雜湊函數h0，用來決定儲存於檔案的記錄類別，進而利用該類別來決定儲存記錄的區段。

5 Larson動態雜湊函數之例子

6 記錄的插入 設一筆新的記錄其主鍵值為”in”欲加入檔案中，h0(“in”)=1，但因其每個區段只能儲存四筆記錄，區段0便發生了碰撞的現象，因此必須對區段0做一次分裂(Split)的程序處理。 在Larson的理論中，當第一次分類儲存的區段發生碰撞，便以各個分類節點為樹根(Root)，做類似二元樹的結構分裂。 分裂的依據和方法，Larson是選擇一個與h0雜湊函數毫不相關的虛擬0/1亂數產生器。該亂數產生器每次出現0和1的機率是相等的，利用這個產生器就可以決定該i+1筆記錄分裂後的儲存定址位置，其中i表示每個區段的容量。

7 加入"in"之結果

8 記錄的搜尋 Larson的雜湊函數中的索引呈現一個樹林的結構，而每棵樹皆是二元樹。 決定節點所屬的二元樹後，再檢查是否為外部節點
其中的節點，若是屬於外部節點者(即樹葉)皆會指到一個區段位址上；因此當使用者想找尋某一筆記錄時，首先利用h0雜湊函數來分辨其在索引中所屬的二元樹。 決定節點所屬的二元樹後，再檢查是否為外部節點 若是，則到該節點所指的區段中找尋該筆記錄， 若不存在則表示該記錄不在檔案中。 若該節點是樹根節點，則再利用主鍵值去執行虛擬亂數產生器 當產生器傳回的值是0，則找左邊的左子樹 反之則找右子樹。 若該節點為內部節點，則繼續執行亂數產生器，直到找到外部節點為止，即可以找到所屬的區段了

9 記錄的刪除 Larson的方法中亦考慮了當記錄被刪除時，如何處理以節省空間。
他的方法中，索引內的外部節點均指到某一區段，因此當某一區段內的某一筆記錄被刪除時，可以統計指向該區段的外部節點和其兄弟節點所關連的總記錄數。 若兩個區段總記錄數可以被一個區段所容納，則合併成一個區段；此時索引內指向此兩個區段的外部節點應同時去除，而他們父節點即成為外部節點，而其內容則儲存了結合後的區段位址。

10 Litwin的虛擬雜湊函數

11 在1977年Litwin提出了虛擬雜湊函數(Virtual Hashing Function)的概念，其中的雜湊函數本身會隨著檔案中記錄的加入或刪除而做自我調整。

12 Litwin 虛擬雜湊函數之例子

13 當某一個區段發生碰撞現象時，對應於該區段的部份則取為j=1，亦即該區段之雜湊函數變動為：
Litwin的虛擬雜湊函數定義如下： hj：Key→Key mod 2jN，j=0，1，2，...， 其中j一開始設為0。 當某一個區段發生碰撞現象時，對應於該區段的部份則取為j=1，亦即該區段之雜湊函數變動為： h1：Key→Key mod 2N 同理，第二次，第三次，...碰撞時，j的值即依次增加。 j值的增加只發生在有碰撞現象的區段中。 當發生碰撞時，增加j值可以重新分配該區段中的記錄到兩個不同的區段，主要原因是Litwin的雜湊函數本身在決定區段編號時，是取同餘數的方法，而j值的增加等於對同餘數的除數擴增為兩倍，因此其餘數的範圍亦會隨之擴增兩倍，因此區段內的記錄便分散到兩個不同的區段中。

14 記錄的插入 以N=100為例，將記錄分散在編號0至99的區段中，如圖。
當新加入一筆主鍵值為4900的記錄時，造成區段0發生碰撞的現象，因而對應於區段0之雜湊函數的j值必須加1，故造成區段0中的五筆記錄分散到區段0和區段100，如圖。

15 延展雜湊函數

16 定義 在1979年Fangin、Nieverglt和Pippenger提出了延展雜湊函數。
保證尋找記錄的過程中絕對不曾超過兩次磁碟機讀取次數(Disk Access Time)。 在延展雜湊函數中，包含一個動態結構的輔助區，用以協助記錄的加入或刪除時，彈性分配記錄到各個區段中， 這一彈性的動態輔助區即是「索引」。 在索引中，若所含的深度(depth)數為d，則整個區域將有2d個節點，而每一個節點均儲存一個區段位址

17 延展雜湊函數之例子

18 在延展雜湊函數法中，首先利用一個雜湊函數h將主鍵值轉換對應到一個虛擬鍵值(Pseudo-Key)，再根據此虛擬鍵值的前d個位元值，分辨其在索引中是屬於那一個節點，再利用每個節點都存有一個區段位址的特點，該區段即是儲存該記錄的區段。 其中d代表索引中對於每個虛擬鍵值選取前面的位元數。

19 記錄的加入 加入的記錄被分配到的區段已經存滿記錄時(發生碰撞現象)，則對於每個虛擬鍵值所選取的位元數會由原來的d個變成d+1個。

20 若有一筆新記錄的主鍵值是”in”且h(“in”)=01...，
因區段０現已額滿了，所以該區段會一分為二，將原來區段０中的記錄分散在區段0和區段3。

21 由於某一筆新記錄的加入而造成某一紀錄區段的碰撞，則延展雜湊函數必須做分裂的動作，如此就會使得索引中的d值加1而造成整個索引節點數將倍增一倍。

22 Trie雜湊函數

23 定義 在1981年Litwin利用Knuth所提的資料結構－Trie，發出另一種虛擬湊雜函數，亦稱之為Trie雜湊函數。
每一區段內所有記錄的主鍵值大於或小於另一區內的的每一筆記錄的主鍵值。 如此構成了一個有序檔案的要件。

24 Trie資料結構 Trie的節點共分成三個欄位(Field)： 數元欄位 高位指標 低位指標

25 其中數元個數(簡稱DN)用來表示在節點「比較」的運算中所選取的數元個數， 而數元值(簡稱DV)則用來記錄該比較的基準值。
數元欄位又分成數元個數和數元值兩個子欄位 其中數元個數(簡稱DN)用來表示在節點「比較」的運算中所選取的數元個數， 而數元值(簡稱DV)則用來記錄該比較的基準值。 高位指標(簡稱UP)則是用來記載當記錄的主鍵值的值大於該基準值時所可能儲存的區段之位址 低位指標(簡稱LP)則是用來儲存主鍵值的值小於該基準值所可能儲存的區段位址 Trie節點會連成類似二元樹的架構 當節點本身屬於內部節點時，即其高位指標或低位指標所指的位址是一個Trie節點而非區段位址時，必須在該值之前加上一個 ’－’ 符號。

26 檔案的初始 檔案開始是空的，假設目前有四筆記錄儲存進來，則區段的內容如圖 (b)所示，而圖(a)為其對應的Trie之節點
由於只有一個區段，所以UP=LP=0，且沒有發生碰撞的情形，因此DN=DV=’-‘。

27 檔案的初始

28 記錄的插入 假設有一筆新記錄且主鍵值為”a”欲加入此檔案 發生了碰撞的現象 必須將區段０做分裂處理

29 Trie雜湊函數首先將此五筆記錄的中間筆記錄(即「(i+1)/2」)的主鍵值找出來
接下來則選擇最小的 k 值使得在五筆記錄中存在有部分記錄的主鍵值C0C1...滿足下列條件： C0C1... Ck＞C’0C’1... C’k 此例中的k=0

30 做完選擇工作後，可以利用C’0C’1... C’k為基準對此五筆記錄重新分配儲存。
C0C1... Ck＞C’0C’1... C’k者的記錄都儲存到新的區段中，其餘的則繼續保留在原來的區段中。 此時Trie節點的UP=1且LP=0 其DN=0，DV=’0’ 區段1是新的區段 處理完碰撞分裂處理之後，檔案可以繼續接受新的記錄之加入。 區段分裂時，每一筆記錄所在的區段，必須符合的規則是將記錄中的主鍵值較大者分配到一個區段中，而主鍵值較小者仍留置在原區段中 Trie雜湊函數架構的檔案系統是有序(Ordered)檔案

31

32 記錄的搜尋 當使用者想要在以Trie雜湊函數組織架構起來的檔案中尋找記錄時
從Trie節點0開始，先比較主鍵值與DF內的值再決定往LP方向亦或往UP方向尋找，依此找尋下去，有如二元樹的搜尋一樣直到找到的指標內所儲存的是一個區段的位址為止； 欲查詢的記錄若不存在該區段中，就表示該記錄不存在檔案中了。

33 應用 雜湊表的製作

34 資料結構：建立一個空的表格 typedef struct list { int data; struct list *next ; } NODE; NODE table [m ] ; Void hashlist_init(void) int i ; for (i =0 ; i < m ; i ++) table[ i ] . key = EMPTY; table[ I ] . next =NULL;

35 插入 Void hashlist_insert(int key) { int insert_hashlist( ), addr ; addr = hash (key) ; if (table [addr].key != EMPTY) hashlist (addr, key ); else table[addr].key = key; }

36 int insert_hashlist ( int addr , int key)
{ NODE *p, *new_node; P = &table[addr]; While (p -> next != NULL) p = p ->next; if ((new_node = (NODE *)malloc(sizeof(NODE))) = = NULL) return (0); new_node ->key = key ; new_node ->next = NULL; p ->next = new_node ; return (1); }