第五周 技术选型 作业一

import java.util.SortedMap;import java.util.TreeMap;
/** * 基于虚拟节点的一致性hash * * @author yingp */public class ConsistentHash {
    /**     * 真实节点     */    private final String[] nodes;    /**     * 一个真实节点对应150个虚拟节点     */    private final static int VIRTUAL_NODE_SIZE = 150;    /**     * 虚拟节点到真实节点的映射，key表示虚拟节点的hash值，value表示真实节点的索引位置     */    private SortedMap<Integer, Integer> virtualNodeMap;
    public ConsistentHash(String[] nodes) {        this.nodes = nodes;        this.virtualNodeMap = new TreeMap<>();        int i = 0;        for (String node : nodes) {            for (int j = 0; j < VIRTUAL_NODE_SIZE; j++) {                String virtualNodeName = String.format("%s->%s", node, j);                virtualNodeMap.put(hashCode(virtualNodeName), i);            }            i++;        }    }
    /**     * FNV1_32_HASH算法     *     * @param str     * @return     */    private static int hashCode(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;    }
    /**     * 根据key值拿到节点     *     * @param key     * @return     */    public String getNode(String key) {        // 得到大于该hash值的所有Map        SortedMap<Integer, Integer> subMap = virtualNodeMap.tailMap(hashCode(key));        Integer nodeIndex = 0;        if (!subMap.isEmpty()) {            // 顺时针选择最近的虚拟结点            nodeIndex = subMap.get(subMap.firstKey());        }        return nodes[nodeIndex];    }}

import java.util.HashMap;import java.util.concurrent.atomic.AtomicInteger;import java.util.stream.Collectors;import java.util.stream.IntStream;
public class Main {    public static void main(String[] args) {        // 测试10个服务器节点        final String[] nodes = new String[]{"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", "192.168.0.10"};        final ConsistentHash hash = new ConsistentHash(nodes);        // 计数器，统计每个节点的命中次数        HashMap<String, AtomicInteger> counter = new HashMap<>(nodes.length);        for (String node : nodes) {            counter.put(node, new AtomicInteger());        }        // 100万次测试        IntStream.range(0, 1000000).mapToObj(String::valueOf).parallel().forEach(i -> {            // 以i为key值，返回命中的节点            String node = hash.getNode(i);            counter.get(node).incrementAndGet();        });        counter.forEach((node, count) -> {            System.out.println(node + "次数：" + count);        });        // 计算标准差        Integer[] counterArr = counter.values().stream().map(AtomicInteger::get).collect(Collectors.toList())                .toArray(new Integer[counter.size()]);        System.out.println("标准差：" + getStandardDeviation(counterArr));    }
    /**     * 计算标准差     *     * @param arr     */    private static double getStandardDeviation(Integer[] arr) {        int len = arr.length;        double sum = 0;        for (int i = 0; i < len; i++) {            sum += arr[i];        }        double avg = sum / len;        double var = 0;        for (int i = 0; i < len; i++) {            var += (arr[i] - avg) * (arr[i] - avg);        }        return Math.sqrt(var / len);    }}

192.168.0.2次数：99704192.168.0.1次数：99212192.168.0.4次数：112385192.168.0.3次数：108530192.168.0.10次数：95650192.168.0.9次数：93799192.168.0.6次数：106480192.168.0.5次数：101454192.168.0.8次数：94226192.168.0.7次数：88560标准差：7018.189068413589