第 5 周 技术选型（一）- 作业

package com.hash;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashing {
	// 服务器列表
	private static String[] servers = { "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111", "192.168.0.5:111", //
			"192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111", "192.168.0.0:111" };
	// 物理节点列表
	private static List<String> realNodesList = Arrays.asList(servers);
	// 虚拟节点的容器，用TreeMap，TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序，
	// 利用tailMap()方法可实现顺时针获取节点
	// key表示虚拟节点的hash值，value表示虚拟节点的名称
	private static SortedMap<Integer, String> virtualNodeContainer = new TreeMap<Integer, String>();
	// 虚拟节点的复制个数，即一个物理节点对应N个虚拟节点，redis的slot数为：16384
	private static final Integer VIRTUAL_NODE_COPIES = 16384;
	// 根据物理节点，添加虚拟节点
	static {
		for (String real : realNodesList) {
			for (int i = 0; i < VIRTUAL_NODE_COPIES; i++) {
				String virtualNodeName = real + "#" + String.valueOf(i);
				int hashCode = getHash(virtualNodeName);
//				System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hashCode);
				virtualNodeContainer.put(hashCode, virtualNodeName);
			}
		}
	}
	public static Integer getVirtualNodeNum() {
		return VIRTUAL_NODE_COPIES;
	}
	/**
	 * 根据传入的内容，获取路由的节点
	 * 
	 * @param content
	 * @return
	 */
	public String getRouteNode(String content) {
		int hashCode = getHash(content);
		// 获取大于该hashCode的所有map
		SortedMap<Integer, String> clockwiseMap = virtualNodeContainer.tailMap(hashCode);
		String virtualNode;
		if (clockwiseMap.isEmpty()) {
			// 如果顺时针该key后没有map，则从virtualNodeContainer第一个node开始
			Integer firstKey = virtualNodeContainer.firstKey();
			virtualNode = virtualNodeContainer.get(firstKey);
		} else {
			// 如果顺时针该key后有map,则取顺时针第一个node
			Integer firstKey = clockwiseMap.firstKey();
			virtualNode = clockwiseMap.get(firstKey);
		}
		return virtualNode;
	}
	/**
	 * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
	 * 
	 * @param str
	 * @return
	 */
	private static int getHash(String str) {
		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;
	}
	// 节点存放数据容器
	private static SortedMap<String, LinkedList<String>> resultContainer = new TreeMap<>();
	public void saveData(String routeNode, String content) {
		LinkedList<String> list = resultContainer.get(routeNode);
		if (list == null) {
			list = new LinkedList<>();
			list.add(content);
		} else {
			list.add(content);
		}
		resultContainer.put(routeNode, list);
	}
	public SortedMap<String, LinkedList<String>> getResultContainer() {
		return resultContainer;
	}
	/**
	 * 标准差σ=sqrt(s^2)
	 * 
	 * @param x
	 * @return
	 */
	public static double getStandardDiviation(List<Double> list) {
		int m = list.size();
		double sum = 0;
		for (int i = 0; i < m; i++) {// 求和
			sum += list.get(i);
		}
		double dAve = sum / m;// 求平均值
		double dVar = 0;
		for (int i = 0; i < m; i++) {// 求方差
			dVar += (list.get(i) - dAve) * (list.get(i) - dAve);
		}
		return Math.sqrt(dVar / m);
	}
	public static void main(String[] args) {
		// 作业1:
		ConsistentHashing consistentHashing = new ConsistentHashing();
		Integer virtualNodeNum = ConsistentHashing.getVirtualNodeNum();
		// 作业2:
		for (int i = 0; i < 1000000; i++) {
			String routeNode = consistentHashing.getRouteNode(String.valueOf(i));
			consistentHashing.saveData(routeNode, String.valueOf(i));
		}
		SortedMap<String, LinkedList<String>> map = consistentHashing.getResultContainer();
		Set<Entry<String, LinkedList<String>>> entrySet = map.entrySet();
		List<Double> list = new ArrayList<>();
		for (Entry<String, LinkedList<String>> entry : entrySet) {
			LinkedList<String> value = entry.getValue();
			Double d = Double.valueOf(value.size());
			list.add(d);
		}
		double standardDiviation = getStandardDiviation(list);
		System.out.println("虚拟节点数：" + virtualNodeNum);
		System.out.println("标准差：" + standardDiviation);
	}
}

虚拟节点数：16384
标准差：6.585452861570997