架构师训练营第五周作业

public interface HashStrategy {
    long getHashCode(String key);
}

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
public class MurmurHashStrategy implements HashStrategy {
    @Override
    public long getHashCode(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;
        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);
        
        long m = 0xc6a4a7935bd1e995L;
        int r = 47;
        long h = seed ^ (buf.remaining() * m);
        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();
            k *= m;
            k ^= k >>> r;
            k *= m;
            h ^= k;
            h *= m;
        }
        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(
               ByteOrder.LITTLE_ENDIAN);
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }
        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;
        buf.order(byteOrder);
        return (int) (h & 0xffffffffL);
    }
}

import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class ConsistentHash {
    private String name;
    public String getName() {
        return name;
    }
    /**
     * 虚拟节点数量
     */
    private int virtualNodeSize;
    public int getVirtualNodeSize() {
        return virtualNodeSize;
    }
    private String VIRTUAL_NODE_SUFFIX="_";
    private TreeMap<Long,Node> virtualNodes=new TreeMap<>();
    private HashStrategy hashStrategy;
    public ConsistentHash(List<Node> nodes,HashStrategy hashStrategy,int virtualNodeSize) {
        this.hashStrategy=hashStrategy;
        name=hashStrategy.getClass().getSimpleName();
        this.virtualNodeSize=virtualNodeSize;
        buildVirtualNodes(nodes);
    }
    private void buildVirtualNodes(List<Node> nodes){
        nodes.forEach(it->{
            for(int i=0;i<virtualNodeSize;i++){
                String key=it.toString()+VIRTUAL_NODE_SUFFIX+i;
                long hash = hashStrategy.getHashCode(key);
                virtualNodes.put(hash,it);
            }
        });
    }
    public Node getNode(String dataKey){
        if(virtualNodes==null)return null;
        long hash=hashStrategy.getHashCode(dataKey);
        if(!virtualNodes.containsKey(hash)){
            Map.Entry<Long,Node> entry=virtualNodes.ceilingEntry(hash);
            if(entry!=null){
               return entry.getValue();
            }else{
                return virtualNodes.firstEntry().getValue();
            }
        }else{
            return virtualNodes.get(hash);
        }
    }
}

@RunWith(JUnit4.class)
public class TestHash {
    @Test
    public void testHash(){
        int circleCount=1000;
        int dataNum=1000000;
        ExecutorService executorService = new ThreadPoolExecutor(5, 10,
                0, TimeUnit.SECONDS,
                new ArrayBlockingQueue<>(circleCount),
                new ThreadPoolExecutor.DiscardPolicy());// 指定拒绝策略
        Map<Integer,Integer> map=new Hashtable<>();
        try {
            CountDownLatch cc=new CountDownLatch(circleCount);
            for (int w=0;w<circleCount;w++) {
                executorService.execute(new Runnable() {
                    @Override
                    public void run() {
                        List<Node> nodeList=new ArrayList<>();
                        for(int i=0;i<10;i++){
                            Node node=new Node();
                            Random r=new Random();
                            node.setIp(r.nextInt(255)+"."+r.nextInt(255)+"."+r.nextInt(255)+"."+r.nextInt(255));
                            node.setPort("3306");
                            nodeList.add(node);
                        }
                        List<String> testDatas=new ArrayList<>(dataNum);
                        for(int j=0;j<dataNum;j++){
                            String uuid= UUID.randomUUID().toString();
                            testDatas.add(uuid);
                        }
                        int kk=0;
                        double min=1000000.0;
                        for(int k=150;k<=200;k=k+10){
                            ConsistentHash consistentHashk=new ConsistentHash(nodeList,new MurmurHashStrategy(),k);
                            double r=statistics(testDatas,consistentHashk);
                            if(r<min){
                                min=r;
                                kk=k;
                            }
                        }
                        System.out.println("虚拟节点数量:"+kk+",平均差:"+min);
                        map.put(kk,(map.get(kk)==null?0:map.get(kk))+1);
                        cc.countDown();
                    }
                });
            }
            cc.await();
            System.out.println("");
            System.out.println("------------------------------");
            map.entrySet().forEach(it->{
                System.out.println("虚拟节点数量:"+it.getKey().toString() + ",平均差最小次数：" +it.getValue());
            });
        } catch (InterruptedException e) {
        }
    }
    public double standardDeviation(Long[] 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);
    }
    private double statistics(List<String> testDatas, ConsistentHash consistentHash){
        Map<Node,Long> dataMap=new HashMap<>();
        for(int j=0;j<testDatas.size();j++){
            String uuid= testDatas.get(j);
            Node node=consistentHash.getNode(uuid);
            dataMap.put(node,dataMap.get(node)==null?0:dataMap.get(node)+1);
        }
        Collection<Long> datas=dataMap.values();
        double result=standardDeviation(datas.toArray(new Long[0]));
        return result;
    }
}

------------------------------
虚拟节点数量:150,平均差最小次数：126
虚拟节点数量:160,平均差最小次数：125
虚拟节点数量:170,平均差最小次数：110
虚拟节点数量:180,平均差最小次数：117
虚拟节点数量:190,平均差最小次数：171
虚拟节点数量:200,平均差最小次数：351