线性散列

线性散列 (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协议之条款下提供

文章作者: 张拓
文章链接: http://www.xssl.online/%e7%ba%bf%e6%80%a7%e6%95%a3%e5%88%97/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自 张拓的博客
浏览次数: 761

张拓

陕西西安蓝田张拓QQ1070410059。一生所求不过“心安”二字。 然,尘世多纷扰。

发表回复