线性散列 | 火苗999℃的博客

线性散列 (LH) 是一种动态数据结构，它实现哈希表并一次增加或收缩一个存储桶。它是由Witold Litwin于1980年发明的。巴埃萨-耶茨和索萨-波尔曼对此进行了分析。它是许多称为动态散列的方案中的第一个，例如拉尔森的线性散列与部分扩展，线性散列与优先级分割，线性散列与部分扩展和优先级分割，或递归线性散列。

动态散列数据结构的文件结构会适应文件大小的变化，因此避免了昂贵的定期文件重组。线性哈希文件通过拆分进行扩展将一个预定的桶一分为二，通过将两个预定的桶合并为一个来收缩。重建的触发因素取决于方案的风格;它可能是存储桶或负载因子(记录数除以存储桶数)的溢出，超出了预定范围。在线性哈希中有两种类型的桶，一种是要拆分的，另一种是要拆分的已经分裂了。虽然可扩展散列只拆分溢出的存储桶，但螺旋散列(又名螺旋存储)在桶上不均匀地分布记录，例如插入、删除或检索成本高的存储桶最早排队进行拆分。

线性哈希也已制成可扩展的分布式数据结构 LH。在 LH 中，每个存储桶驻留在不同的服务器上。 LH 本身已扩展，可在存在失败的存储桶。LH 和 LH 中基于键的操作(插入、删除、更新、读取)和 LH 采用最大常量时间，与存储桶数量无关，因此与记录无关。

算法细节

LH 或 LH* 中的记录由键和内容组成，后者基本上是记录的所有其他属性。它们存储在桶中。例如，在 Ellis 的实现中，存储桶是记录的链接列表。该文件允许基于键的 CRUD 操作创建或插入、读取、更新和删除，以及扫描所有记录的扫描操作，例如对非键属性执行数据库选择操作。记录存储在编号以 0 开头的存储桶中。

哈希函数

为了使用键访问记录 $c$ ，一系列哈希函数，称为将动态哈希函数共同应用于密钥 $c$ .在任何时候，最多两个哈希函数 $h_{i}$ 和 $h_{i+1}$ 被使用。一个典型的示例使用除模 X 运算。如果原始存储桶数为 $n$ ，则哈希函数族为

$h_{i}(c)\mapsto c{\pmod {N\cdot 2^{i}}}$

文件扩展

当文件通过插入而增长时，它会通过拆分优雅地扩展一个桶变成两个桶。要拆分的存储桶顺序是预先确定的。这是与Fagin可扩展哈希等方案的根本区别。对于两个新存储桶，哈希函数 $h_{i}$ 替换为 $h_{i+1}$ .要拆分的存储桶编号是文件状态并调用拆分指针 $s$ .

拆分控制

每当存储桶溢出时，都可以执行拆分。这是一个不受控制的分裂。或者，该文件可以监控负载系数，并在任何时候执行拆分负载系数超过阈值。这是受控分裂。

寻址

寻址基于文件状态，由拆分指针组成 $s$ 和级别 $l$ .如果级别为 $l$ ，然后是哈希函数使用的有 $h_{l}$ 和 $h_{l+1}$ .

用于哈希键的 LH 算法 $c$ 是 $a：=h_{l}(c)$
如果 $a<s：a：=h_{l+1}(c)$

分裂

当一个桶被拆分时，拆分指针和可能的级别会根据更新 $s：=s+1$
如果 $s\geq N\times 2^{l}$ : $l+=1，s=0$

文件收缩

如果在受控拆分下，负载系数将下降到阈值以下，则合并操作被触发。合并操作将撤消上次拆分，同时重置文件状态。

文件状态计算

文件状态由拆分指针组成 $s$ 和级别 $l$ .如果原始文件开头为 $N=1$ 存储桶，然后是存储桶的数量 $n$ 并且文件状态通过相关 $n=2^{l}+s$

LH*

LH 的主要贡献是允许 LH 文件的客户端找到其中的存储桶即使客户端不知道文件状态，记录也会驻留。事实存储中的客户端他们的文件状态版本，最初只是第一个存储桶(即存储桶 0)的知识。根据其文件状态，客户端计算键，并向该存储桶发送请求。在存储桶中，检查请求以及是否记录不在存储桶中，而是转发。在一个相当稳定的系统中，也就是说，如果在处理请求时只有一个拆分或合并正在进行，则可以显示最多有两个前锋。转发后，最后一个存储桶发送图像调整向状态现在更接近已分发文件状态的客户端发送的消息。虽然远期对活跃客户来说相当罕见，它们的数量可以通过服务器和客户端