线性哈希计算？
Linear Hashing calculation?
我目前正在备考，遇到了这个问题：
(5d) 假设我们正在使用线性哈希，并从一个空的 table 开始，有 2 个桶（M = 2），split = 0，负载因子为 0.9。解释我们在添加以下哈希值（按顺序）时所经历的步骤：
5,7,12,11,9
为此提供的答案是：
*— —5— (0,1)
* — —5,7 —
- 拆分 —*—5,7— — (0,1,2)
—12*—5,7— — —
- 拆分—12—5—*—7—(0,1,2,3)
- 拆分=M，M=2*M，拆分=0
*—12—5— —7—
*—12—5— —7,11—
- 拆分 —*—5— —7,11—12— (0,1,2,3,4)
—*—5,9— —7,11—12—
- 拆分— —9*— —7,11—12—5— (0,1,2,3,4,5)
这个答案对我来说没有任何意义，讲师也没有经历过这个。
我该如何解决这个问题？
我编辑了你的问题，因为答案看起来像是执行每个操作时散列 table 状态的描述列表。您的教授是否涵盖了线性哈希？ Wikipedia description mention a load factor precisely, but it's in the original LH paper by Witold Litwin。当发生受控分裂时，它是不可或缺的。我还找到了这些描述：
Let l denote the Linear Hashing scheme’s load factor, i.e., l = S/b where S is the total number of records and b is the number of buckets used.
Linear Hashing 张等 (PDF)
- The linear hashing algorithm performs splits in a deterministic order, rather than splitting at a bucket that overflowed. The splits are performed in linear order (bucket 0 first, then bucket 1, then 2, ...), and a split is performed when any bucket overflows. If the bucket that overflows is not the bucket that is split (which is the common case), overflow techniques such as chaining are used, but the common case is that few overflow buckets are needed.
snip
- Instead of splitting on every collision, you can do a split when the "load" (which is bytes stored / (num buckets * bucket size), i.e. utilization of the data structure) crosses some watermark. This is called controlled splitting; the previously described is called uncontrolled splitting.
Linear Hashing: A new Tool for File and Table Addressing Witold Litwin，摘要作者：Steve Gribble 和 Armando Fox，在线 Berkley.edu 于 6 月 16 日检索
所以基本上，负载因子是一种可预测地控制何时发生拆分的方法。线性散列的一种实现似乎称为 'uncontrolled split'，它会添加一个新桶并在发生冲突时执行拆分。使用 0.9 的负载因子只会在 table 的桶中的 90% 已满时发生拆分 - 或者更确切地说，根据桶被统一分配给的预测将满。
根据这篇文章和我刚刚阅读的维基百科文章，设置是这样的：
- Table 最初是空的，有两个桶 (N = 2)
- -（编号为 0 和 1）
- N 对于 n 个桶对我来说比 M 更有意义，所以我在回答中使用了它。
- 显然 N 从未改变，即使新的桶被添加到 table。
- 我们的增长因子（L 桶 level）为 0。每次 [=364 中的每个桶都会递增=] 被拆分了一次，这与我们的 table 大小翻倍的时间一致。
- 步长指针S（也称为分割指针）指向第0个桶。它指示接下来将对哪个桶应用拆分。
这遵循我上面链接的维基百科文章描述。现在我们需要介绍散列和桶分配。
- 对于您希望具有正态分布的整数，一个体面的哈希函数是只使用整数本身。所以对于输入整数 I，我们的散列 H(I) 就是 I。我认为这跟在答案键后面，这很好，因为这个问题在不知道 H.
的情况下是无法回答的
- 要确定整数 I 添加到哪个桶，将使用两个函数值之一，具体取决于赋值指向 [=81 之前还是之后=]S。
- 首先，计算H(I)
mod (N x 2L), 这实际上只是 I mod (N x 2L)。为了简洁起见，我将在下面称其为 B(I)（也用于 bucket）。称其为分配地址 A.
- 如果A大于或等于S，我们将输入I赋值给地址 A 并继续前进。
- 如果A (B(I))小于S，我们实际上使用不同的散列函数，我将调用 B'(I)，计算为 I
mod (N x 2L + 1),给我们一个实际的分配地址A'.
- 我认为这样做的原因是即使桶在途中被分割，也会更多地保持对桶的分配，但我没有其重要性的数学证明。
我认为上面答案中的*表示分割指针的位置S。在我对下面问题的其余部分的记法中：
- 让
- 表示一个空桶，i 表示一个包含整数 i 的桶，i,j 表示一个包含 i 和 j 在里面。
- 所以你的答案“— —5— (0,1)”的第一步是说桶 0 是空的，桶 1 中有 5 个。为了清楚起见，我将其重写为
- 5。
我认为您的答案细分如下：
- table 加 5。
- 线性哈希算法将其放入第二个桶（索引 1），因为：
- B(5) = 5
mod (2 x 20) = 5 mod ( 2 x 1) = 5 mod 2 = 1
- 1大于S，还是0，所以我们用1作为地址。
- Table 现在有
- 5（第 0 个桶是空的，第 1 个桶里面有 5 个。
- N、L、S不变
将 table 加 7。
- B(7) = 7
mod 2 = 1，所以7和5加到同一个bucket中。S 仍然没有改变，所以再次使用 1 作为地址。
- Table 现在有
- 5,7
- 分裂发生！不是因为桶溢出了，而是因为超过了负载因子。添加了 2 个项目，总共 2 个桶，2/2 = 1.0 > 0.9 = 进行拆分。
- 首先在 table.
的末尾添加一个新的桶
- S 递增为 1。N 不递增。 L不变
- 拆分是在桶上完成的。拆分意味着桶中的所有项目都会根据新的哈希 table 大小重新计算其分配。但是，线性哈希的一个关键是实际的桶是按顺序拆分的，因此即使第 1 个桶已满，第 0 个桶也会被拆分。
- Post 拆分，table 现在是
- 5,7 -，桶 0 和 2 是空的，1 仍然有 5 和 7。
将 12 添加到 table。
- B(12) = 12
mod (2 x 20) = 12 mod 2 = 0
- S为1，B(12)为0，所以我们计算B'(12) 而不是我们的地址。
- 很巧，这是12
mod(2 x 20 + 1)=12mod4，还是0，所以12是添加到第 0 个存储桶。
- Table 现在有
12 5,7 -，只有第 3 个，新桶是空的。
- 再次分裂，因为3/3 = 1.0 > 0.9。这次拆分肯定会比上次更有趣！
- 一个新的桶被添加到 table 的末尾，给我们
12 5,7 - -
- S = 1，所以
5,7的桶被拆分。这意味着为 5 和 7 选择了新的桶。
- 将 S 增加到 2。这是在选择拆分目标桶之后，但在分配新桶之前完成的。这确保了新的 table 分布更均匀（同样，我的假设，没有证据）。
- 5
mod 2 = 1, 1 < S, 计算 5 mod 2 x 21 = 5 mod 4 = 1. 5 被重新分配给同一个桶。
- 7
mod 2 = 1, 1 < S, 计算 7 mod 2 x 21 = 7 mod 4 = 3. 7 被重新分配给 3.
- Table 现在有
12 5 - 7
- S = 2，N 仍然等于 2，L 仍然 = 0。 S 现在已经达到 N x 2L = 2 x 20 = 2，所以 S 重置为 0 并且 L 递增为 1.
在 table 上加 11。
- B(11) = 11
mod (2 x 21) = 11 mod 4 = 3. 11 分配给第 3 个桶。
- Table 现在有
12 5 - 7,11，4 个项目和 4 个桶，因此再次发生拆分。
- S又是0，所以第0个12的bucket在加入新的bucket后重新赋值。 S 在为 12 选择新桶之前递增到 1。
- B(12) = 12
mod (2 x 21) = 12 mod 4 = 0. 0 < 1，所以重新计算
- B'(12) = 12
mod (2 x 21+1) = 12 mod 8 = 4. 12 分配给第 4 个桶。
- Table 现在包含
- 5 - 7,11 12
在 table 上加 9。
我会把最后一步的步骤留给你。我不太了解 LH 算法的一些细微差别。我可能会问有关它们的其他问题。但希望这足以让你继续下去。以后建议直接问课程老师
我目前正在备考，遇到了这个问题：
(5d) 假设我们正在使用线性哈希，并从一个空的 table 开始，有 2 个桶（M = 2），split = 0，负载因子为 0.9。解释我们在添加以下哈希值（按顺序）时所经历的步骤：
5,7,12,11,9
为此提供的答案是：
*— —5— (0,1)
* — —5,7 —
- 拆分 —*—5,7— — (0,1,2)
—12*—5,7— — —
- 拆分—12—5—*—7—(0,1,2,3)
- 拆分=M，M=2*M，拆分=0
*—12—5— —7—
*—12—5— —7,11—
- 拆分 —*—5— —7,11—12— (0,1,2,3,4)
—*—5,9— —7,11—12—
- 拆分— —9*— —7,11—12—5— (0,1,2,3,4,5)
这个答案对我来说没有任何意义，讲师也没有经历过这个。
我该如何解决这个问题？
我编辑了你的问题，因为答案看起来像是执行每个操作时散列 table 状态的描述列表。您的教授是否涵盖了线性哈希？ Wikipedia description mention a load factor precisely, but it's in the original LH paper by Witold Litwin。当发生受控分裂时，它是不可或缺的。我还找到了这些描述：
Let l denote the Linear Hashing scheme’s load factor, i.e., l = S/b where S is the total number of records and b is the number of buckets used.
Linear Hashing 张等 (PDF)
- The linear hashing algorithm performs splits in a deterministic order, rather than splitting at a bucket that overflowed. The splits are performed in linear order (bucket 0 first, then bucket 1, then 2, ...), and a split is performed when any bucket overflows. If the bucket that overflows is not the bucket that is split (which is the common case), overflow techniques such as chaining are used, but the common case is that few overflow buckets are needed.
snip
- Instead of splitting on every collision, you can do a split when the "load" (which is bytes stored / (num buckets * bucket size), i.e. utilization of the data structure) crosses some watermark. This is called controlled splitting; the previously described is called uncontrolled splitting.
Linear Hashing: A new Tool for File and Table Addressing Witold Litwin，摘要作者：Steve Gribble 和 Armando Fox，在线 Berkley.edu 于 6 月 16 日检索
所以基本上，负载因子是一种可预测地控制何时发生拆分的方法。线性散列的一种实现似乎称为 'uncontrolled split'，它会添加一个新桶并在发生冲突时执行拆分。使用 0.9 的负载因子只会在 table 的桶中的 90% 已满时发生拆分 - 或者更确切地说，根据桶被统一分配给的预测将满。
根据这篇文章和我刚刚阅读的维基百科文章，设置是这样的：
- Table 最初是空的，有两个桶 (N = 2)
- -（编号为 0 和 1）- N 对于 n 个桶对我来说比 M 更有意义，所以我在回答中使用了它。
- 显然 N 从未改变，即使新的桶被添加到 table。
- 我们的增长因子（L 桶 level）为 0。每次 [=364 中的每个桶都会递增=] 被拆分了一次，这与我们的 table 大小翻倍的时间一致。
- 步长指针S（也称为分割指针）指向第0个桶。它指示接下来将对哪个桶应用拆分。
这遵循我上面链接的维基百科文章描述。现在我们需要介绍散列和桶分配。
- 对于您希望具有正态分布的整数，一个体面的哈希函数是只使用整数本身。所以对于输入整数 I，我们的散列 H(I) 就是 I。我认为这跟在答案键后面，这很好，因为这个问题在不知道 H. 的情况下是无法回答的
- 要确定整数 I 添加到哪个桶，将使用两个函数值之一，具体取决于赋值指向 [=81 之前还是之后=]S。
- 首先，计算H(I)
mod(N x 2L), 这实际上只是 Imod(N x 2L)。为了简洁起见，我将在下面称其为 B(I)（也用于 bucket）。称其为分配地址 A. - 如果A大于或等于S，我们将输入I赋值给地址 A 并继续前进。
- 如果A (B(I))小于S，我们实际上使用不同的散列函数，我将调用 B'(I)，计算为 I
mod(N x 2L + 1),给我们一个实际的分配地址A'. - 我认为这样做的原因是即使桶在途中被分割，也会更多地保持对桶的分配，但我没有其重要性的数学证明。
- 首先，计算H(I)
我认为上面答案中的*表示分割指针的位置S。在我对下面问题的其余部分的记法中：
- 让
-表示一个空桶，i表示一个包含整数i的桶，i,j表示一个包含i和j在里面。 - 所以你的答案“— —5— (0,1)”的第一步是说桶 0 是空的，桶 1 中有 5 个。为了清楚起见，我将其重写为
- 5。
我认为您的答案细分如下：
- table 加 5。
- 线性哈希算法将其放入第二个桶（索引 1），因为：
- B(5) = 5
mod(2 x 20) = 5mod( 2 x 1) = 5mod2 = 1 - 1大于S，还是0，所以我们用1作为地址。
- Table 现在有
- 5（第 0 个桶是空的，第 1 个桶里面有 5 个。 - N、L、S不变
将 table 加 7。
- B(7) = 7
mod2 = 1，所以7和5加到同一个bucket中。S 仍然没有改变，所以再次使用 1 作为地址。 - Table 现在有
- 5,7 - 分裂发生！不是因为桶溢出了，而是因为超过了负载因子。添加了 2 个项目，总共 2 个桶，2/2 = 1.0 > 0.9 = 进行拆分。
- 首先在 table. 的末尾添加一个新的桶
- S 递增为 1。N 不递增。 L不变
- 拆分是在桶上完成的。拆分意味着桶中的所有项目都会根据新的哈希 table 大小重新计算其分配。但是，线性哈希的一个关键是实际的桶是按顺序拆分的，因此即使第 1 个桶已满，第 0 个桶也会被拆分。
- Post 拆分，table 现在是
- 5,7 -，桶 0 和 2 是空的，1 仍然有 5 和 7。
- B(7) = 7
将 12 添加到 table。
- B(12) = 12
mod(2 x 20) = 12mod2 = 0 - S为1，B(12)为0，所以我们计算B'(12) 而不是我们的地址。
- 很巧，这是12
mod(2 x 20 + 1)=12mod4，还是0，所以12是添加到第 0 个存储桶。 - Table 现在有
12 5,7 -，只有第 3 个，新桶是空的。 - 再次分裂，因为3/3 = 1.0 > 0.9。这次拆分肯定会比上次更有趣！
- 一个新的桶被添加到 table 的末尾，给我们
12 5,7 - - - S = 1，所以
5,7的桶被拆分。这意味着为 5 和 7 选择了新的桶。 - 将 S 增加到 2。这是在选择拆分目标桶之后，但在分配新桶之前完成的。这确保了新的 table 分布更均匀（同样，我的假设，没有证据）。
- 5
mod2 = 1, 1 < S, 计算 5mod2 x 21 = 5mod4 = 1. 5 被重新分配给同一个桶。 - 7
mod2 = 1, 1 < S, 计算 7mod2 x 21 = 7mod4 = 3. 7 被重新分配给 3. - Table 现在有
12 5 - 7 - S = 2，N 仍然等于 2，L 仍然 = 0。 S 现在已经达到 N x 2L = 2 x 20 = 2，所以 S 重置为 0 并且 L 递增为 1.
- B(12) = 12
在 table 上加 11。
- B(11) = 11
mod(2 x 21) = 11mod4 = 3. 11 分配给第 3 个桶。 - Table 现在有
12 5 - 7,11，4 个项目和 4 个桶，因此再次发生拆分。 - S又是0，所以第0个12的bucket在加入新的bucket后重新赋值。 S 在为 12 选择新桶之前递增到 1。
- B(12) = 12
mod(2 x 21) = 12mod4 = 0. 0 < 1，所以重新计算 - B'(12) = 12
mod(2 x 21+1) = 12mod8 = 4. 12 分配给第 4 个桶。 - Table 现在包含
- 5 - 7,11 12
- B(11) = 11
在 table 上加 9。
我会把最后一步的步骤留给你。我不太了解 LH 算法的一些细微差别。我可能会问有关它们的其他问题。但希望这足以让你继续下去。以后建议直接问课程老师