線性散列

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

算法細節

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

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

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

• 使用散列函數 進行地址計算，並把這個計算結果記為 $H$ 中。
• 如果 $H{\bmod {(}}N\times 2^{L})$ 是位於 $S$ 之前的地址，那麼訪問的地址為 $H{\bmod {(}}N\times 2^{L+1})$。
• 如果 $H{\bmod {(}}N\times 2^{L})$ 是位於 $S$ 指向或之後的地址，那麼地址為$H{\bmod {(}}N\times 2^{L})$。

添加一個散列槽時：

• 在散列表的末尾分配一個新的散列槽。
• 如果 $S$ 指向第 $N\times 2^{L}$ 散列槽中，重置 $S$ 並自增 $L$。
• 否則自增 $S$中。

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

在語言系統中的應用

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

在數據庫系統中的應用

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