线性散列

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

 算法细节 
散列表初始化时，先分配任意的数目的散列槽，并在运行过程中检测以下的值：
 ：最初分配的散列槽数目。
 ：它是一个整数，用于表征当前散列表增长至的数量，这个整数是以对数来表示的。初始化数目为0。
 ：一个指向散列槽的迭代指针，最初指向表中的第一个散列槽。

冲突（Collision）可以通过不同的方式来处理，最典型的处理方法是，每当发生溢出（overflow）插入操作后，与之对应创建一个新的散列槽，表的地址可以用以下的策略进行计算：
 使用散列函數进行地址计算，并把这个计算结果记为中。
 如果是位于之前的地址，那么访问的地址为。
 如果是位于指向或之后的地址，那么地址为。

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

最後所得的表分为三个部分；之前的部分，从到的部分，和之后的部分。第一个和第三个部分的存储位置為，中間部分储存於。每當的值增至，表的大小都會增加一倍。

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

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

 参考文献 

Category:散列
Category:搜尋演算法