线性散列

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

算法细节

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

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

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

  • 使用散列函数 进行地址计算,并把这个计算结果记为   中。
  • 如果   是位于   之前的地址,那么访问的地址为  
  • 如果   是位于   指向或之后的地址,那么地址为 

添加一个散列槽时:

  • 在散列表的末尾分配一个新的散列槽。
  • 如果   指向第   散列槽中,重置   并自增  
  • 否则自增  中。

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


在语言系统中的应用

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

在数据库系统中的应用

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

参考文献

  1. ^ Litwin, Witold, Linear hashing: A new tool for file and table addressing (PDF), Proc. 6th Conference on Very Large Databases, 1980: 212–223 [2018-04-16], (原始内容存档 (PDF)于2019-07-28) 
  2. ^ Larson, Per-Åke, Dynamic Hash Tables, Communications of the ACM, April 1988, 31 (4): 446–457, doi:10.1145/42404.42410 
  3. ^ Griswold, William G.; Townsend, Gregg M., The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon, Software - Practice and Experience, April 1993, 23 (4): 351–367 [2018-04-16], (原始内容存档于2008-03-19)