查看“︁线性散列”︁的源代码

{{roughtranslation|time=2018-04-16T12:07:54+00:00}}
'''线性散列'''是由Witold Litwin（1980）<ref>{{Citation|title=Linear hashing: A new tool for file and table addressing|url=http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|year=1980|last1=Litwin|first1=Witold|journal=Proc. 6th Conference on Very Large Databases|pages=212–223|format=PDF|accessdate=2018-04-16|archive-date=2019-07-28|archive-url=https://web.archive.org/web/20190728080823/http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|dead-url=no}}</ref> 发明并被Paul Larson推广的一种动态散列（dynamic hash）算法。线性散列表的每次扩张仅增加一个槽（slot、bucket），
频繁的单槽扩张可以非常有效控制的冲突链的长度，从而哈希表扩展的代价摊还在每一次插入操作中<ref>{{Citation|title=Dynamic Hash Tables|date=April 1988|number=4|last1=Larson|first1=Per-Åke|journal=Communications of the ACM|volume=31|pages=446–457|doi=10.1145/42404.42410}}</ref>。 因此非常适合用于交互式应用程序。

== 算法细节 ==

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

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

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

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

添加一个散列槽时：

* 在散列表的末尾分配一个新的散列槽。
* 如果 <math>S</math> 指向第 <math>N \times 2^L</math> 散列槽中，重置 <math>S</math> 并自增 <math>L</math>。
* 否则自增 <math>S</math>中。

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



== 在语言系统中的应用 ==
Griswold和Townsend <ref>{{Citation|title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon|date=April 1993|url=http://citeseer.ist.psu.edu/griswold93design.html|last1=Griswold|last2=Townsend|first1=William G.|first2=Gregg M.|author1-link=Bill Griswold|journal=Software - Practice and Experience|volume=23|issue=4|pages=351–367|accessdate=2018-04-16|archive-date=2008-03-19|archive-url=https://web.archive.org/web/20080319150729/http://citeseer.ist.psu.edu/griswold93design.html|dead-url=no}}</ref> 讨论了线性散列在Icon language中的应用。 他们讨论了使用线性散列作为动态数组的一种实现的效果，并得出了相关的性能比较。

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

== 参考文献 ==
{{Reflist}}
[[Category:散列]]
[[Category:搜尋演算法]]