第五周作业

public class ConsistencyHash {
    private final SortedMap<Integer,String> notes;
    private int virtualNoteNumber = 0;
    public ConsistencyHash(){
        notes = new TreeMap<>();
    }
    public ConsistencyHash(int virtualNoteNumber){
        this();
        this.virtualNoteNumber = virtualNoteNumber;
    }
    public ConsistencyHash(List<String> notes,int virtualNoteNumber) {
        this(virtualNoteNumber);
        addNotes(notes);
    }
    public void addNotes(List<String> notes){
        for (String note : notes) {
            if(virtualNoteNumber > 0) {
                for (int i = 0; i < this.virtualNoteNumber; i++) {
                     int noteHash = getHash(note+"###"+i);
                     this.notes.put(noteHash, note);
                     //System.out.println("["+note+"###"+i+"]加入集合，hash值："+noteHash);
                }
            }else{
                int noteHash = getHash(note);
                this.notes.put(noteHash, note);
                //System.out.println("["+note+"]加入集合，hash值："+noteHash);
            }
        }
    }
    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
     */
    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;
    }
    /**
     * 得到路由节点
     * @param key
     * @return
     */
    public String getServer(String key){
        SortedMap<Integer, String> sortedMap = this.notes.tailMap(getHash(key));
        if(sortedMap.size() <= 0){
            sortedMap = this.notes;
        }
        return sortedMap.get(sortedMap.firstKey());
    }
}

public class ConsistencyHashTest {
    public static void main(String[] args) {
        List<String> cacheNotes = new ArrayList<>(10);
        cacheNotes.add("192.168.0.1:8081");
        cacheNotes.add("192.168.0.2:8081");
        cacheNotes.add("192.168.0.3:8081");
        cacheNotes.add("192.168.0.4:8081");
        cacheNotes.add("192.168.0.5:8081");
        cacheNotes.add("192.168.0.6:8081");
        cacheNotes.add("192.168.0.7:8081");
        cacheNotes.add("192.168.0.8:8081");
        cacheNotes.add("192.168.0.9:8081");
        cacheNotes.add("192.168.0.10:8081");
        int[] virtualNumber = new int[]{20,50,100,150,200,500,1000,2000,4000,8000};
        for (int i = 0; i < 10; i++) {
            test(cacheNotes,virtualNumber[i]);
        }
    }
    private static void test(List<String> cacheNotes,int virtualNumber) {
        ConsistencyHash consistencyHash = new ConsistencyHash(cacheNotes,virtualNumber);
        Map<String, AtomicInteger> map = new HashMap<>();
        int [] array = new int[virtualNumber];
        for(int i = 0;i<1000000;i++){
            String server = consistencyHash.getServer(i + "");
            AtomicInteger atomicInteger = map.get(server);
            if(null == atomicInteger){
                atomicInteger = new AtomicInteger();
            }
            atomicInteger.addAndGet(1);
            map.put(server,atomicInteger);
        }
        int i = 0;
        for(String server : map.keySet()){
            array[i] = map.get(server).get();
            //System.out.println("服务器："+server+",存储数量："+map.get(server).get());
            i++;
        }
        System.out.println("虚拟节点数:"+virtualNumber+",标准差："+StandardDiviation(array));
    }
    //标准差σ=sqrt(s^2)
    public static double StandardDiviation(int[] x) {
       int m=x.length;
       double sum=0;
        for(int i=0;i<m;i++){//求和
            sum+=x[i];
        }
        double dAve=sum/m;//求平均值
        double dVar=0;
        for(int i=0;i<m;i++){//求方差
            dVar+=(x[i]-dAve)*(x[i]-dAve);
        }
        return Math.sqrt(dVar/m);
       }
}

虚拟节点数:20,标准差：51652.91375130739
虚拟节点数:50,标准差：40269.389089977514
虚拟节点数:100,标准差：30162.625967246287
虚拟节点数:150,标准差：24993.333392638004
虚拟节点数:200,标准差：21821.283071350317
虚拟节点数:500,标准差：14017.568843704674
虚拟节点数:1000,标准差：9954.714354314743
虚拟节点数:2000,标准差：7054.797328626812