week5- 作业一致性 HASH 算法的 JAVA 实现

package work5;
import java.util.*;
public class ConsistentHash {
    public static void main(String[] args) {
        // write your code here
        System.out.println("hello world");
        String[] nodes={"node-00","node-01","node-02","node-03","node-04","node-05","node-06","node-07","node-08","node-09"};
        ConsistentHash ch= new  ConsistentHash(nodes,175);
        double[] cntarray={0,0,0,0,0,0,0,0,0,0} ;
        double var;
        for(long i=0; i<1000000; i++)
        {
            double dvalue=Math.random();
            String keytmp=Double.toString(dvalue);
           // System.out.println("[" +i + "]的hash值为" + ch.getHash(keytmp) + ", 被路由到结点[" + ch.getRealNode(keytmp) + "]");
            long hashtmp=ch.getHash(keytmp);
            String realNode=ch.getRealNode(keytmp);
            //System.out.println(realNode);
            int index=   Integer.parseInt(realNode.substring(6,7));
            cntarray[index]=cntarray[index]+1;
        }
        for(int i=0;i<cntarray.length;i++)
        {
            System.out.println("【物理节点"+i+"】="+cntarray[i]);
        }
        var=MathUtil.variance(cntarray);
        System.out.println("【标准差】="+var);
    }
    //真实的节点列表
    public List<String> realNodes = new LinkedList<String>();
    //每个真实节点对于的虚拟节点数
    public int  virtualNodesCnt ;
    //虚拟节点，key表示虚拟节点在环上的hash值，value表示虚拟节点的名称
    private static SortedMap<Long, String> vNodes = new TreeMap<>();
   //构造函数，初始化
   // 虚拟节点排序空间
    public  ConsistentHash(String[] nodes,int vcnt)
    {
        for(int i=0; i<nodes.length; i++) {
            this.realNodes.add(nodes[i]);
        }
        this.virtualNodesCnt=vcnt;
        for (String realnodename : this.realNodes){
            for(int i=0; i<this.virtualNodesCnt; i++){
                String vNodesName =realnodename+"--"+i;
                long hash = this.getHash(vNodesName);
                //  System.out.println("虚拟节点[" + vNodesName + "]被添加, hash值为" + hash);
                vNodes.put(hash, vNodesName);
            }
        }
        System.out.println();
    }
    //输入字符串KEY ，然后计算出对应的HASH值，找到虚拟节点，然后匹配到物理节点
    public   String getRealNode(String key){
        //得到该key的hash值
        long hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Long, String> subMap = vNodes.tailMap(hash);
        //对应的虚拟节点名称
        String virtualNode;
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            //返回第一个node的hash
            long i = vNodes.firstKey();
            //返回对应的虚拟服务器
            virtualNode = vNodes.get(i);
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            //返回第一个node的hash
            Long i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }
        //virtualNode虚拟节点名称要截取一下
        if(virtualNode!=null ){
            return virtualNode.substring(0, virtualNode.indexOf("--"));
        }
        return null;
    }
    /**
     * 使用的是 FNV1_32_HASH
     */
    public  long  getHash(String  key)  {
        final  int  p  =  16777619;
        int  hash  =  (int)2166136261L;
        for(int  i  =  0;  i  <  key.length();  i++)  {
            hash  =  (hash  ^  key.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;
    }
}