1.话不多说直接上代码,原理或详解自行百度即可

import cn.pheker.utils.UtilElapsedTime;

import cn.pheker.utils.UtilLogger;

import cn.pheker.utils.UtilMD5;

import java.util.*;

/**

 * <pre>

 * author    cn.pheker

 * date      2018/3/19 10:20

 * email     1176479642@qq.com

 * desc      一致性哈希算法

 *

 * </pre>

 */

public class ConsistentHashing {

    private static final long MIN_NODE_NUMBER = 0;

    private static final int MAX_NODE_NUMBER = Integer.MAX_VALUE;

    private static int VIRTUAL_NODE_NUMBER;

    //真实节点

    private List<Node> realNodes = new LinkedList<Node>();

    //虚拟节点,hash环

    private SortedMap<Integer, VNode> circle = new TreeMap<Integer, VNode>();

    private ConsistentHashing(int vnNumber) {

        VIRTUAL_NODE_NUMBER = vnNumber;

    }

    public static ConsistentHashing build(int vnNumber) {

        return new ConsistentHashing(vnNumber);

    }

    public ConsistentHashing addNode(Map<String,String> ipPorts) {

        Set<String> ips = ipPorts.keySet();

        Iterator<String> ipite = ips.iterator();

        while(ipite.hasNext()){

            String ip = ipite.next();

            addNode(ip, ipPorts.get(ip));

        }

        return this;

    }

    public ConsistentHashing addNode(String ip, int port) {

        addNode(ip, String.valueOf(port));

        return this;

    }

    public ConsistentHashing addNode(String ip, String port) {

        Node node = new Node(ip, port);

        if (!realNodes.contains(node)) {

            realNodes.add(node);

            UtilLogger.println("[Node]:"+node.toString()+" Hash:"+node.hashFNV1_32());

            //生成VIRTUAL_NODE_NUMBER个虚拟节点

            for (int i = 0; i < VIRTUAL_NODE_NUMBER; i++) {

                VNode vNode = node.createVNode(i);

                circle.put(vNode.hashFNV1_32(), vNode);

                UtilLogger.println("\t[VNode]:"+vNode.toString()+" Hash:"+vNode.hashFNV1_32());

            }

        }

        return this;

    }

    public void removeNode(String ip,String port) {

        Node node = new Node(ip, port);

        for(int i = 0;i<VIRTUAL_NODE_NUMBER;i++) {

            VNode vNode = node.createVNode(i);

            circle.remove(vNode.hashFNV1_32());

        }

        circle.remove(node.hashFNV1_32());

    }

    public VNode getNode(String ip, int port) {

        return getNode(ip, String.valueOf(port));

    }

    public VNode getNode(String ip, String port) {

        Node node = new Node(ip, port);

        int hash = node.hashFNV1_32();

        if(circle.isEmpty()) return null;

        SortedMap<Integer, VNode> tailMap = circle.tailMap(hash);

        int hashKey;

        if (tailMap.isEmpty()) {

            hashKey = circle.firstKey();

        }else {

            hashKey = tailMap.firstKey();

        }//顺时针最近节点

        VNode vNode = circle.get(hashKey);

        UtilLogger.println(String.format("[%s]:%s ==> [%s]:%s",

                node.hashFNV1_32(),node,vNode.hashFNV1_32(),vNode));

        return vNode;

    }

    /**

     * 第个节点都是一个服务器主机

     */

    public class Node {

        String ip;

        String port;

        public Node(String ip, String port) {

            this.ip = ip;

            this.port = port;

        }

        public String getIp() {

            return ip;

        }

        public void setIp(String ip) {

            this.ip = ip;

        }

        public String getPort() {

            return port;

        }

        public void setPort(String port) {

            this.port = port;

        }

        public VNode createVNode(int vnNumber) {

            return new VNode(ip, port, vnNumber);

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            Node vNode = (Node) o;

            return Objects.equals(ip, vNode.ip) &&

                    Objects.equals(port, vNode.port);

        }

        @Override

        public String toString() {

            return ip + ":" + port;

        }

