线性散列

线性散列是由Witold Litwin（1980） 发明并被Paul Larson推广的一种动态散列（dynamic hash）算法。线性散列表的每次扩张仅增加一个槽（slot、bucket），
频繁的单槽扩张可以非常有效控制的冲突链的长度，从而哈希表扩展的代价摊还在每一次插入操作中。 因此非常适合用于交互式应用程序。

算法细节 

散列表初始化时，先分配任意的数目的散列槽，并在运行过程中检测以下的值：

 :最初分配的散列槽数目。
 :它是一个整数，用于表征当前散列表增长至的数量，这个整数是以对数来表示的。初始化数目为0。
 ：一个指向散列槽的迭代指针，最初指向表中的第一个散列槽。

冲突（Collision）可以通过不同的方式来处理，最典型的处理方法是，每当发生溢出（overflow）插入操作后，与之对应创建一个新的散列槽，表的地址可以用以下的策略进行计算：

 使用散列函数 进行地址计算，并把这个计算结果记为  中。
 如果  是位于  之前的地址，那么访问的地址为 。
 如果  是位于  指向或之后的地址，那么地址为。

添加一个散列槽时：

 在散列表的末尾分配一个新的散列槽。
 如果  指向第  散列槽中，重置  并自增 。
 否则自增 中。

所有这一切的是，该表分为三个部分；该部分之前 该科从  要 和之后 中。 第一个和最后一个部分都存储使用  与中部分储存使用 中。 每个时间  到达  表增加了一倍的大小。

在语言系统中的应用 
Griswold和Townsend  讨论了线性散列在Icon language中的应用。 他们讨论了使用线性散列作为动态数组的一种实现的效果，并得出了相关的性能比较。

在数据库系统中的应用 
线性散列用于在Berkely DB中，而Berkerly DB又用于许多的软件中（例如OpenLDAP)。它由C语言实现，原理基于一篇发表于CACM的文章。

参考文献 

散列
搜尋演算法