用你熟悉的编程语言实现一致性 hash 算法。
    编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

    1. package com.example.design.hash;
    3. import org.springframework.util.StringUtils;
    5. import java.util.LinkedList;
    6. import java.util.List;
    7. import java.util.SortedMap;
    8. import java.util.TreeMap;
    10. /**
    11.  * 带虚拟节点的一致性Hash算法
    12.  */
    13. public class ConsistentHashingWithVirtualNode {
    15.     /**
    16.      * 待添加入Hash环的服务器列表
    17.      */
    18.     public static String[] servers =
    19.         {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111",
    20.             "192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111"};
    22.     private static List<String> realNodes = new LinkedList<>();
    24.     private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
    26.     /**
    27.      * /虚拟节点的数目, 一个真实节点对应的虚拟节点数
    28.      */
    29.     private static final int VIRTUAL_NODES = 100;
    31.     static {
    32.         //先把原始的服务器添加到真实结点列表中
    33.         for (int i = 0; i < servers.length; i++) {
    34.             realNodes.add(servers[i]);
    35.         }
    37.         //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
    38.         for (String str : realNodes) {
    39.             for (int i = 0; i < VIRTUAL_NODES; i++) {
    40.                 String virtualNodeName = str + "&&VN" + String.valueOf(i);
    41.                 int hash = getHash(virtualNodeName);
    42.                 //                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
    43.                 virtualNodes.put(hash, virtualNodeName);
    44.             }
    45.         }
    46.         System.out.println();
    47.     }
    49.     /**
    50.      * 使用FNV1_32_HASH算法计算服务器的Hash值
    51.      * @param str
    52.      * @return
    53.      */
    54.     public static int getHash(String str) {
    55.         final int p = 16777619;
    56.         int hash = (int)2166136261L;
    57.         for (int i = 0; i < str.length(); i++) {
    58.             hash = (hash ^ str.charAt(i)) * p;
    59.         }
    60.         hash += hash << 13;
    61.         hash ^= hash >> 7;
    62.         hash += hash << 3;
    63.         hash ^= hash >> 17;
    64.         hash += hash << 5;
    66.         // 如果算出来的值为负数则取其绝对值
    67.         if (hash < 0) {
    68.             hash = Math.abs(hash);
    69.         }
    70.         return hash;
    71.     }
    73.     /**
    74.      * 获取应当路由到的结点
    75.      * @param key
    76.      * @return
    77.      */
    78.     public static String getServer(String key) {
    79.         //得到该key的hash值  
    80.         int hash = getHash(key);
    81.         // 得到大于该Hash值的所有Map
    82.         SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
    83.         String virtualNode;
    84.         if (subMap.isEmpty()) {
    85.             //如果没有比该key的hash值大的，则从第一个node开始  
    86.             Integer i = virtualNodes.firstKey();
    87.             //返回对应的服务器  
    88.             virtualNode = virtualNodes.get(i);
    89.         } else {
    90.             //第一个Key就是顺时针过去离node最近的那个结点  
    91.             Integer i = subMap.firstKey();
    92.             //返回对应的服务器  
    93.             virtualNode = subMap.get(i);
    94.         }
    95.         //virtualNode虚拟节点名称要截取一下
    96.         if (!StringUtils.isEmpty(virtualNode)) {
    97.             return virtualNode.substring(0, virtualNode.indexOf("&&"));
    98.         }
    99.         return null;
    100.     }
    101. }
    1. package com.example.design.hash;
    3. import java.util.Arrays;
    4. import java.util.Map;
    5. import java.util.TreeMap;
    7. /**
    8.  * @description: 测试 100 万 KV 数据，10 个服务器节点的情况下，
    9.  * 计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
    10.  * @author: jcwang
    11.  * @create: 2020-07-08 10:00
    12.  **/
    13. public class Test {
    15.     /**
    16.      * 计算标准方差
    17.      *
    18.      * @param array
    19.      * @return
    20.      */
    21.     public static double calcStd(Integer[] array) {
    22.         double avg = Arrays.stream(array).mapToInt(Integer::intValue).average().orElse(0d);
    23.         double avgStd =
    24.             Arrays.stream(array).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average()
    25.                 .orElse(0d);
    26.         return Math.sqrt(avgStd);
    27.     }
    29.     public static void main(String[] args) {
    30.         int keyNum = 10000;
    31.         Map<String, Integer> serverCount = new TreeMap<>();
    33.         for (String server : ConsistentHashingWithVirtualNode.servers) {
    34.             serverCount.put(server, 0);
    35.         }
    37.         String serverName = "";
    38.         String key = "";
    39.         for (int i = 0; i < keyNum; i++) {
    40.             key = "key" + System.currentTimeMillis();
    41.             serverName = ConsistentHashingWithVirtualNode.getServer(key);
    42.             serverCount.put(serverName, serverCount.get(serverName) + 1);
    43.         }
    45.         Integer[] array = new Integer[serverCount.size()];
    46.         double rs = calcStd(serverCount.values().toArray(array));
    47.         System.out.println("rs = " + rs);
    49.     }
    50. }

    作业提交地址： https://jinshuju.net/f/0zLWY4