循环散列算法提供给定静态目标集的一致性。例如:
- 我有一组初始目标，我们称它们为
- 我有一个键，命名为
x - 我有一个循环哈希函数，命名为
hash(key, targets) - 当我调用
hash(x, [A,B,C])时，x总是散列到A
A, B和C。似乎很明显。我总是在给定x的情况下得到A，这一事实代表了我在使用循环哈希时所期望的一致性。但是，现在让我们考虑如果添加一个new会发生什么节点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]))时，问题会进一步加剧。我研究了一下循环哈希的学术方面，这种类型的"扩展一致性"似乎并不是它的主要关注点之一。也许我只是用错了哈希算法?
你的问题有一个很简单的解决办法。下面是它如何工作的一个例子。
假设您有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的map从C传输到D。该操作的复杂度为O(n)，其中n为传输的值数，因为每个实目标都在单独的哈希映射中服务于每个虚目标。
为了实现良好的负载平衡，虚拟目标的数量应该比实际目标的最大可能数量估计大几倍(例如10倍)。
换句话说，该方案的主要思想是使用哈希函数将key映射到虚拟目标，其中虚拟目标的数量不变。然后使用静态映射将虚拟目标映射到真实目标，当添加或删除真实目标时，静态映射会发生变化。
当您扩展哈希函数的允许输出范围时，理所当然地，一些输入将被哈希到不同的输出(否则扩展范围就没有意义了)。唯一的方法是，如果哈希函数存储所有以前的结果(或压缩的，可能是有损的形式的相同，像布鲁姆过滤器)，这样它可以记住使用"旧"的结果输入，它已经看到了。
我无法以一致的方式解释你的整个问题，所以我将猜测你真正想问什么并根据它回答。
假设问题:你有一堆对象(例如字符串)和一堆机器，你想把每个对象分配给一台机器，以便在机器之间分散工作负载。当一台机器加入或离开机器池时，您不希望重新洗牌太多的对象到机器分配("缩放一致性")。
我认为你有一个误解，你说你哈希对象x来映射池[A,B,C]中的一台机器。我的理解是有三个中间步骤。
-
计算每个对象的哈希值。假设哈希输出空间是一个很大的值，就像所有从0到2的整数32−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
好的,我想我明白了。
我最终保持散列算法简单，并使用"校验和"(各种)来确保x总是指向相同的目标。当添加新目标并且系统重新平衡时，我只需通知所有现有目标有关重新平衡的信息。这样，如果x散列到一个它不应该再散列到的目标，目标就可以委托给正确的目标。
感谢你们所有的回复，如果不是因为你们提供的清晰，我可能不会得到这个解决方案。
欢呼,Jon