随着目标集合的增长，循环散列可以保持一致吗？

循环哈希算法在给定一组静态目标的情况下提供一致性。例如：随着目标集合的增长，循环散列可以保持一致吗？

我有一组初始的目标，让我们称他们为A，B和C。
我有钥匙，让我们把它x
我有一个圆形的哈希函数，我们称之为hash(key, targets)
当我打电话hash(x, [A,B,C])，x总是散列到A

似乎很明显。事实上，我总是得到A给定x代表我使用循环散列时所期望的一致性。然而，现在让我们考虑一下，如果我添加一个新的节点D会发生什么：

我的既定目标是重新平衡，以包括A，B，C和D
我重新申请我的钥匙x到hash(x, [A,B,C,D])
因为圈子是平衡的，我不能保证得到A

我是否想念或者我只是运气不好？当您开始对节点重新排序（例如hash(x, [B,A,D,C])），或者如果您在现有节点列表中间插入新节点（例如hash(x, [A,AA,B,C,D])），问题会进一步恶化。我已经对循环散列的学术方面进行了一些研究，这种“扩展一致性”似乎不是它的主要关注点之一。也许我只是使用错误类型的散列算法？

来源

2013-03-08 Jonathan Azoff

对不起，我找不到对循环哈希多的材料。你的意思是一致的哈希和DHT？ – Nayuki 2013-03-08 03:35:14

你的回答恰当地解释了我所理解的“循环散列”。但是，我不认为我更接近真正的解决方案。用“记忆”的概念很容易解决这个问题，即记住过去的密钥散列在哪里。但是，将内存构建到算法中可能是不可能的。该算法必须在密钥被哈希后进行变异。添加新的目标不应该影响过去的密钥被散列的位置。 – 2013-03-08 05:57:02

“因为圆是重新平衡的，所以我不能保证再得到A”所以你说对于已经哈希的项目，它们不应该分配给新的节点？ /“开始对节点重新排序时，问题会进一步恶化”但是在答案中提出的模型中，不存在重新排序节点的问题，因为节点集是无序的。你能解决这两个问题吗？ – Nayuki 2013-03-08 14:28:14

当您展开散列函数的允许输出范围时，它有理由认为某些输入会散列到不同的输出（否则没有扩大范围的点）。否则，唯一的方法是如果散列函数存储所有先前的结果（或者压缩的，可能有损耗的形式，如布卢姆过滤器），以便它可以记住使用“旧”结果进行输入前面看过。

来源

2013-03-08 03:19:28

完全公平的回应。但是，我不想让算法记住任何东西。 – 2013-03-08 06:24:29

我无法以一致的方式解释你的整个问题，所以我会猜测你真正想问什么，并根据这个答案来回答。假设问题：你有一堆对象（例如字符串），并且你有一堆机器，并且你想把每个对象分配给一台机器，以便在机器间传播工作负载。当机器加入或离开机器池时，您不希望重新洗牌太多的对象到机器分配（“缩放一致性”）。

我认为你有一个误解，你说你散列对象x映射池中的机器[A,B,C]。我的理解是，涉及三个中间步骤。

计算每个对象的散列值。假设散列输出空间大到像从0到2的所有整数那样大 - - 1。
为每台机器指定一个值（在相同的编号空间中），并在其生命周期内保持不变。你会想随机分发这些数字。
现在，我们分配每个对象属于最接近的向上机器。这意味着如果对象的散列是x，那么它属于机器M，使得M的值是大于x的最小数。

实施例：

我们有与它们各自的散列4个字符串对象在0至999的范围内：ABC = 314，DEF = 125，GHI = 802，JKL = 001。
我们有3台机器，有这些数字：X = 010，Y = 357，Z = 768。
哪台机器对象abc = 314属于？向上计数，最近的机器是Y = 357。
哪台机器对象ghi = 802属于？向上计数，最近的机器是X = 010。

来源

2013-03-08 03:55:25 Nayuki

这个答案没有任何错误。你对我的意思的假设是完全正确的。但是，我不确定这是否真的回答了我的问题。 – 2013-03-08 06:22:58

对于您的问题有一个相当简单的解决方案。这是一个如何工作的例子。假设你有3个真正的目标（即物理机器）：A，B，C，然后你引入9个虚拟目标：1,2,3,4,5,6,7,8,9，并建立静态从虚拟目标映射到真正的目标是这样的：

1, 2, 3 -> A 
4, 5, 6 -> B 
7, 8, 9 -> C

当你需要一些关键的读/写值，您可以使用杂凑函数首先映射的关键，虚拟目标，然后使用静态虚拟目标映射到实际目标映射如上所示。一旦某个真实目标服务于多个虚拟目标，它应该将它们存储在单独的哈希映射中，因此真实目标B为它所服务的三个虚拟目标提供了三个单独的哈希映射。

现在我们要添加新的实际目标：D.我们首先重新平衡我们的静态映射，例如，像这样：

1, 2, 3 -> A 
4, 5 -> B 
7, 8 -> C 
6, 9 -> D

然后我们转移哈希表，从真正的目标B提供虚拟目标6到新的真正的目标D。我们还将地图服务虚拟目标9从C转移到D。此操作的复杂性为O(n)，其中n是传输值的数量，因为每个真实目标都在单独的哈希映射中为每个虚拟目标服务。

为了具有良好的负载平衡，虚拟目标的数量应该比实际目标的最大可能数目的估计大几倍（例如10倍）。

换句话说，该解决方案的主要思想是使用散列函数将键映射到虚拟目标的数量不变的虚拟目标。然后使用静态映射来将虚拟目标映射到真实目标，并且当真实目标被添加或移除时，该静态映射会改变。

来源

2013-03-08 18:40:36

我不认为这会奏效。这是为什么：使用你的第一个例子，假设'x'哈希到虚拟目标'6'，它散列到真正的目标'C'。现在让我们重新平衡，就像你的第二个例子。在重新平衡之后，'x'仍然映射到虚拟目标'6'，这实际上是一致的。然而，虚拟目标'6'不再映射到真实目标'C'。虽然我可能已经实现了更好的分配，但我没能保持'x'与实际目标'C'之间的相关性。当我们添加新目标时，将关键字与真实目标保持一致，这是我的目标;没有更好的分配。 – 2013-03-08 20:24:55

正如我之前提到的，重新平衡可能需要在真实目标之间移动虚拟目标，这意味着将所有数据从一个真实目标转移到另一个真实目标。 – 2013-03-08 21:02:00

好吧，我想我明白了。

我最终保持了哈希算法的简单性，并使用“校验和”（各种）来确保x总是键入同一个目标。当添加新目标并重新平衡系统时，我只需将所有现有目标通知给重新平衡。这样，如果x散列到目标，它不应该散列，那么目标就可以委托给正确的目标。

谢谢你所有的答复，我可能没有来到这个解决方案，因为它不是为了你所有提供的清晰度。

干杯，

乔恩

来源

2013-03-09 05:06:16

随着目标集合的增长，循环散列可以保持一致吗？

回答

相关问题