線性散列是由Witold Litwin（1980）發明並被Paul Larson推廣的一種動態散列（dynamic hash）算法。線性散列表的每次擴張僅增加一個槽（slot、bucket）， 頻繁的單槽擴張可以非常有效控制的衝突鏈的長度，從而哈希表擴展的代價攤還在每一次插入操作中。 因此非常適合用於互動式應用程式。
基本介紹
- 中文名：線性散列
- 外文名：Linear Hashing
- 套用領域：算法
算法細節,在語言系統中的套用,在資料庫系統中的套用,
算法細節
散列表初始化時，先分配任意的數目的散列槽，並在運行過程中檢測以下的值：
- N:最初分配的散列槽數目。
- L:它是一個整數，用於表征當前散列表增長至的數量，這個整數是以對數來表示的。初始化數目為0。
- S：一個指向散列槽的疊代指針，最初指向表中的第一個散列槽。
衝突（Collision）可以通過不同的方式來處理，最典型的處理方法是，每當發生溢出（overflow）插入操作後，與之對應創建一個新的散列槽，表的地址可以用以下的策略進行計算：
- 使用散列函式進行地址計算，並把這個計算結果記為H中。
- 如果公式1是位於S之前的地址，那么訪問的地址為公式2。
- 如果公式1是位於S指向或之後的地址，那么地址為公式1。
添加一個散列槽時：
- 在散列表的末尾分配一個新的散列槽。
- 如果S指向第公式3散列槽中，重置S並自增 L。
- 否則自增S中。
所有這一切的是，該表分為三個部分；該部分之前 該科從 要 和之後 中。 第一個和最後一個部分都存儲使用 與中部分儲存使用 中。 每個時間 到達 表增加了一倍的大小。
在語言系統中的套用
Griswold和Townsend討論了線性散列在Icon language中的套用。 他們討論了使用線性散列作為動態數組的一種實現的效果，並得出了相關的性能比較。
