线性散列是由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中。
最後所得的表分为三个部分；S之前的部分，从S到N \times 2^L的部分，和N \times 2^L之后的部分。第一个和第三个部分的存储位置為H \bmod (N \times 2^{L+1})，中間部分储存於H \bmod( N \times 2^L)。每當S的值增至N \times 2^L，表的大小都會增加一倍。
在语言系统中的应用
Griswold和Townsend讨论了线性散列在Icon language中的应用。他们讨论了使用线性散列作为动态数组的一种实现的效果，并得出了相关的性能比较。
在数据库系统中的应用
线性散列用于在Berkely DB中，而Berkerly DB又用于许多的软件中（例如OpenLDAP)。它由C语言实现，原理基于一篇发表于CACM的文章。
参考文献
评论 (0)