一致性哈希算法实现及案例测试，java 版

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Random;



public class ConsistentHash {

// 虚拟节点long类型ip地址

private List<Long> nodeList = new ArrayList<Long>();

// 虚拟节点对应实际节点long类型ip地址

private Map<Long,Long> nodeMap = new HashMap<Long,Long>();

// 实际节点long类型ip地址对应实际ip地址

private Map<Long,String> ipMap = new HashMap<Long,String>();

/**

* 删除服务器节点，服务器宕机时，虚拟节点也被删除

* @param orgIp 服务器真实ip

* @param virtualNodeNum

*/

public void delNode(String orgIp,int virtualNodeNum) {

Random r = new Random();

r.setSeed(this.ipToLong(this.randomNewIp(orgIp)));

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

long virtual = this.ipToLong(this.randomIp(r));

nodeList.remove(virtual);

nodeMap.remove(virtual);

}

this.sortNodes();

}

/**

* 随机生成ip，用于测试使用

* @return

*/

public String randomIp() {

Random r = new Random();

StringBuilder str = new StringBuilder();

str.append(r.nextInt(256)).append(".").append(r.nextInt(256)).append(".").append(r.nextInt(256)).append(".").append(r.nextInt(256));

return str.toString();

}

/**

* 通过调用方ip获取对应服务ip地址

* @param ip

* @return

*/

public String getNodeIp(String ip) {

return ipMap.get(this.getVirtualNode(ip));

}

/**

* 将服务ip加入集群中

* @param ip

* @param virtualNodeNum

*/

public void setNode(String ip,int virtualNodeNum) {

long longIp = this.ipToLong(this.randomNewIp(ip));

ipMap.put(longIp, ip);

// 生成虚拟节点

this.generateVirtualNodToNodeList(longIp,virtualNodeNum);

this.sortNodes();

}

// 获取服务器的虚拟节点

private long getVirtualNode(String ip) {

long longIp = this.ipToLong(ip);

int low = 0;

int high = nodeList.size()-1;

long node = this.getNextNearestVirtualNode(nodeList, low, high, longIp);

return node;

}

// 顺时针获取距离最近的服务期虚拟节点

private long getNextNearestVirtualNode(List<Long> list,int low,int high,long destNum) {

long node = -1L;

int mid = (low+high) >> 1;

if(destNum < list.get(low)) {

node = nodeMap.get(list.get(low));

return node;

} else if(destNum > list.get(high) && high < list.size()-1) {

node = nodeMap.get(list.get(high+1));

return node;

} else if(destNum > list.get(high) && high == list.size()-1) {

node = nodeMap.get(list.get(low));

return node;

} else if(low > high) {

return node;

}

if(destNum > list.get(mid)) {

low = mid+1;

node = this.getNextNearestVirtualNode(list,low,high,destNum);

} else if(destNum < list.get(mid)) {

high = mid-1;

node = this.getNextNearestVirtualNode(list,low,high,destNum);

} else if(destNum == list.get(mid)){

node = nodeMap.get(destNum);

}

return node;

}

// 将ip地址转化成long类型，即hashcode方法

private long ipToLong(String ipAddress) {

String[] ipAddressInArray=ipAddress.split("\\.");

if(ipAddressInArray.length != 4

|| (Long.parseLong(ipAddressInArray[0]) < 0 || Long.parseLong(ipAddressInArray[0]) > 255)

|| (Long.parseLong(ipAddressInArray[1]) < 0 || Long.parseLong(ipAddressInArray[1]) > 255)

|| (Long.parseLong(ipAddressInArray[2]) < 0 || Long.parseLong(ipAddressInArray[2]) > 255)

|| (Long.parseLong(ipAddressInArray[3]) < 0 || Long.parseLong(ipAddressInArray[3]) > 255)) {

throw new RuntimeException("ip非法");

}

long result = Long.parseLong(ipAddressInArray[0]) << 24 | Long.parseLong(ipAddressInArray[1]) << 16

| Long.parseLong(ipAddressInArray[2]) << 8 | Long.parseLong(ipAddressInArray[3]);

return result;

}

// 生成服务器的虚拟ip

private void generateVirtualNodToNodeList(long orgNode,int virtualNodeNum) {

Random r = new Random();

r.setSeed(orgNode);

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

long virtual = this.ipToLong(this.randomIp(r));

nodeList.add(virtual);

nodeMap.put(virtual,orgNode);

}

}

// 对服务器虚拟ip进行排序

private void sortNodes() {

Collections.sort(nodeList);

}



// 随机生成ip地址，用于生成虚拟节点

private String randomIp(Random r) {

StringBuilder str = new StringBuilder();

str.append(r.nextInt(256)).append(".").append(r.nextInt(256)).append(".").append(r.nextInt(256)).append(".").append(r.nextInt(256));

return str.toString();

}

// 随机生成新的ip地址，用于虚拟调用方ip，扩大随机性

private String randomNewIp(String ip) {

String[] ipInArray=ip.split("\\.");

StringBuilder str = new StringBuilder();

Random r = new Random();

long randomSeed = this.ipToLong(ip);

r.setSeed(Long.parseLong(ipInArray[0])*randomSeed);

str.append(r.nextInt(256)).append(".");

r.setSeed(Long.parseLong(ipInArray[1])*randomSeed);

str.append(r.nextInt(256)).append(".");

r.setSeed(Long.parseLong(ipInArray[2])*randomSeed);

str.append(r.nextInt(256)).append(".");

r.setSeed(Long.parseLong(ipInArray[3])*randomSeed);

str.append(r.nextInt(256));

return str.toString();

}

}



import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;



public class Test {

public static void main(String[] args) {

ConsistentHash c = new ConsistentHash();

// 节点数

int nodeNum = 10;

// 每个节点的虚拟节点数

int virtualNodeNum = 150;

Map<String,Integer> map = new HashMap<String,Integer>();

List<String> ipList = new ArrayList<String>();

// 设置节点

for(int j = 0; j < nodeNum; j++) {

String ip = c.randomIp();

c.setNode(ip,virtualNodeNum);

map.put(ip, 0);

ipList.add(ip);

}

int tmp = 1000000;

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

String testIp = c.randomIp();

String nodeIp = c.getNodeIp(testIp);

int times = map.get(nodeIp);

map.put(nodeIp, ++times);

}

long sum = 0L;

long avg = tmp/nodeNum;

int num = 1;

for(String ip : ipList) {

System.out.println("第"+num+"个ip,ipAddress:"+ip+",获得请求数量"+map.get(ip));

sum += ((map.get(ip)-avg)*(map.get(ip)-avg));

num++;

}

System.out.println("标准差:"+Math.sqrt(sum/nodeNum));

}

}