循环散列是否可以随着目标集的增长而保持一致？

Question

循环哈希算法在给定静态目标集的情况下提供一致性。例如：

1. 我有一组最初的目标，让我们称它们为A、B和C。
2. 我有钥匙，我们叫它x
3. 我有一个循环散列函数，让我们称之为hash(key, targets)
4. 当我调用hash(x, [A,B,C])时，x总是散列到A

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

1. 我的目标集被重新平衡，包括A、B、C和D
2. 我将密钥x重新应用于hash(x, [A,B,C,D])
3. 因为循环是重新平衡的，所以我不再保证得到A。

我是错过了什么还是我只是运气不好？当您开始重新排序节点(例如hash(x, [B,A,D,C]))或在现有节点列表的中间插入一个新节点(例如hash(x, [A,AA,B,C,D]))时，问题会进一步恶化。我看了一下循环散列的学术方面，这种类型的“缩放一致性”似乎不是它的主要关注点之一。也许我只是使用了错误的哈希算法？

Answer 1

你的问题有很简单的解决办法。下面是它如何工作的一个例子。

假设您有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

然后将为虚拟目标6服务的散列映射从真实目标B转移到新的真实目标D。同时，我们还将为虚拟目标9服务的映射从C传输到D。该操作具有复杂性O(n)，其中n是传递的值数，因为每个实际目标在单独的散列映射中服务于每个虚拟目标。

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

换句话说，该解决方案的主要思想是使用散列函数将键映射到虚拟目标，其中虚拟目标的数量不发生变化。然后利用静态映射将虚拟目标映射到真实目标，这种静态映射在添加或删除真实目标时发生变化。

Answer 2

当您扩展哈希函数的允许输出范围时，一些输入随后会散列到不同的输出(否则没有扩展范围的意义)，这是合理的。否则的唯一方法是，如果哈希函数存储所有以前的结果(或者是一个压缩的、可能是有损的结果形式，比如Bloom过滤器)，那么它就可以记住对它以前见过的输入使用“旧”结果。

Answer 3

好吧，我想我明白了。

最后，我保持了散列算法的简单性，并使用了一个“校验和”(排序)，以确保x总是指向同一个目标。当添加了一个新的目标，并且系统重新平衡时，我只需通知所有现有的目标有关的再平衡。这样，如果x散列到它不应该再散列的目标，那么目标就可以委托给正确的目标。

谢谢你的所有答复，如果没有你们所提供的明确性，我可能不会提出这个解决办法。

干杯,

琼恩