        /**

         *使用FNV1_32_HASH算法计算服务器的Hash值,这里不能重写hashCode的方法

         */

        public int hashFNV1_32(){

            String str = UtilMD5.MD5(this.toString());

            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;

        }

    }

    /**

     * 虚拟节点

     */

    public class VNode extends Node{

        int number;

        public VNode(String ip, String port,int number) {

            super(ip, port);

            this.number = number;

        }

        public Node toNode() {

            return new Node(ip,port);

        }

        @Override

        public boolean equals(Object o) {

            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            if (!super.equals(o)) return false;

            VNode vNode = (VNode) o;

            return number == vNode.number;

        }

        @Override

        public int hashCode() {

            return Objects.hash(number);

        }

        @Override

        public String toString() {

            return ip + ":" + port+"#"+number;

        }

    }

    /**

     * 校验hash分布均匀性

     * @return

     */

    public float check() {

        Set<Integer> ks = circle.keySet();

        int size = ks.size();

        long sum = 0L;

        for (int hash : ks) {

            sum += hash;

        }

        double percent = size == MIN_NODE_NUMBER ? MIN_NODE_NUMBER :

                (100*2*sum/size)/MAX_NODE_NUMBER;

        return Float.valueOf(String.format("%.2f", percent));

    }

    public static void main(String[] args) {

        UtilElapsedTime.test(() -> {

            ConsistentHashing ch = ConsistentHashing.build(3);

            //添加节点

            UtilLogger.println("------------添加节点----------------");

            ch.addNode("10.96.74.187", 80);

            ch.addNode("127.0.0.1", 8080);

            ch.addNode("243.15.155.0", 2150);

            ch.addNode("243.15.155.1", 2150);

            UtilLogger.println("------------是否均匀----------------");

            UtilLogger.println(ch.check() + "%");

            //获取节点

            UtilLogger.println("------------获取节点----------------");

            ch.getNode("10.96.74.187", 80);

            ch.getNode("123.1.122.253", 44);

            ch.getNode("234.67.80.219", 3306);

            return "耗时计算完成";

        });

    }

}

2.结果

------------添加节点----------------

[Node]:10.96.74.187:80 Hash:1695118842

	[VNode]:10.96.74.187:80#0 Hash:1661313686

	[VNode]:10.96.74.187:80#1 Hash:1283046442

	[VNode]:10.96.74.187:80#2 Hash:564332117

[Node]:127.0.0.1:8080 Hash:678080562

	[VNode]:127.0.0.1:8080#0 Hash:1731933288

	[VNode]:127.0.0.1:8080#1 Hash:1369405387

	[VNode]:127.0.0.1:8080#2 Hash:200594664

[Node]:243.15.155.0:2150 Hash:1175061629

	[VNode]:243.15.155.0:2150#0 Hash:134880260

	[VNode]:243.15.155.0:2150#1 Hash:1677894747

	[VNode]:243.15.155.0:2150#2 Hash:522817245

[Node]:243.15.155.1:2150 Hash:1305999210

	[VNode]:243.15.155.1:2150#0 Hash:1193457699

	[VNode]:243.15.155.1:2150#1 Hash:279279823

	[VNode]:243.15.155.1:2150#2 Hash:2115663065

------------是否均匀----------------

98.0%

------------获取节点----------------

[1695118842]:10.96.74.187:80 ==> [1731933288]:127.0.0.1:8080#0

[601034131]:123.1.122.253:44 ==> [1193457699]:243.15.155.1:2150#0

[508181784]:234.67.80.219:3306 ==> [522817245]:243.15.155.0:2150#2

[23.104187ms] 耗时计算完成

Process finished with exit code 0

3.注意事项

代码中用到了几个工具类UtilMD5,UtilLogger换成自己的即可,UtilElapsedTime用于计算耗时,可以直接去掉。

4.参考链接

对一致性Hash算法，Java代码实现的深入研究

 白话解析：一致性哈希算法 consistent hashing

巴特西

一致性hash算法Consistent Hashing

1.话不多说直接上代码,原理或详解自行百度即可

2.结果

3.注意事项

4.参考链接

最新文章

热门文章