一致性hash算法-java

主要的东西在于hash环，在这个闭环上发生了很多事情，简单的说，常规的hash算法取值后就进行数据存储，而一致性hash对分布式的主机进行了一次取值操作，由计算出来的值先确认主机在环上的位置，再到主机上面存取值

这里用java写了一个破产版的一致性哈希算法，200多行，基本的扩容，删除主机，虚拟节点都囊括到了。最大瑕疵在于为了使用数组来体现环使用java自带的hashCode方法时，会产生负数，代码中取了一个绝对值。
可以用md5,sha等取代

应用场景暂时模拟为memcache的查询

package com.tango.data.method.coinsidenthash;

import java.util.HashMap;
import java.util.Map;

public class CHashMain {
    public static void main(String[] args) {
        RealMachine[] machines = new RealMachine[]{
                new RealMachine("192.168.1.123","a"),
                new RealMachine("192.168.1.128","b"),
                new RealMachine("192.168.155.123","c"),
                new RealMachine("251.168.155.123","d")
        };
        
        Client client = new Client(machines);
        client.put("abc", "first");
        client.put("qwer", "sec");
        client.put("bbc", "thrd");
        client.put("dnsommm", "thrd2");
        client.put("1524", "thrd3");
        client.put("1443", "thrd5");
        
        
        System.out.println(client.get("bbc"));
        System.out.println("rm192.168.155.123");
        client.dropMachine(new RealMachine("192.168.155.123", ""));
        System.out.println(client.get("bbc"));
        client.addMachine(new RealMachine("192.168.155.123", ""));
        client.addMachine(new RealMachine("192.168.155.122", ""));
        client.put("bbc", "thrd");
        System.out.println(client.get("1524"));
        client.put("bbc", "新放的");
        System.out.println(client.get("bbc"));
    }
}

class Client{
    
    private static HashCircle circle = new HashCircle();
    
    public Client(RealMachine[] machines){
        for (RealMachine realMachine : machines) {
            circle.putMachine(realMachine);
        }
    }
    
    public void addMachine(RealMachine machine) {
        circle.putMachine(machine);
    }
    
    public void dropMachine(RealMachine machine) {
        circle.dropMachine(machine);
    }
    
    public void put(Object key, Object obj){
        circle.findMachine(key).putKValue(key.hashCode(), obj);
    }
    
    public Object get(Object key){
        RealMachine machine = circle.findMachine(key);
        if(machine==null){
            return "未查询到值";
        }
        return machine.getValue(key.hashCode());
    }
}

class RealMachine extends Node{
    //主机IP
    private String ip;
    //主机名 也可以用于计算hash
    private String name;
    //模拟cache
    private Map map = new HashMap();
    //虚拟节点数量
    public static final int v_node_num=10;
    //虚拟节点
    private VitualNode[] v_node = new VitualNode[v_node_num];
    
    public RealMachine(String ip, String name) {
        super();
        this.ip = ip;
        this.name = name;
        this.addVNode(ip);
    }
    
    //创建物理主机时添加虚拟节点
    private void addVNode(String ip) {
        for (int i = 0; i < v_node_num; i++) {
            v_node[i] = new VitualNode(ip);
        }
    }
    
    //销毁主机
    public void destroy() {
        for (int i = 0; i < v_node_num; i++) {
            v_node[i] = null;
        }
        v_node = null;
        System.out.println(name+"主机销毁");
    }
    
    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public VitualNode[] getV_node() {
        return v_node;
    }

    public void setV_node(VitualNode[] v_node) {
        this.v_node = v_node;
    }

    public void putKValue(Object hashCode, Object obj) {
        map.put(hashCode, obj);
        System.out.println(ip+"的map"+map);
    }
    
    public Object getValue(Object hashCode){
        System.out.println(ip+"的map获取");
        return map.get(hashCode);
    }
}

class HashCircle{
    //正常是为2的32次方
    private final static int circle_length = 1100;
    //直接用数组把位置定死
    private static Node[] circle = new Node[circle_length];
    //添加机器
    public void putMachine(RealMachine machine) {
        int hash = Math.abs(machine.getIp().hashCode());//瑕疵是取了个整，java的hash方法会返回负数
        int index = hash%circle_length;
        circle[index] = machine;
        this.addVNodes(machine);
//        System.out.println("add machine"+index);
    }
    
    //添加虚拟节点
    public void addVNodes(RealMachine machine){
        //添加时需要分散，直接用环的长度来均分
        int hash = Math.abs(machine.getIp().hashCode());//瑕疵是取了个整，java的hash方法会返回负数
        Node[] vNodes = machine.getV_node();
        for (int i = 0; i < vNodes.length; i++) {
            Node node = vNodes[i];
            int index = hash%circle_length+(i+1)*(circle_length/(vNodes.length+i));
            circle[index%circle_length] = node;
//            System.out.println("add v_node"+index%circle_length);
        }
    }
    
    //模拟宕机
    public void dropMachine(RealMachine machine) {
        machine.destroy();
        int hash = machine.getIp().hashCode();
        int index = hash%circle_length;
        circle[index] = null;
        System.out.println("rm machine"+index);
    }

    //顺时针寻找机器，数组搜索效率比较低，但是可以表现出顺时针或者逆时针的算法
    public RealMachine findMachine(Object key) {
        int hash = Math.abs(key.hashCode());
        int index = hash%circle_length;
        
        Node node = null;
        for(int i=0; i
            node = circle[(i+index)%circle_length];
            if(node!=null){
                break;
            }
        }
        
        if(node instanceof RealMachine){
            System.out.println("找到真实主机");
            return (RealMachine)node;
        }else if(node instanceof VitualNode){
            System.out.println("找到虚拟节点");
            VitualNode v = (VitualNode)node;
            hash = v.getRealKey().hashCode();
            index = Math.abs(hash%circle_length);
            return (RealMachine) circle[index];
        }else{
            return null;
        }
    }
    
    //查找key
    public Object findValue(Object key) {
        RealMachine machine = this.findMachine(key);
        return machine.getValue(key);
    }
    
    //存放key-value
    public void putValue(Object key, Object obj) {
        RealMachine machine = this.findMachine(key);
        machine.putKValue(key, obj);
    }
    
}
//节点
class Node{
}
class VitualNode extends Node{
    private Object realKey;//便于查找到对应真实主机
    public VitualNode(Object key) {
        this.realKey = key;
    }
    public Object getRealKey() {
        return realKey;
    }
}