为什么我们有双重哈希函数 [(hash1(key) + i * hash2(key)) % TABLE_SIZE] 而不是简单的 [(i * hash2(key)) % TABLE_SIZE]？
Why do we have double hashing function as [(hash1(key) + i * hash2(key)) % TABLE_SIZE] but not simply as [(i * hash2(key)) % TABLE_SIZE]?
我几天前学习了双重哈希的符号 [(hash1(key) + i * hash2(key)) % TABLE_SIZE] 。有一个地方想了好几天没明白
Why don't we discard the [hash1(key)] part from the double hashing function and simply make it as [(i * hash2(key)) % TABLE_SIZE]?
我找不到这样做的任何缺点，除了所有哈希码将从 0 开始（当 i = 0 时）。
使用双重散列的主要目的，避免集群，还是可以实现的。
如果有人可以的话，将不胜感激help:D
双重哈希的证明是在关于 h1 和 h2 的一些弱假设下进行的，即它们来自通用家族。您得到的结果是每个操作都需要恒定时间（对于不依赖于 h1 和 h2 选择的每个访问）。
对于 h2 only，您需要加强 h2 的条件或按照规定给出时间限制。选择一个与 1 mod 4 一致的素数 p，设 P* = {1, …, p−1} 为单位集 mod p，并考虑以下平庸但通用的哈希函数族来自 {L, R} × P*。绘制一个随机标量 c ← P* 和一个随机函数 f ← (P* → P*) 并定义
h2((L, x)) = cx mod p
h2((R, x)) = f(x).
这个系列是通用的，因为 (L, x) 键永远不会相互碰撞，并且每隔一对键碰撞的概率恰好为 1/|P*|。对于仅使用 h2 的双重哈希算法来说，这是一个糟糕的选择，因为它在其范围的一半上是线性的，并且线性保留了算术序列。
考虑以下操作顺序。通过插入 (R, 1), …, (R, (p−1)/2) 随机填充散列 table 的一半，然后再插入一半的元素 (L, (p−1)/ 4), …, (L, 1)。 table 负载最多为 3/4，因此一切都应在预期的恒定时间内 运行。然而，考虑一下当我们插入 (L, 1) 时会发生什么。以 1/2 的概率，位置 h2((L, 1)) 被 R 键之一占据。第 ith 个探针 i h2((L, 1)) 命中与 h2((L, i)) 相同的位置，对于 i ≤ (p−1)/4 是有保证的由较早的操作填满。因此，此操作的预期成本在 p 中是线性的，即使密钥序列不依赖于哈希函数，即 unacceptable.
将 h1 放回组合中会破坏此结构。
（呃，这不太行得通，因为预期恒定时间的证明假定了强普遍性，而不是摘要中所述的普遍性。）
这个答案的快速总结：
- 您修改后的版本有实际的性能影响，虽然不是很大。
- 我认为这是因为没有像常规双重散列那样多的不同探测序列，由于 birthday paradox.
而导致一些额外的冲突
现在，真正的答案。 :-)
让我们从一些实证分析开始。如果您从双重散列的“标准”版本切换到您提出的双重散列的变体，会发生什么情况？
我编写了一个 C++ 程序，它为每个元素生成 h1 和 h2 值的统一随机选择。然后它将它们插入到两个不同的双重散列 table 中，一个使用正常方法，一个使用变体。它多次重复此过程并报告每次插入所需的平均探针数。这是我的发现：
#include <iostream>
#include <vector>
#include <random>
#include <utility>
using namespace std;
/* Table size is picked to be a prime number. */
const size_t kTableSize = 5003;
/* Load factor for the hash table. */
const double kLoadFactor = 0.9;
/* Number of rounds to use. */
const size_t kNumRounds = 100000;
/* Random generator. */
static mt19937 generator;
/* Creates and returns an empty double hashing table. */
auto emptyTable(const size_t numSlots) {
return vector<bool>(numSlots, false);
}
/* Simulation of double hashing. Each vector entry represents an item to store.
* The first element of the pair is the value of h1(x), and the second element
* of the pair is the value of h2(x).
*/
auto hashCodes(const size_t numItems) {
vector<pair<size_t, size_t>> result;
uniform_int_distribution<size_t> first(0, kTableSize - 1), second(1, kTableSize - 1);
for (size_t i = 0; i < numItems; i++) {
result.push_back({ first(generator), second(generator) });
}
return result;
}
/* Returns the probe location to use given a number of steps taken so far.
* If modified is true, we ignore h1.
*/
size_t locationOf(size_t tableSize, size_t numProbes, size_t h1, size_t h2, bool modified) {
size_t result = (numProbes == 0 || !modified)? h1 : 0;
result += h2 * numProbes;
return result % tableSize;
}
/* Performs a double-hashing insert, returning the number of probes required to
* settle the element into its place.
*/
size_t insert(vector<bool>& table, size_t h1, size_t h2, bool modified) {
size_t numProbes = 0;
while (table[locationOf(table.size(), numProbes, h1, h2, modified)]) {
numProbes++;
}
table[locationOf(table.size(), numProbes, h1, h2, modified)] = true;
return numProbes + 1; // Count the original location as one probe
}
int main() {
size_t normalProbes = 0, variantProbes = 0;
for (size_t round = 0; round < kNumRounds; round++) {
auto normalTable = emptyTable(kTableSize);
auto variantTable = emptyTable(kTableSize);
/* Insert a collection of items into the table. */
for (auto [h1, h2]: hashCodes(kTableSize * kLoadFactor)) {
normalProbes += insert(normalTable, h1, h2, false);
variantProbes += insert(variantTable, h1, h2, true);
}
}
cout << "Normal probes: " << normalProbes << endl;
cout << "Variant probes: " << variantProbes << endl;
}
输出：
Normal probes: 1150241942
Variant probes: 1214644088
因此，根据经验，修改后的方法看起来会导致放置所有元素所需的探针增加大约 5%。那么，问题是为什么会这样。
对于为什么修改后的版本变慢，我没有一个完整的理论解释，但我对发生了什么有一个合理的猜测。直观上，双重哈希通过为插入的每个元素分配一个随机探测序列来工作，这是 table 槽的某种排列。它不是真正随机的排列，因为并非所有排列都可以实现，但对于“足够随机”的某些定义来说它足够随机（例如，参见 Guibas and Szemendi's "The Analysis of Double Hashing）。
让我们考虑一下插入时会发生什么。按照预期，我们需要查看 h1 之外的探针序列多少次？第一项需要看h2的概率为0。第二项有 1/T 的概率，因为它以 1/T 的概率命中第一个元素。第二个项目有 2/T 的概率，因为它有 2/T 的机会击中前两个项目。更一般地说，使用线性期望，我们可以证明一个项目在一个已经被占用的地方的预期次数由
给出
1/T + 2/T + 3/T + 4/T + ... + (n-1)/T
=(1+2+3+...+(n-1))/T
= n(n-1)/2T
现在，假设我们的散列 table 上的负载因子为 α，即 αT = n。那么预期的碰撞次数为
αT(αT - 1) / 2T
≈ α2T / 2.
换句话说，我们应该期望在使用双哈希时看到相当多的次数需要检查 h2。
现在，当我们查看探针序列时会发生什么？使用传统的双重哈希的不同探测序列的数量是T(T-1)，其中T是table中的槽数。这是因为 h1(x) 有 T 种可能的选择，h2(x) 有 T-1 种选择。
birthday paradox 背后的数学表明一旦大约 √(2T(T-1)) ≈ T√2 项被插入到 table，我们有 50% 的机会其中两个最终将分配有相同的探针序列。这里的好消息是不可能将 T√2 项插入 T 槽哈希 table - 元素比槽多！ - 因此我们看到被分配相同探测序列的元素的可能性相当低。这意味着我们在 table 中遇到的冲突主要是由于具有不同探测序列的元素之间的碰撞，但巧合的是最终落在彼此之上。
另一方面，让我们考虑一下您的变化。从技术上讲，仍然有 T(T-1) 个不同的探针序列。然而，我要争辩说，“有效地”更像是只有 T-1 不同的探针序列。这样做的原因是
- 探针序列并不重要，除非在插入时发生碰撞，并且
- 一旦插入后发生碰撞，给定元素的探测序列完全由其 h2 值决定。
这不是一个严格的论点 - 它更像是一种直觉 - 但它表明我们在选择排列的方式上变化较小。
因为一旦发生碰撞，只有 T-1 个不同的探测序列可供选择，生日悖论表明我们需要看到大约 √(2T) 次碰撞才能找到具有相同值的两个项目h2。事实上，鉴于我们预期，α2T/2 项需要 h2 检查，这意味着我们很有可能找到其位置将由完全相同的 h2 值序列确定的项目。这意味着与“经典”双重哈希相比，我们有了一种新的冲突源：来自 h2 值的冲突相互重叠。
现在，即使我们确实与 h2 值发生冲突，也没什么大不了的。毕竟，在我们到达新插槽之前，只需要一些额外的探测就可以跳过过去放置有相同 h2 值的项目。但我认为这可能是在修改版本中看到的额外探针的来源。
希望对您有所帮助！
再咬一口苹果，这次的普适性很强。留下我的另一个答案，因为这个答案使用 Patrascu 和 Thorup 的结果作为黑匣子（以及您选择的一些深度数论或一些 handwaving），这可能不太令人满意。结果是关于线性探测的，即对于每个 table 大小为 4 的幂的 m，存在一个 2-通用（即强通用）哈希族和一系列操作，使得期望超过随机散列函数，一次操作（简称The Query）探测Theta(√m)个单元格。
为了使用这个结果，我们真的想要一个大小为 p−1 的 table，其中 p 是一个素数，所以固定 m 和不利于线性探测的哈希族 Hm（其函数的辅域为{0, …, m-1}），选择p为大于m的最小素数。 （或者，m 是 4 的幂的要求基本上是为了方便编写证明；这似乎很乏味，但可以将 Patrascu 和 Thorup 的结果推广到其他 table 大小。）定义分布 Hp通过画一个函数h''←Hm然后根据分布独立定义h'的每个值
h'(x) = | h''(x) + 1 with probability m/(p-1)
| m with probability 1/m
...
| p-1 with probability 1/m.
设 K 为字段 mod p，函数 h 的陪域 K* = {1, …, p-1}，K 的单位。除非我搞砸了定义，否则很容易验证Hp 是强普遍的。我们需要引入一些 heavy-duty number theory 来证明 p - m 是 O(m2/3)（这是因为足够大的连续立方体之间存在素数），这意味着对于 Omega(m1/3) 步，我们的长度为 O(√m) 的线性探测序列保持不变，概率恒定，远远超过常数。
现在，为了将这个系列从线性探测破坏器更改为“双”哈希破坏器，我们需要为查询中涉及的密钥命名，假设为 q。 （我们肯定知道它是哪一个，因为操作顺序不依赖于散列函数。）我们定义一个新的散列函数分布 h 通过像以前一样绘制 h'，绘制 c ← K*，然后定义
h(x) = | c h'(x) if x ≠ q
| c if x = q.
让我们验证一下这仍然是2-universal。给定键 x 和 y 都不等于 q，很明显 (h(x), h(y)) = (c h'(x), c h'(y)) 在 K* × K* 上均匀分布.给定 q 和一些其他键 x，我们检查 (h(q), h(x)) = (c, c h'(x)) 的分布，这是需要的，因为 c 是均匀的，而 h'(x ) 是统一的并且独立于 c，因此 c h'(x) 也是如此。
OK，本次练习的重点终于来了。 The Query 的探测序列将是 c、2c、3c 等。哪些键散列到（例如）2c？它们是满足方程
的x
h(x) = c h'(x) = 2c
我们从中得出
h'(x) = 2,
即，其首选插槽在线性探测顺序中紧随查询之后的键。从 2 推广到 i，我们得出结论，对于 h' 的查询，错误的线性探测序列变成了对于 h 的查询，QED 的错误“双重”散列探测序列。
我几天前学习了双重哈希的符号 [(hash1(key) + i * hash2(key)) % TABLE_SIZE] 。有一个地方想了好几天没明白
Why don't we discard the [hash1(key)] part from the double hashing function and simply make it as [(i * hash2(key)) % TABLE_SIZE]?
我找不到这样做的任何缺点，除了所有哈希码将从 0 开始（当 i = 0 时）。 使用双重散列的主要目的，避免集群，还是可以实现的。
如果有人可以的话，将不胜感激help:D
双重哈希的证明是在关于 h1 和 h2 的一些弱假设下进行的，即它们来自通用家族。您得到的结果是每个操作都需要恒定时间（对于不依赖于 h1 和 h2 选择的每个访问）。
对于 h2 only，您需要加强 h2 的条件或按照规定给出时间限制。选择一个与 1 mod 4 一致的素数 p，设 P* = {1, …, p−1} 为单位集 mod p，并考虑以下平庸但通用的哈希函数族来自 {L, R} × P*。绘制一个随机标量 c ← P* 和一个随机函数 f ← (P* → P*) 并定义
h2((L, x)) = cx mod p
h2((R, x)) = f(x).
这个系列是通用的，因为 (L, x) 键永远不会相互碰撞，并且每隔一对键碰撞的概率恰好为 1/|P*|。对于仅使用 h2 的双重哈希算法来说，这是一个糟糕的选择，因为它在其范围的一半上是线性的，并且线性保留了算术序列。
考虑以下操作顺序。通过插入 (R, 1), …, (R, (p−1)/2) 随机填充散列 table 的一半，然后再插入一半的元素 (L, (p−1)/ 4), …, (L, 1)。 table 负载最多为 3/4，因此一切都应在预期的恒定时间内 运行。然而，考虑一下当我们插入 (L, 1) 时会发生什么。以 1/2 的概率，位置 h2((L, 1)) 被 R 键之一占据。第 ith 个探针 i h2((L, 1)) 命中与 h2((L, i)) 相同的位置，对于 i ≤ (p−1)/4 是有保证的由较早的操作填满。因此，此操作的预期成本在 p 中是线性的，即使密钥序列不依赖于哈希函数，即 unacceptable.
将 h1 放回组合中会破坏此结构。
（呃，这不太行得通，因为预期恒定时间的证明假定了强普遍性，而不是摘要中所述的普遍性。）
这个答案的快速总结：
- 您修改后的版本有实际的性能影响，虽然不是很大。
- 我认为这是因为没有像常规双重散列那样多的不同探测序列，由于 birthday paradox. 而导致一些额外的冲突
现在，真正的答案。 :-)
让我们从一些实证分析开始。如果您从双重散列的“标准”版本切换到您提出的双重散列的变体，会发生什么情况？
我编写了一个 C++ 程序，它为每个元素生成 h1 和 h2 值的统一随机选择。然后它将它们插入到两个不同的双重散列 table 中，一个使用正常方法，一个使用变体。它多次重复此过程并报告每次插入所需的平均探针数。这是我的发现：
#include <iostream>
#include <vector>
#include <random>
#include <utility>
using namespace std;
/* Table size is picked to be a prime number. */
const size_t kTableSize = 5003;
/* Load factor for the hash table. */
const double kLoadFactor = 0.9;
/* Number of rounds to use. */
const size_t kNumRounds = 100000;
/* Random generator. */
static mt19937 generator;
/* Creates and returns an empty double hashing table. */
auto emptyTable(const size_t numSlots) {
return vector<bool>(numSlots, false);
}
/* Simulation of double hashing. Each vector entry represents an item to store.
* The first element of the pair is the value of h1(x), and the second element
* of the pair is the value of h2(x).
*/
auto hashCodes(const size_t numItems) {
vector<pair<size_t, size_t>> result;
uniform_int_distribution<size_t> first(0, kTableSize - 1), second(1, kTableSize - 1);
for (size_t i = 0; i < numItems; i++) {
result.push_back({ first(generator), second(generator) });
}
return result;
}
/* Returns the probe location to use given a number of steps taken so far.
* If modified is true, we ignore h1.
*/
size_t locationOf(size_t tableSize, size_t numProbes, size_t h1, size_t h2, bool modified) {
size_t result = (numProbes == 0 || !modified)? h1 : 0;
result += h2 * numProbes;
return result % tableSize;
}
/* Performs a double-hashing insert, returning the number of probes required to
* settle the element into its place.
*/
size_t insert(vector<bool>& table, size_t h1, size_t h2, bool modified) {
size_t numProbes = 0;
while (table[locationOf(table.size(), numProbes, h1, h2, modified)]) {
numProbes++;
}
table[locationOf(table.size(), numProbes, h1, h2, modified)] = true;
return numProbes + 1; // Count the original location as one probe
}
int main() {
size_t normalProbes = 0, variantProbes = 0;
for (size_t round = 0; round < kNumRounds; round++) {
auto normalTable = emptyTable(kTableSize);
auto variantTable = emptyTable(kTableSize);
/* Insert a collection of items into the table. */
for (auto [h1, h2]: hashCodes(kTableSize * kLoadFactor)) {
normalProbes += insert(normalTable, h1, h2, false);
variantProbes += insert(variantTable, h1, h2, true);
}
}
cout << "Normal probes: " << normalProbes << endl;
cout << "Variant probes: " << variantProbes << endl;
}
输出：
Normal probes: 1150241942
Variant probes: 1214644088
因此，根据经验，修改后的方法看起来会导致放置所有元素所需的探针增加大约 5%。那么，问题是为什么会这样。
对于为什么修改后的版本变慢，我没有一个完整的理论解释，但我对发生了什么有一个合理的猜测。直观上，双重哈希通过为插入的每个元素分配一个随机探测序列来工作，这是 table 槽的某种排列。它不是真正随机的排列，因为并非所有排列都可以实现，但对于“足够随机”的某些定义来说它足够随机（例如，参见 Guibas and Szemendi's "The Analysis of Double Hashing）。
让我们考虑一下插入时会发生什么。按照预期，我们需要查看 h1 之外的探针序列多少次？第一项需要看h2的概率为0。第二项有 1/T 的概率，因为它以 1/T 的概率命中第一个元素。第二个项目有 2/T 的概率，因为它有 2/T 的机会击中前两个项目。更一般地说，使用线性期望，我们可以证明一个项目在一个已经被占用的地方的预期次数由
给出1/T + 2/T + 3/T + 4/T + ... + (n-1)/T
=(1+2+3+...+(n-1))/T
= n(n-1)/2T
现在，假设我们的散列 table 上的负载因子为 α，即 αT = n。那么预期的碰撞次数为
αT(αT - 1) / 2T
≈ α2T / 2.
换句话说，我们应该期望在使用双哈希时看到相当多的次数需要检查 h2。
现在，当我们查看探针序列时会发生什么？使用传统的双重哈希的不同探测序列的数量是T(T-1)，其中T是table中的槽数。这是因为 h1(x) 有 T 种可能的选择，h2(x) 有 T-1 种选择。
birthday paradox 背后的数学表明一旦大约 √(2T(T-1)) ≈ T√2 项被插入到 table，我们有 50% 的机会其中两个最终将分配有相同的探针序列。这里的好消息是不可能将 T√2 项插入 T 槽哈希 table - 元素比槽多！ - 因此我们看到被分配相同探测序列的元素的可能性相当低。这意味着我们在 table 中遇到的冲突主要是由于具有不同探测序列的元素之间的碰撞，但巧合的是最终落在彼此之上。
另一方面，让我们考虑一下您的变化。从技术上讲，仍然有 T(T-1) 个不同的探针序列。然而，我要争辩说，“有效地”更像是只有 T-1 不同的探针序列。这样做的原因是
- 探针序列并不重要，除非在插入时发生碰撞，并且
- 一旦插入后发生碰撞，给定元素的探测序列完全由其 h2 值决定。
这不是一个严格的论点 - 它更像是一种直觉 - 但它表明我们在选择排列的方式上变化较小。
因为一旦发生碰撞，只有 T-1 个不同的探测序列可供选择，生日悖论表明我们需要看到大约 √(2T) 次碰撞才能找到具有相同值的两个项目h2。事实上，鉴于我们预期，α2T/2 项需要 h2 检查，这意味着我们很有可能找到其位置将由完全相同的 h2 值序列确定的项目。这意味着与“经典”双重哈希相比，我们有了一种新的冲突源：来自 h2 值的冲突相互重叠。
现在，即使我们确实与 h2 值发生冲突，也没什么大不了的。毕竟，在我们到达新插槽之前，只需要一些额外的探测就可以跳过过去放置有相同 h2 值的项目。但我认为这可能是在修改版本中看到的额外探针的来源。
希望对您有所帮助！
再咬一口苹果，这次的普适性很强。留下我的另一个答案，因为这个答案使用 Patrascu 和 Thorup 的结果作为黑匣子（以及您选择的一些深度数论或一些 handwaving），这可能不太令人满意。结果是关于线性探测的，即对于每个 table 大小为 4 的幂的 m，存在一个 2-通用（即强通用）哈希族和一系列操作，使得期望超过随机散列函数，一次操作（简称The Query）探测Theta(√m)个单元格。
为了使用这个结果，我们真的想要一个大小为 p−1 的 table，其中 p 是一个素数，所以固定 m 和不利于线性探测的哈希族 Hm（其函数的辅域为{0, …, m-1}），选择p为大于m的最小素数。 （或者，m 是 4 的幂的要求基本上是为了方便编写证明；这似乎很乏味，但可以将 Patrascu 和 Thorup 的结果推广到其他 table 大小。）定义分布 Hp通过画一个函数h''←Hm然后根据分布独立定义h'的每个值
h'(x) = | h''(x) + 1 with probability m/(p-1)
| m with probability 1/m
...
| p-1 with probability 1/m.
设 K 为字段 mod p，函数 h 的陪域 K* = {1, …, p-1}，K 的单位。除非我搞砸了定义，否则很容易验证Hp 是强普遍的。我们需要引入一些 heavy-duty number theory 来证明 p - m 是 O(m2/3)（这是因为足够大的连续立方体之间存在素数），这意味着对于 Omega(m1/3) 步，我们的长度为 O(√m) 的线性探测序列保持不变，概率恒定，远远超过常数。
现在，为了将这个系列从线性探测破坏器更改为“双”哈希破坏器，我们需要为查询中涉及的密钥命名，假设为 q。 （我们肯定知道它是哪一个，因为操作顺序不依赖于散列函数。）我们定义一个新的散列函数分布 h 通过像以前一样绘制 h'，绘制 c ← K*，然后定义
h(x) = | c h'(x) if x ≠ q
| c if x = q.
让我们验证一下这仍然是2-universal。给定键 x 和 y 都不等于 q，很明显 (h(x), h(y)) = (c h'(x), c h'(y)) 在 K* × K* 上均匀分布.给定 q 和一些其他键 x，我们检查 (h(q), h(x)) = (c, c h'(x)) 的分布，这是需要的，因为 c 是均匀的，而 h'(x ) 是统一的并且独立于 c，因此 c h'(x) 也是如此。
OK，本次练习的重点终于来了。 The Query 的探测序列将是 c、2c、3c 等。哪些键散列到（例如）2c？它们是满足方程
的xh(x) = c h'(x) = 2c
我们从中得出
h'(x) = 2,
即，其首选插槽在线性探测顺序中紧随查询之后的键。从 2 推广到 i，我们得出结论，对于 h' 的查询，错误的线性探测序列变成了对于 h 的查询，QED 的错误“双重”散列探测序列。