第五周作业

用户头像
路人
关注
发布于: 2020 年 07 月 08 日

代码:

一致性哈希算法的代码实现:

package com.leopo.consistentHashingAlgorithm;

import java.util.*;

/**
* 一致性哈希算法的实现
*/
public class ConsistentHashingAlgo {

/**
* 服务器节点集合
*/
private static List<String> servers = new LinkedList<>();

/**
* 虚拟节点集合
*/
private static SortedMap<Long, String> virtualNodes = new TreeMap<>();

/**
* 每个服务器的虚拟节点数
*/
private static int virtualNodeCount;

static {
virtualNodeCount = 200;
}

public static List<String> getServers() {
return servers;
}

public static void setServers(List<String> servers) {
ConsistentHashingAlgo.servers = servers;
initVirtualNodes();
}

public static Map<Long, String> getVirtualNodes() {
return virtualNodes;
}

/**
* 初始化虚拟节点
*/
public static void initVirtualNodes() {
virtualNodes.clear();
if (servers.size() == 0) {
return;
}
for (String server : servers) {
for (int count = 0; count < virtualNodeCount; count++) {
String virtualNode = server + ":" + count;
virtualNodes.put(getHash(virtualNode),virtualNode);
}
}
}

/**
* 新加服务器节点
* @param server
*/
public static void addServer(String server){
servers.add(server);
for (int count = 0; count < virtualNodeCount; count++) {
String virtualNode = server + ":" + count;
virtualNodes.put(getHash(virtualNode),virtualNode);
}
}

public static int getVirtualNodeCount() {
return virtualNodeCount;
}

public static void setVirtualNodeCount(int virtualNodeCount) {
ConsistentHashingAlgo.virtualNodeCount = virtualNodeCount;
}

/**
* 计算哈希值
* @param key
* @return
*/
private static long getHash(String key) {
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < key.length(); i++)
hash = (hash ^ key.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;
}

/**
* 获取数据对应的服务器节点
* @param key
* @return
*/
public static String getServiceNode(String key){
long hashCode = getHash(key);
SortedMap<Long,String> subMap = virtualNodes.tailMap(hashCode);
String serviceNode;
if(subMap.isEmpty()){
serviceNode = virtualNodes.get(virtualNodes.firstKey());
} else {
serviceNode = subMap.get(subMap.firstKey());
}
return serviceNode.split(":",-1)[0];
}
}


标准差计算的实现:

package com.leopo.consistentHashingAlgorithm;

/**
* 标准差计算
*/
public class StandardDeviation {

public static double compute(int[] nums){
int sum = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
}
double average = sum/nums.length;
int total=0;
for(int i=0;i<nums.length;i++){
total += (nums[i]-average)*(nums[i]-average);
}
double standardDeviation = Math.sqrt(total/nums.length);
return standardDeviation;
}
}


测试主函数:

package com.leopo.consistentHashingAlgorithm;

import java.util.LinkedList;
import java.util.List;

public class Main {

public static void main(String[] args) {

List<String> servers = new LinkedList<String>();
servers.add("172.16.101.1");
servers.add("172.16.101.2");
servers.add("172.16.101.3");
servers.add("172.16.101.4");
servers.add("172.16.101.5");
servers.add("172.16.101.6");
servers.add("172.16.101.7");
servers.add("172.16.101.8");
servers.add("172.16.101.9");
servers.add("172.16.101.10");
ConsistentHashingAlgo.setServers(servers);

int[] results = new int[10];
for(int i = 0 ; i < 1000000;i++){
String serviceNode = ConsistentHashingAlgo.getServiceNode("current is " + i + " num");
int serviceNum = Integer.parseInt(serviceNode.split("\\.",-1)[3]);
results[serviceNum-1]++;
}
/**
* 打印标准差
*/
System.out.println("标准差: " + StandardDeviation.compute(results));
System.out.println("详细分布:");
for(int i : results){
System.out.println(i);
}
}
}


测试结果打印:

标准差: 6807.232036591672
详细分布:
91971
109091
90334
97364
97640
97650
112414
104338
103571
95627

Process finished with exit code 0


说明:

在第一次实现的时候,用了字符串自带的getHash()方法,结果发现哈希值分布有问题,重新写了方法,好了。

用户头像

路人

关注

还未添加个人签名 2018.07.26 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业