線性散列是由Witold Litwin(1980)[1] 發明並被Paul Larson推廣的一種動態散列(dynamic hash)算法。線性散列表的每次擴張僅增加一個槽(slot、bucket), 頻繁的單槽擴張可以非常有效控制的衝突鏈的長度,從而哈希表擴展的代價攤還在每一次插入操作中[2]。 因此非常適合用於交互式應用程式。

算法細節

編輯

散列表初始化時,先分配任意的數目的散列槽,並在運行過程中檢測以下的值:

  •  :最初分配的散列槽數目。
  •  :它是一個整數,用於表徵當前散列表增長至的數量,這個整數是以對數來表示的。初始化數目為0。
  •  :一個指向散列槽的迭代指針,最初指向表中的第一個散列槽。

衝突(Collision)可以通過不同的方式來處理,最典型的處理方法是,每當發生溢出(overflow)插入操作後,與之對應創建一個新的散列槽,表的地址可以用以下的策略進行計算:

  • 使用散列函數 進行地址計算,並把這個計算結果記為   中。
  • 如果   是位於   之前的地址,那麼訪問的地址為  
  • 如果   是位於   指向或之後的地址,那麼地址為 

添加一個散列槽時:

  • 在散列表的末尾分配一個新的散列槽。
  • 如果   指向第   散列槽中,重置   並自增  
  • 否則自增  中。

所有這一切的是,該表分為三個部分;該部分之前 該科從 和之後 中。 第一個和最後一個部分都存儲使用 與中部分儲存使用 中。 每個時間 到達 表增加了一倍的大小。


在語言系統中的應用

編輯

Griswold和Townsend [3] 討論了線性散列在Icon language中的應用。 他們討論了使用線性散列作為動態數組的一種實現的效果,並得出了相關的性能比較。

在數據庫系統中的應用

編輯

線性散列用於在Berkely DB中,而Berkerly DB又用於許多的軟件中(例如OpenLDAP)。它由C語言實現,原理基於一篇發表於CACM的文章。

參考文獻

編輯
  1. ^ Litwin, Witold, Linear hashing: A new tool for file and table addressing (PDF), Proc. 6th Conference on Very Large Databases, 1980: 212–223 [2018-04-16], (原始內容存檔 (PDF)於2019-07-28) 
  2. ^ Larson, Per-Åke, Dynamic Hash Tables, Communications of the ACM, April 1988, 31 (4): 446–457, doi:10.1145/42404.42410 
  3. ^ Griswold, William G.; Townsend, Gregg M., The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon, Software - Practice and Experience, April 1993, 23 (4): 351–367 [2018-04-16], (原始內容存檔於2008-03-19)