第五周作业 一致性 hash 算法

public interface HashService {
    /**
     *
     * @param key
     * @return
     */
    Long hash(String key);
}
package com.example;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
public class HashServiceImpl implements HashService {
    /**
     * MurMurHash算法,性能高,碰撞率低
     * @param key
     * @return
     */
    @Override
    public Long hash(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 h;
    }
}
package com.example;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
    private final HashService hashService;
    private final int nums;
    private final SortedMap<Long,T> circleMap = new TreeMap<>();
    public ConsistentHash(HashService hashService, int nums, Collection<T> nodes) {
        this.hashService = hashService;
        this.nums = nums;
        for (T node :nodes) {
            addNode(node);
        }
    }
    public void addNode(T node) {
        for (int i = 0; i < this.nums;i++) {
            circleMap.put(this.hashService.hash(node.toString()+i),node);
        }
    }
    public void removeNode(T node) {
        for (int i = 0; i < this.nums;i++){
            circleMap.remove(this.hashService.hash(node.toString()+i),node);
        }
    }
    public T get(String key) {
        if (circleMap.isEmpty()) {
            return null;
        }
        long hash = hashService.hash(key);
        if (!circleMap.containsKey(hash)) {
            SortedMap<Long,T> tailMap = circleMap.tailMap(hash);
            hash = tailMap.isEmpty() ? circleMap.firstKey():tailMap.firstKey();
        }
        return circleMap.get(hash);
    }
}
package com.example;
public class Node<T> {
    /**
     * ip地址
     */
    private String ip;
    /**
     * 名称
     */
    private String name;
    public String getIp() {
        return ip;
    }
    public void setIp(String ip) {
        this.ip = ip;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Node(String ip, String name) {
        this.ip = ip;
        this.name = name;
    }
    @Override
    public String toString() {
        return ip;
    }
}
package com.example;
import java.nio.ByteOrder;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.UUID;
public class HashTest {
    /**
     * 思考
     * 1.构建hash环 2^32-1
     * 2.物理节点如何虚拟化出节点，节点个数是多少个？推荐个数100~200
     * 3.hash函数如何设计？
     *
     * 环和虚拟节点的关系
     * 虚拟节点和物理节点的关系
     *
     *
     * @param args
     */
    /**
     * 机器节点IP前缀
     */
    private static final String IP_PREFIX = "192.168.0.";
    private static final int MACHINE_NUMS = 10;
    public static void main(String[] args) {
        // 每台真实机器节点上保存的记录条数
        Map<String, Integer> map = new HashMap<>();
        // 真实机器节点, 模拟10台
        List<Node<String>> nodes = new ArrayList<Node<String>>();
        for (int i = 1; i <= MACHINE_NUMS; i++) {
            // 初始化记录
            map.put(IP_PREFIX + i, 0);
            Node<String> node = new Node<>(IP_PREFIX + i, "node" + i);
            nodes.add(node);
        }
        HashService iHashService = new HashServiceImpl();
        // 每台真实机器引入100个虚拟节点
        ConsistentHash<Node<String>> consistentHash = new ConsistentHash<Node<String>>(iHashService, 2000, nodes);
        // 将1000000条记录尽可能均匀的存储到10台机器节点上
        for (int i = 0; i < 1000000; i++) {
            // 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
            String data = UUID.randomUUID().toString() + i;
            // 通过记录找到真实机器节点
            Node<String> node = consistentHash.get(data);
            // 每台真实机器节点上保存的记录条数加1
            map.put(node.getIp(), map.get(node.getIp()) + 1);
        }
        double[] x = new double[MACHINE_NUMS];
        // 打印每台真实机器节点保存的记录条数
        for (int i = 1; i <= MACHINE_NUMS; i++) {
            System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get(IP_PREFIX + i));
            x[i-1] = Double.valueOf(map.get(IP_PREFIX + i));
        }
        System.out.println("标准差="+standardDiviation(x));
    }
    /**
     * 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
     * 或者
     * s^2=[(x1-x)^2 +...(xn-x)^2]/(n-1)
     * @param x
     * @return
     */
    public static double variance(double[] 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 dVar/m;
    }
    /**
     * 标准差σ=sqrt(s^2)
     * @param x
     * @return
     */
    public static double standardDiviation(double[] x) {
        return Math.sqrt(variance(x));
    }
}