线性散列

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

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

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

• 使用散列函数 进行地址计算，并把这个计算结果记为 ${\displaystyle H}$  中。
• 如果 ${\displaystyle H{\bmod {(}}N\times 2^{L})}$  是位于 ${\displaystyle S}$  之前的地址，那么访问的地址为 ${\displaystyle H{\bmod {(}}N\times 2^{L+1})}$ 。
• 如果 ${\displaystyle H{\bmod {(}}N\times 2^{L})}$  是位于 ${\displaystyle S}$  指向或之后的地址，那么地址为${\displaystyle H{\bmod {(}}N\times 2^{L})}$ 。

添加一个散列槽时：

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

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

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

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