[科普中国]-线性散列

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

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

N:最初分配的散列槽数目。

L:它是一个整数，用于表征当前散列表增长至的数量，这个整数是以对数来表示的。初始化数目为0。

S：一个指向散列槽的迭代指针，最初指向表中的第一个散列槽。

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

使用散列函数进行地址计算，并把这个计算结果记为H中。

如果公式1是位于S之前的地址，那么访问的地址为公式2。

如果公式1是位于S指向或之后的地址，那么地址为公式1。

（公式1）

（公式2）

添加一个散列槽时：

在散列表的末尾分配一个新的散列槽。

如果S指向第公式3散列槽中，重置S并自增 L。

否则自增S中。

（公式3）

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

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

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

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学