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