第 5 周作业

public class HashUtils {
    /**
     * 使用FNV1_32_HASH算法计算Hash值
     */
    public static long 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;
    }
}

import lombok.Getter;
import lombok.Setter;
import org.apache.commons.lang.StringUtils;
import java.util.ArrayList;
import java.util.List;
/**
 * 服务器节点
 */
@Getter
@Setter
public class Node {
    private Integer id;
    private String name;
    private String uniqueKey;
    private List<Long> hashes;
    public Node(Integer id) {
        this(id, 100);
    }
    public Node(Integer id, int virtualNodeNum) {
        this.id = id;
        this.name = "node-" + id;
        this.uniqueKey = this.name;
        this.hashes = new ArrayList<>(virtualNodeNum);
        for (int i = 0; i < virtualNodeNum; i++) {
            String key = this.uniqueKey + "#" + i;
            this.hashes.add(HashUtils.getHash(StringUtils.reverse(key)));
        }
    }
}

import com.google.common.collect.Lists;
import java.util.*;
public class Cluster {
    private List<Node> nodes = new ArrayList<>();
    private TreeMap<Long, List<Node>> virtualNodes = new TreeMap<>();
    public Cluster(List<Node> nodes) {
        nodes.forEach(node -> this.addNode(node));
    }
    /**
     * 根据key获取集群节点
     * @param key
     * @return
     */
    public Node get(String key){
        if(virtualNodes.size() == 0){
            return null;
        }
        long hash = HashUtils.getHash(key);
        Map.Entry<Long, List<Node>> entry = virtualNodes.higherEntry(hash) == null ? virtualNodes.higherEntry(0L) : virtualNodes.higherEntry(hash);
        return entry.getValue().get(0);
    }
    /**
     * 添加节点
     * @param node
     */
    public void addNode(Node node) {
        nodes.add(node);
        node.getHashes().forEach(hash -> {
            if(virtualNodes.get(hash) == null){
                virtualNodes.put(hash, Lists.newArrayList(node));
            } else {
                virtualNodes.get(hash).add(node);
            }
        });
    }
    /**
     * 移除节点
     * @param node
     */
    public void removeNode(Node node) {
        nodes.removeIf(o -> o.getId().equals(node.getId()));
        node.getHashes().forEach(hash -> {
            List<Node> nodes = virtualNodes.get(hash);
            nodes.removeIf(o -> o.getId().equals(node.getId()));
            if(nodes.size() == 0) {
                virtualNodes.remove(hash);
            }
        });
    }
}

import com.alibaba.fastjson.JSONObject;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

public class ConsistencyHashTest {

    Cluster cluster;

    @Before
    public void setup() {
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            Node node = new Node(i, 100);
            nodes.add(node);
        }

        cluster = new Cluster(nodes);
    }

    @Test
    public void test(){
        long t1 = System.currentTimeMillis();

        int num = 1000000;

        Map<Integer, Integer> nodeKeyNumMap = new HashMap<>();
        for (int i = 0; i < num; i++) {
            String key = UUID.randomUUID().toString();
            Node node = cluster.get(key);
            Integer n = nodeKeyNumMap.get(node.getId());
            if(n == null) {
                nodeKeyNumMap.put(node.getId(), 1);
            } else {
                nodeKeyNumMap.put(node.getId(), n + 1);
            }
        }

        System.out.println(nodeKeyNumMap);

        double[] datas = new double[10];
        for (int i = 0; i < 10; i++) {
            datas[i] = nodeKeyNumMap.get(i) !=null ? nodeKeyNumMap.get(i) : 0;
        }
        System.out.println(JSONObject.toJSONString(datas));

        System.out.println("标准差:" + standardDeviation(datas));

        long t2 = System.currentTimeMillis();
        System.out.println("耗时"+(t2-t1)+"ms");
    }


    /**
     * 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
     * @param datas
     * @return
     */
    public static double variance(double[] datas) {
        int n = datas.length;
        double sum = 0;
        for(int i=0;i<n;i++){//求和
            sum += datas[i];
        }
        double avg = sum / n;//求平均值
        double var = 0;
        for(int i=0;i<n;i++){//求方差
            var += (datas[i]-avg)*(datas[i]-avg);
        }
        return var/n;
    }

    /**
     * 标准差σ=sqrt(variance)
     * @param datas
     * @return
     */
    public static double standardDeviation(double[] datas) {
        return Math.sqrt(variance(datas));
    }

}