第五周作业
发布于: 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详细分布:919711090919033497364976409765011241410433810357195627Process finished with exit code 0
说明:
在第一次实现的时候,用了字符串自带的getHash()方法,结果发现哈希值分布有问题,重新写了方法,好了。
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 46
路人
关注
还未添加个人签名 2018.07.26 加入
还未添加个人简介
评论