线性散列 (LH) 是一种动态数据结构，它实现哈希表并一次增加或收缩一个存储桶。它是由Witold Litwin于1980年发明的。巴埃萨-耶茨和索萨-波尔曼对此进行了分析。 它是许多称为动态散列的方案中的第一个，例如拉尔森的线性散列与部分扩展，线性散列与优先级分割，线性散列与部分扩展和优先级分割，或递归线性散列。
动态散列数据结构的文件结构会适应文件大小的变化，因此避免了昂贵的定期文件重组。线性哈希文件通过拆分进行扩展 将一个预定的桶一分为二，通过将两个预定的桶合并为一个来收缩。重建的触发因素取决于方案的风格;它可能是存储桶或负载因子(记录数除以存储桶数)的溢出，超出了预定范围。 在线性哈希中有两种类型的桶，一种是要拆分的，另一种是要拆分的 已经分裂了。虽然可扩展散列只拆分溢出的存储桶，但螺旋散列(又名螺旋存储)在桶上不均匀地分布记录，例如 插入、删除或检索成本高的存储桶最早排队 进行拆分。
线性哈希也已制成可扩展的分布式数据结构 LH。在 LH 中，每个存储桶驻留在不同的服务器上。 LH 本身已扩展，可在存在 失败的存储桶。LH 和 LH 中基于键的操作(插入、删除、更新、读取)和 LH 采用最大常量时间，与存储桶数量无关，因此与记录无关。
算法细节
LH 或 LH* 中的记录由键和内容组成，后者基本上是记录的所有其他属性。它们存储在桶中。例如，在 Ellis 的实现中，存储桶是记录的链接列表。 该文件允许基于键的 CRUD 操作创建或插入、读取、更新和删除，以及扫描所有记录的扫描操作，例如对非键属性执行数据库选择操作。 记录存储在编号以 0 开头的存储桶中。
哈希函数
为了使用键访问记录{\displaystyle c}，一系列哈希函数，称为 将动态哈希函数共同应用于密钥{\displaystyle c}.在任何时候， 最多两个哈希函数{\displaystyle h_{i}}和{\displaystyle h_{i+1}}被使用。一个典型的 示例使用除模 X 运算。如果原始存储桶数为{\displaystyle n}，则哈希函数族为
{\displaystyle h_{i}(c)\mapsto c{\pmod {N\cdot 2^{i}}}}
文件扩展
当文件通过插入而增长时，它会通过拆分优雅地扩展 一个桶变成两个桶。要拆分的存储桶顺序是预先确定的。 这是与Fagin可扩展哈希等方案的根本区别。 对于两个新存储桶，哈希函数{\displaystyle h_{i}}替换为{\displaystyle h_{i+1}}.要拆分的存储桶编号是 文件状态并调用拆分指针{\displaystyle s}.
拆分控制
每当存储桶溢出时，都可以执行拆分。这是一个不受控制的分裂。 或者，该文件可以监控负载系数，并在任何时候执行拆分 负载系数超过阈值。这是受控分裂。
寻址
寻址基于文件状态，由拆分指针组成{\displaystyle s}和级别{\displaystyle l}.如果级别为{\displaystyle l}，然后是哈希函数 使用的有{\displaystyle h_{l}}和{\displaystyle h_{l+1}}.
用于哈希键的 LH 算法{\displaystyle c}是{\displaystyle a：=h_{l}(c)}
如果{\displaystyle a
分裂
当一个桶被拆分时，拆分指针和可能的级别会根据更新{\displaystyle s：=s+1}
如果{\displaystyle s\geq N\times 2^{l}}:{\displaystyle l+=1，s=0}
文件收缩
如果在受控拆分下，负载系数将下降到阈值以下，则合并操作 被触发。合并操作将撤消上次拆分，同时重置文件状态。
文件状态计算
文件状态由拆分指针组成{\displaystyle s}和级别{\displaystyle l}.如果 原始文件开头为{\displaystyle N=1}存储桶，然后是存储桶的数量{\displaystyle n}并且文件状态通过相关{\displaystyle n=2^{l}+s}
LH*
LH 的主要贡献是允许 LH 文件的客户端找到其中的存储桶 即使客户端不知道文件状态，记录也会驻留。事实存储中的客户端 他们的文件状态版本，最初只是第一个存储桶(即存储桶 0)的知识。根据其文件状态，客户端计算 键，并向该存储桶发送请求。在存储桶中，检查请求以及是否 记录不在存储桶中，而是转发。在一个相当稳定的系统中，也就是说， 如果在处理请求时只有一个拆分或合并正在进行，则可以 显示最多有两个前锋。转发后，最后一个存储桶发送 图像调整 向状态现在更接近已分发文件状态的客户端发送的消息。虽然远期对活跃客户来说相当罕见， 它们的数量可以通过 服务器和客户端
语言系统的采用
Griswold和Townsend 讨论了在图标语言中采用线性散列。他们讨论了线性散列中使用的动态数组算法的实现替代方案，并使用 Icon 基准测试应用程序列表进行了性能比较。
在数据库系统中的采用
线性散列用于伯克利数据库系统(BDB)，而许多软件系统又使用C实现，使用源自CACM文章的C实现，并于1988年由Esmond Pitt首次发布在Usenet上。
原文地址：
https://en.wikipedia.org/wiki/Linear_hashing
在知识共享 署名-相同方式共享 3.0协议之条款下提供
