一致性hash算法Consistent Hashing
对于原有hash算法hash%n
so...
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用于计算耗时,可以直接去掉。