使用一个哈希 Table 改进另一个
Using one Hash Table to Improve another
我正在为期末考试学习我们教授给我们的问题。我不知道如何回答这个问题：
考虑一个具有 n 个值的哈希-table T1，其中我们使用 f(k) = k%n 作为哈希函数和链接作为我们的冲突解决方法。现在，我们想使用相同的散列函数将这些相同的值插入第二个散列-table T2，但应用线性探测（单探测）来解决冲突。你怎么能利用T1来构建T2？
注意：我的回答没有精确解，只有思路。
如果我没理解错的话，我们已经有一个散列table实例T1，里面有n值，并且我们想用它来构建 T2，而不是通常从头开始构建 T2。
因为我们有 n 个值 n 个桶，我们知道散列 table 将被填满。
我的想法#1：
我会遍历 T1 的所有桶。当我在第 m 个桶中找到一串值时，我可以知道所有这些值的散列都是 m，而无需调用哈希函数。所以我可以将所有这些值插入第 m-th、(m+1)-th、(m+ 2) -th ... T2 中的桶，或者如果一个桶被占用，那么我跳过那个桶。
优点是我们永远不必调用哈希函数。
我的想法#2：
我可以在 T1 中看到哪些桶包含很多元素，哪些桶包含很少的元素（如 1-2）。我可以使用此信息来确定理想的插入顺序，以最大限度地减少平均访问时间。不幸的是，我想不出一个具体的方法来确定一个理想的顺序。
示例：
N = 10
values = 10,20,30,40,11,32,13,35,45,19
T1 总是这样（链内顺序无关紧要）：
0 -> {10,20,30,40}
1 -> {11}
2 -> {32}
3 -> {13}
4 -> {}
5 -> {35,45}
6 -> {}
7 -> {}
8 -> {}
9 -> {19}
与 T1 不同，T2 可以根据值的插入顺序而变化。一种可能的 T2，其中访问每个元素需要几个步骤：
0 -> {10} 0 off
1 -> {20} 1 off
2 -> {30} 2 off
3 -> {40} 3 off
4 -> {11} 3 off
5 -> {32} 3 off
6 -> {13} 3 off
7 -> {35} 2 off
8 -> {45} 3 off
9 -> {19} 0 off
另一种可能的 T2，当某些元素可以立即访问，但某些元素确实关闭时：
0 -> {10} 0 off
1 -> {11} 0 off
2 -> {32} 0 off
3 -> {13} 0 off
4 -> {20} 4 off
5 -> {35} 0 off
6 -> {45} 1 off
7 -> {30} 7 off
8 -> {40} 8 off
9 -> {19} 0 off
...hash-table T1 with n values where we have used f(k) = k%n for a hash-function and Chaining as our collision resolution method. Now, we want to insert these same values into a second hash-table T2 using the same hash-function, but apply Linear Probing (Single-Probing) to resolve collisions. How could you take advantage of T1 to build T2?
完全按照要求，f(k) = k%n 是一个非常愚蠢的哈希函数，如：
我们被告知 "n" 是值的数量
如果那是真的并且 n 少于桶的数量，我们会在第 n 个桶被使用后人为地阻止桶；因此，碰撞率将明显高于必要的水平
随着元素被插入或删除 n 次更改，我们无法想象我们会在每次插入或删除单个值时重新散列 table
总而言之，可以安全地假设教授忘记了 s/he 的定义 "n"，并希望 f(k) 中的 n 是桶的数量。
让我们运行...
因为我们知道散列值与存储桶值相匹配，所以我们知道从单个存储桶链接的所有值都已散列到存储桶数组中该存储桶的索引。我们不需要再次调用 f(x) 来为同一个#buckets 生成另一个哈希值。
这无疑是教授所追求的：如果 T2 是使用与 T1 相同数量的桶创建的，那么您可以 运行 对桶索引进行计数器，将所有值复制到到 T2 从同一个桶开始，或者如果正在使用 - 您可以使用线性探测找到下一个桶。您还可以保留一个 next-index-in-T2-that-might-be-free 变量，这样您就不必遍历线性探测已经结束的桶。
因此：您可以避免自己重新散列 k，并通过较少的重复探测来处理冲突。
我正在为期末考试学习我们教授给我们的问题。我不知道如何回答这个问题：
考虑一个具有 n 个值的哈希-table T1，其中我们使用 f(k) = k%n 作为哈希函数和链接作为我们的冲突解决方法。现在，我们想使用相同的散列函数将这些相同的值插入第二个散列-table T2，但应用线性探测（单探测）来解决冲突。你怎么能利用T1来构建T2？
注意：我的回答没有精确解，只有思路。
如果我没理解错的话，我们已经有一个散列table实例T1，里面有n值，并且我们想用它来构建 T2，而不是通常从头开始构建 T2。
因为我们有 n 个值 n 个桶，我们知道散列 table 将被填满。
我的想法#1：
我会遍历 T1 的所有桶。当我在第 m 个桶中找到一串值时，我可以知道所有这些值的散列都是 m，而无需调用哈希函数。所以我可以将所有这些值插入第 m-th、(m+1)-th、(m+ 2) -th ... T2 中的桶，或者如果一个桶被占用，那么我跳过那个桶。
优点是我们永远不必调用哈希函数。
我的想法#2：
我可以在 T1 中看到哪些桶包含很多元素，哪些桶包含很少的元素（如 1-2）。我可以使用此信息来确定理想的插入顺序，以最大限度地减少平均访问时间。不幸的是，我想不出一个具体的方法来确定一个理想的顺序。
示例：
N = 10
values = 10,20,30,40,11,32,13,35,45,19
T1 总是这样（链内顺序无关紧要）：
0 -> {10,20,30,40}
1 -> {11}
2 -> {32}
3 -> {13}
4 -> {}
5 -> {35,45}
6 -> {}
7 -> {}
8 -> {}
9 -> {19}
与 T1 不同，T2 可以根据值的插入顺序而变化。一种可能的 T2，其中访问每个元素需要几个步骤：
0 -> {10} 0 off
1 -> {20} 1 off
2 -> {30} 2 off
3 -> {40} 3 off
4 -> {11} 3 off
5 -> {32} 3 off
6 -> {13} 3 off
7 -> {35} 2 off
8 -> {45} 3 off
9 -> {19} 0 off
另一种可能的 T2，当某些元素可以立即访问，但某些元素确实关闭时：
0 -> {10} 0 off
1 -> {11} 0 off
2 -> {32} 0 off
3 -> {13} 0 off
4 -> {20} 4 off
5 -> {35} 0 off
6 -> {45} 1 off
7 -> {30} 7 off
8 -> {40} 8 off
9 -> {19} 0 off
...hash-table
T1with n values where we have used f(k) = k%n for a hash-function and Chaining as our collision resolution method. Now, we want to insert these same values into a second hash-tableT2using the same hash-function, but apply Linear Probing (Single-Probing) to resolve collisions. How could you take advantage ofT1to buildT2?
完全按照要求，f(k) = k%n 是一个非常愚蠢的哈希函数，如：
我们被告知 "n" 是值的数量
如果那是真的并且
n少于桶的数量，我们会在第 n 个桶被使用后人为地阻止桶；因此，碰撞率将明显高于必要的水平随着元素被插入或删除 n 次更改，我们无法想象我们会在每次插入或删除单个值时重新散列 table
总而言之，可以安全地假设教授忘记了 s/he 的定义 "n"，并希望 f(k) 中的 n 是桶的数量。
让我们运行...
因为我们知道散列值与存储桶值相匹配，所以我们知道从单个存储桶链接的所有值都已散列到存储桶数组中该存储桶的索引。我们不需要再次调用 f(x) 来为同一个#buckets 生成另一个哈希值。
这无疑是教授所追求的：如果 T2 是使用与 T1 相同数量的桶创建的，那么您可以 运行 对桶索引进行计数器，将所有值复制到到 T2 从同一个桶开始，或者如果正在使用 - 您可以使用线性探测找到下一个桶。您还可以保留一个 next-index-in-T2-that-might-be-free 变量，这样您就不必遍历线性探测已经结束的桶。
因此：您可以避免自己重新散列 k，并通过较少的重复探测来处理冲突。