哈希环法是最常用的、最经典的一致性哈希算法，也叫做割环法。这个算法易于理解、应用广泛（例如亚马逊的Dynamo），实现了最小化的重新映射。
具体的算法：
我们接下来讨论下，当新增和删除槽位时，哈希环的表现如何。
哈希环做到了在槽位数量变化前后的增量式的重新映射，避免了全量的重新映射。
对于空间复杂度，显然是$O(n)$。
实际应用中，还可以对槽位（节点）添加权重。大概的逻辑是构建很多指向真实节点的虚拟节点，也叫影子节点。影子节点之间是平权的，选中影子节点，就代表选中了背后的真实节点。权重越大的节点，影子节点越多，被选中的概率就越大。
下面的图6.2是一个例子，其中$N_0,N_1,N_2,N_3$的权重比是$1:2:3:2$。选中一个影子节点如$V(N_2)$就是选中了$N_2$。
但是需要注意的是，权重的调整会带来数据迁移的工作。
With100replicas(“vnodes”)perserver,thestandarddeviationofloadisabout10%.Increasingthenumberofreplicasto1000pointsperserverreducesthestandarddeviationto~3.2%.
意思是，当有100个影子节点时，哈希环法的映射结果的分布的标准差大约有$10\%$。当影子节点增加到1000个时，这个标准差降到$3.2\%$左右。
如果我们要实现动态扩容和缩容，即所谓的热扩容，不停止服务对系统进行增删节点，可以这样做：
下面的图7.1中演示了这两种规则：
同样的，中继也可以不止一次。下面图7.3中演示了中继两次的情况，如果一个节点上查不到数据，就中继给下一个节点，最多两次中继，这样就可以满足同时添加”两个正好在环上相邻的”节点的情况了。
THE END