我想创建一个包含许多（可能是数百个）工作程序（计算实体，也可以根据需要将其称为节点）的哈希表。目的是通过利用并发来加快大型哈希表的创建。实现此目的的一种方法是 Radix 分区（比较论文“优化现代硬件上的主内存连接”）。据我了解，这种方法需要共享内存，这意味着所有工作人员都可以将其结果写入同一内​​存。这里不是这种情况。 每个工人都有自己的记忆力。

问题：如何在此设置中创建（可能很大）哈希表？您如何看待我的想法？

变量：

d -用于构建哈希表的数据集 h（d）

P -在 d 中又名所有分区的集合。每个工作人员使用的数据块。 P 中的单个分区称为 p 。

n - P 中的分区数，它等于工人数，因为每个工人得到一个 p 。

h（p）-单个哈希表，也就是从 p 构建的哈希表。

h（d）-生成的哈希表，是各个哈希表 h（p）的总和。

k -拆分哈希函数 h 的键范围时的零件数。

想法1：

简单方法：每个工作人员都会获得一个分区 p ，从该分区构建一个哈希表，并将其写入自己的内存中。

优势1 ：简单

缺点1：如果 n 很大，并且您想在 h（d）中查找一个值，则必须检查 n 个不同的哈希表。最坏的情况是 n 等于 d 中所有元素的数量。如果是这种情况，您基本上可以对 d 进行顺序扫描。

改进1：为了改进想法1 ，我们可以使用Bloom Filters。布隆过滤器基本上告诉我们哈希是否在 h（p）中（可能出现假阳性，不可能出现假阴性）。如果幸运的话，我们可以避免扫描许多 h（p）来查找密钥。

想法2：

将哈希函数的键范围分为 k 个部分。您现在需要 n * k 个工人。每个工作人员处理一个 p ，但只关心映射到其键范围内部分的键。现在，我们可以尝试将 n 保持在较低水平，这意味着 p 的大小会很大，这是可以的，因为生成的 h（p）仍然很小，因为每个 h（p）仅平均包含 p 中元素的数量 1 / k 。

优势：假设我们将 n 保持很小，例如 n = 3 ，但我们使用较高的 k 。由于工人人数为 n * k ，因此我们仍然可以将工作分配给许多工人。要查找键，我们只需要检查3个不同的哈希表，这很好。由于我们知道键映射的范围，因此我们可以直接检查每个 h（p）范围内的范围。

缺点2：潜在的开销，因为每个工作人员处理大量数据（大 p ），但实际上只使用其中的一小部分（平均1 / k ）。我猜这种方法会比想法1 慢，因为 p 更大。

编辑：

工作人员会将创建的表 h（p）发送给一名工作人员，该工作人员将使用所有 h（p）。 h（d）查找密钥。最后，这里的目标是加快哈希表的构建阶段，同时在探测阶段仍保持良好的速度。