一致性 hash 算法

package com.xgx.hash.utils;

import com.google.common.util.concurrent.AtomicLongMap;import org.apache.commons.lang3.StringUtils;
import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;
/** * @author guixian.xi * @date 2021-01-31 20:23. * @desc */public class UnitHashMatch {
    //服务器列表    private static String[] servers = {            "192.168.0.0", "192.168.0.1", "192.168.0.2",            "192.168.0.3", "192.168.0.4", "192.168.0.5"            , "192.168.0.6", "192.168.0.7", "192.168.0.8"            , "192.168.0.9"};
    //真实结点列表    private static List<String> realNodes = new LinkedList<String>();
    //虚拟节点列表    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
    //虚拟节点的数目，单个节点设置10W个虚拟节点    private static final int VIRTUAL_NODES = 100000;
    static {        //先把原始的服务器添加到真实结点列表中        for (int i = 0; i < servers.length; i++)            realNodes.add(servers[i]);
        //再添加虚拟节点        for (String str : realNodes) {            for (int i = 0; i < VIRTUAL_NODES; i++) {                String virtualNodeName = str + "&&VN" + String.valueOf(i);                int hash = HashUtil.getHash(virtualNodeName);                virtualNodes.put(hash, virtualNodeName);            }        }    }

    /**     * 获取节点     *     * @param key     * @return     */    private static String getServer(String key) {        //得到该key的hash值        int hash = HashUtil.getHash(key);        // 得到大于该Hash值的所有Map        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);        String virtualNode;        if (subMap.isEmpty()) {            //如果没有比该key的hash值大的，则从第一个node开始            Integer i = virtualNodes.firstKey();            //返回对应的服务器            virtualNode = virtualNodes.get(i);        } else {            //第一个Key就是顺时针过去离node最近的那个结点            Integer i = subMap.firstKey();            //返回对应的服务器            virtualNode = subMap.get(i);        }        //截取virtualNode虚拟节点名称        if (StringUtils.isNotBlank(virtualNode)) {            return virtualNode.substring(0, virtualNode.indexOf("&&"));        }        return null;    }
    public static void main(String[] args) {              for (int i = 1; i <= 10; i++) {            match(i);        }    }
    private static void match(int count) {        //key数量        int total = 1000000;
        String[] keys = new String[total];        for (int i = 0; i < total; i++) {            keys[i] = RandomUtil.randomChar(10);        }
        // 初始化真实节点 统计分布        AtomicLongMap<String> atomicLongMap = AtomicLongMap.create();        for (String server : realNodes) {            atomicLongMap.put(server, 0);        }
        //遍历keys        for (String key : keys) {            //根据Key计算出hash后，定位到对应的虚拟服务器            //返回服务器名称            String serverTag = getServer(key);            if (StringUtils.isNotBlank(serverTag)) {                //根据服务器名称，命中统计数量                atomicLongMap.getAndIncrement(serverTag);            }        }
       /* for (String key : atomicLongMap.asMap().keySet()) {
            System.out.println("服务节点：" + key + "，写入数： " + atomicLongMap.get(key));        }*/
        //计算标准差        double standardValue = MatchUtil.standardDiviation(atomicLongMap.asMap().values().toArray(new Long[]{}));
        System.out.println("10个节点，100W个虚拟节点，100W个随机Key写入，第" + count + "次计算标准差为：" + standardValue);    }}

package com.xgx.hash.utils;
/** * @author guixian.xi * @date 2021-01-31 20:25. * @desc */public class HashUtil {
    public static int getHash(String str){        final int p = 16777619;        int hash = (int)2166136261L;        for (int i = 0; i < str.length(); i++)            hash = (hash ^ str.charAt(i)) * p;        hash += hash << 13;        hash ^= hash >> 7;        hash += hash << 3;        hash ^= hash >> 17;        hash += hash << 5;
        // 如果算出来的值为负数则取其绝对值        if (hash < 0)            hash = Math.abs(hash);        return hash;    }}

package com.xgx.hash.utils;
/** * @author guixian.xi * @date 2021-01-31 20:44. * @desc */public class MatchUtil {
    /**     * 传入一个数列x计算平均值     *     * @param x     * @return 平均值     */    public static double average(Long[] x) {        int n = x.length;            //数列元素个数        double sum = 0;        for (double i : x) {        //求和            sum += i;        }        return sum / n;    }
    /**     * 传入一个数列x计算方差     * 方差s^2=[（x1-x）^2+（x2-x）^2+......（xn-x）^2]/（n）（x为平均数）     *     * @param x 要计算的数列     * @return 方差     */    public static double variance(Long[] x) {        int n = x.length;            //数列元素个数        double avg = average(x);    //求平均值        double var = 0;        for (double i : x) {            var += (i - avg) * (i - avg);    //（x1-x）^2+（x2-x）^2+......（xn-x）^2        }        return var / n;    }
    /**     * 传入一个数列x计算标准差     * 标准差σ=sqrt(s^2)，即标准差=方差的平方根     *     * @param x 要计算的数列     * @return 标准差     */    public static double standardDiviation(Long[] x) {        return Math.sqrt(variance(x));    }}

package com.xgx.hash.utils;
import java.util.Random;
/** * @author guixian.xi * @date 2021-01-31 20:59. * @desc */public class RandomUtil {    private static final Random random = new Random();    private static char[] chars = new char[]            {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    public RandomUtil() {    }
    public static Random getRandom() {        return random;    }
    public static String randomChar(int len) {        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; ++i) {            sb.append(chars[random.nextInt(chars.length)]);        }
        return sb.toString();    }
    public static String randomChar() {        return randomChar(8);    }}