線性散列：動態hash常用的另一種方法為線性散列，它能隨數據的插入和刪除，適當的對hash桶數進行調整，與可擴展散列相比，線性散列不需要存放數據桶指針的專門目錄項，且能更自然的處理數據桶已滿的情況，允許更靈活的選擇桶分裂的時機，因此實現起來相比前兩種方法要復雜。
理解線性散列，需要引入“輪轉分裂進化”的概念，各個桶輪流進行分裂，當一輪分裂完成之後，進入下一輪分裂，於是分裂將從頭開始。用Level表示當前的“輪數”，其值從0開始。假定hash表初始桶數為N(要求N是2的冪次方)，則值logN(以2為底)是指用於表示N個數需要的最少二進制位數，用d0表示，即d0 =logN。
以上提到，用Level表示當前輪數，則每輪的初始桶數為N*2^Level個(2^Level表示2的Level次方)。例如當進行第0輪時，level值為0，則初始桶數為N*2^0=N。桶將按桶編號從小到大的順序，依次發生分裂，一次分裂一個桶，這裡我們使用Next指向下次將被分裂的桶。
每次桶分裂的條件可靈活選擇，例如，可設置一個桶的填充因子r(r<1)，當桶中記錄數達到該值時進行分裂；也可選擇當桶滿時才進行分裂。
需要注意的時，每次發生分裂的桶總是由Next決定，與當前值被插入的桶已滿或溢出無關。為處理溢出情況，可引入溢出頁解決。話不多說，先來看一個圖示：
假定初始時，數據分佈如上，hash函數為h(x)。桶數N=4，輪數Level為0，Next處於0位置；採用“發生溢出分裂”作為觸發分裂的條件。此時d=logN=2，即使用兩個二進位可表示桶的全部編號。
簡單解釋一下，為什麼32*、25*、18*分別位於第一、二、三個桶中。因為h(x)=32=100000，取最後兩個二進制位00，對應桶編號00；h(y)=25=11001,取最後兩個二進制位01，對應桶編號01；h(z)= 18=10010，最後兩位對應桶編號10。
接下來，向以上hash表中插入兩個新項h(x1)=43和h(x2)=37，插入結果如下圖所示：
我們來分析一下。當插入h(x1)=43=101011時，d值為2，因此取末尾兩個二進制位，應插入11桶。由於該桶已滿，故應增加溢出頁，並將43*插入該溢出頁內。由於觸發了桶分裂，因此在Next=0位置上(注意不是在11桶上)，進行桶分裂，產生00桶的映像桶，映像桶的編號計算方式為N+Next=4+0=100，且將原來桶內的所有元素進行重新分配，Next值移向下一個桶。
當插入h(x2)=37=100101時，d值仍為2，取末尾兩個二進制位，應插入01桶，該桶中有空餘空間，直接插入。
分析到這裡，讀者應該基本了解了線性散列的分裂方式。我們發現，桶分裂是依次進行的，且後續產生的映像桶一定位於上一次產生的映像桶之後。
讀者不妨繼續嘗試插入h(x)=29,22,66,34,50，情況如下圖所示，這裡不再詳細分析。
線性散列的查找操作，例如要查詢h(x)=18,32,44。假定查詢時，hash表狀態為N=4，Level=0,Next=1，因此d值為2。
(1) 查找h(x)=18=10010，取末兩位10，由於10位於Next=1和N=4之間，對用桶還未進行分裂，直接取10作為桶編號，在該桶中進行查找。
(2) 查找h(x)=32=10000，取末兩位00，由於00不在Next=1和N=4之間，表示該桶已經分裂，再向前取一位，因此桶編號為000 ，在該桶中進行查找。
(3) 查找h(x)=44=101100，取末兩位00，由於00不在Next=1和N=4之間，表示該桶已經分裂，再向前取一位，因此桶編號為100 ，在該桶中進行查找。
線性散列的刪除操作是插入操作的逆操作，若溢出塊為空，則可釋放。若刪除導致某個桶元素變空，則Next指向上一個桶。當Next減少到0，且最後一個桶也是空時，則Next指向N/2 -1的位置，同時Level值減1。
線性散列比可擴展動態散列更靈活，且不需要存放數據桶指針的專門目錄項，節省了空間；但如果數據散列後分佈不均勻，導致的問題可能會比可擴展散列還嚴重。
至此，三種動態散列方式介紹完畢。
附：對於多hash表和可擴展的動態散列，桶內部的組織，可採用(1)鍊式方法，一個元素一個元素的鏈接起來，則上例中的4表示最多只能鏈接4個這樣的元素；也可採用(2)塊方式，每個塊中可放若干個元素，塊與塊之間鏈接起來，則上例中的4表示最多只能鏈接4個這樣的塊。
參考書籍：高級數據庫系統及其應用，謝興生主編，清華大學出版社(北京)，2010.1
沒有留言:
張貼留言