线性散列

线性散列是由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的文章。