week5

package test;
import java.util.*;
public class HashTest {
    private static List<String> cluster = new ArrayList<>();
    private static int virtualNodeNum = 150;
    private static Set<VirtualNode> virtualNodeSet = new TreeSet<>();
    public static void main(String[] args) {
        addRedisAddr("redis0");
        addRedisAddr("redis1");
        addRedisAddr("redis2");
        addRedisAddr("redis3");
        addRedisAddr("redis4");
        addRedisAddr("redis5");
        addRedisAddr("redis6");
        addRedisAddr("redis7");
        addRedisAddr("redis8");
        addRedisAddr("redis9");
        Map<String, Integer> countMap = new HashMap<>();
        for (int i = 0; i < 1000000; i++) {
            String randomKey = getRandomString(10);
            VirtualNode node = fetchVirtualNode(randomKey);
            countMap.put(node.realAddr, countMap.getOrDefault(node.realAddr, 0)+1);
        }
        System.out.println(countMap);
        System.out.println("标准差 = " +  StandardDiviation(countMap.values()));
    }
    private static VirtualNode fetchVirtualNode(String key) {
        VirtualNode firstNode = null;
        Integer hash = stringToHash(key);
        for (VirtualNode node : virtualNodeSet) {
            if (node.hashValue > hash) return node;
            if (firstNode == null) firstNode = node;
        }
        return firstNode;
    }
    private static void addRedisAddr(String addr) {
        for (int i = 0; i < virtualNodeNum; i++) {
            String virtualNodeId = "virtual-" + addr + "-" + i;
            virtualNodeSet.add(new VirtualNode(virtualNodeId, addr, stringToHash(virtualNodeId)));
        }
    }
    public static Integer stringToHash(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash > 0 ? hash : (0-hash);
    }
    //随机字符串
    public static String getRandomString(int length){
        String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(62);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }
    //标准差σ=sqrt(s^2)
    public static double StandardDiviation(Collection<Integer> x) {
        int m=x.size();
        double sum=0;
        for(Integer i : x){//求和
            sum+=i;
        }
        double dAve=sum/m;//求平均值
        double dVar=0;
        for(Integer i : x){//求方差
            dVar+=(i-dAve)*(i-dAve);
        }
        //reture Math.sqrt(dVar/(m-1));
        return Math.sqrt(dVar/m);
    }
}
class VirtualNode implements Comparable<VirtualNode>{
    public String nodeId;
    public String realAddr;
    public Integer hashValue;
    public VirtualNode(String nodeId, String realAddr, Integer hashValue) {
        this.nodeId = nodeId;
        this.realAddr = realAddr;
        this.hashValue = hashValue;
        if (hashValue < 0)
            System.out.println(this.toString());
    }
    @Override
    public int compareTo(VirtualNode o) {
        if (o == null) return 1;
        return hashValue - o.hashValue;
    }
    @Override
    public String toString() {
        return "VirtualNode{" +
                "nodeId='" + nodeId + '\'' +
                ", realAddr='" + realAddr + '\'' +
                ", hashValue=" + hashValue +
                '}';
    }
}