一致性哈希算法的介绍与实现( 三 ) _一致性哈希算法

可见需要迁移的数据由90%降到了8% ，效果十分可观。那我们再看下数据的分布情况，是否仍然均匀：
/**平均值：100000.00最大值：589675,（589.68%）最小值：227,（0.23%）极差：589448,（589.45%）标准差：77421.44,（77.42%）**/77%的标准差，一个字，崩！这是为啥？我们原本设想的是节点映射到环上时，能将环均匀划分，所以当数据映射到环上时，也将被均匀分布到节点上。而实际情况，由于节点地址相似，映射到环上的位置也将相近，所以造成分布的不均匀，如下图所示：

文章插图

分布不均
由于A、B、C的地址相似，例如：
A: 192.168.1.0B: 192.168.1.1C: 192.168.1.2所以映射的位置相近，那我们可以复制几份A、B、C ，并且通过改变key ，让节点能更均匀的划分环。比如我们在地址后面追加 “-index” 的序号，例如：
A0: 192.168.1.0-0B0: 192.168.1.1-0C0: 192.168.1.2-0A1: 192.168.1.0-1B1: 192.168.1.1-1C1: 192.168.1.2-1虽然A0、B0、C0会相距较近，但是和A1、B1、C1的key具有差别，将能够成功分开，这也正是虚拟节点的作用。达到的效果如下：

文章插图

虚拟节点
下面我们通过代码验证下实际效果：

private static int vNodeNum = 100;public static void consistHashVirtualNodeMain() {    Map<String, Integer> nodeCount = new HashMap<>();    SortedMap<Integer, String> circle = new TreeMap<>();    for (String node : nodes) {        for (int i = 0; i < vNodeNum; i++) {            circle.put(hash(node + "-" + i), node);        }    }    for (Integer data : datas) {        String node = consistHashVirtualNode(data, circle);        if (nodeCount.containsKey(node)) {            nodeCount.put(node, nodeCount.get(node) + 1);        } else {            nodeCount.put(node, 1);        }    }    analyze(nodeCount, dataNum, nodeNum);}/**平均值：100000.00最大值：122931,（122.93%）最小值：74434,（74.43%）极差：48497,（48.50%）标准差：7475.08,（7.48%）**/

可看到标准差已经由77%降到7% ，效果显著。再多做几组实验，标准差随着虚拟节点数的变化如下：