第 5 周结构师训练营——作业

public class ConsistentHashWithoutVirtualNode {
	private static String[] servers = {"192.168.0.1:8090","192.168.0.2:8090","192.168.0.3:8090","192.168.0.4:8090",
	"192.168.0.5:80990","192.168.0.6:8090","192.168.0.7:8090","192.168.0.8:8090","192.168.0.9:8090","192.168.0.10:8090"};
	
	//key 表示服务器hash值，value表示服务器 
	private static SortedMap<Integer,String> sortedMap = new TreeMap<Integer,String>();
	
	//sortedMap表示闭型环，初始化将服务器加入到环中
	static {
		for (String server : servers) {
			int hash = getHash(server);
			sortedMap.put(hash, server);
			System.out.println("服务器[" + server + "]加入集合中,对应的hash值为:" + hash);
		}
	}
	
	/**
	 * 获取数据存放的服务器的key
	 * @param str
	 */
	private static Integer getserver(String str) {
		int hash = getHash(str);
		SortedMap<Integer,String> resultMap = sortedMap.tailMap(hash);
		if(null == resultMap || resultMap.isEmpty()) 
			return sortedMap.firstKey();
		else 
			return resultMap.firstKey();
		
	}
	
	/**
	 * 获取key的hash值
	 * @param key
	 * @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;
	}
	
	/**
	 * 生成随机字符串
	 * @param len
	 * @return
	 */
	public static String generatedString(int len) {
		byte[] array = new byte[len];
		new Random().nextBytes(array);
		String str = new String(array,Charset.forName("UTF-8"));
		return str;
	}
	
	public static void main(String[] args) {
		Map<Integer,Integer> countMap = new HashMap<Integer,Integer>();
		for(int i=1;i<=1000000;i++) {
			String str = generatedString(8);
			Integer hash = getserver(str);
			if(countMap.containsKey(hash))
				countMap.put(hash, countMap.get(hash)+1);
			else
				countMap.put(hash, 1);
		}
		double sum = 0;
		for(Integer hash : sortedMap.keySet()) {
			sum += Math.pow(countMap.get(hash)-100000,2);
			System.out.println("服务器["+sortedMap.get(hash)+"]存储数据量为:"+countMap.get(hash)+"占比为:"+(countMap.get(hash)/10000)+"%");
		}
		System.out.println("标准差为:"+(Math.sqrt(sum/10)));
	}
}

public class ConsistentHashUseVirtualNode {
	//服务器列表
	private static String[] servers = {"192.168.0.1:8090","192.168.0.2:8090","192.168.0.3:8090","192.168.0.4:8090",
			"192.168.0.5:80990","192.168.0.6:8090","192.168.0.7:8090","192.168.0.8:8090","192.168.0.9:8090","192.168.0.10:8090"};
	
	//便于生产上伸缩机器,使用LinkedList 存放服务器
	private static List<String> realNode = new LinkedList<String>();
	
	//虚拟节点，key表示hash value对应虚拟节点名称
	private static SortedMap<Integer,String> virtualNode = new TreeMap<Integer,String>();
	
	//设置虚拟节点数
	private static final int vnode = 100;
	
	static{
		//将服务器加入到真实节点列表中
		for(String str : servers) {
			realNode.add(str);
			//创建虚拟节点
			for(int i = 1;i <= vnode ;i++) {
				String serverName = str + "&&VN" + i;
				int hash = getHash(serverName);
				virtualNode.put(hash, serverName);
			}
		}
		
	}
	
	/**
	 * 获取数据存储服务器
	 * @param str
	 * @return
	 */
	private static String getServer(String str) {
		int hash = getHash(str);
		String nodeName = null;
		SortedMap<Integer,String> subMap = virtualNode.tailMap(hash);
		if(null == subMap || subMap.isEmpty()) {
			nodeName = virtualNode.get(virtualNode.firstKey());
			return nodeName.substring(0, nodeName.indexOf("&&"));
		}
		nodeName = subMap.get(subMap.firstKey());
		return nodeName.substring(0, nodeName.indexOf("&&"));	
	}
	
	/**
	 * 获取hash值
	 * @param str
	 * @return
	 */
	private static Integer 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;
	}
	
	/**
	 * 生成随机字符串
	 * @param len
	 * @return
	 */
	public static String generatedString(int len) {
		byte[] array = new byte[len];
		new Random().nextBytes(array);
		String str = new String(array,Charset.forName("UTF-8"));
		return str;
	}
	
	public static void main(String[] args) {
		System.out.println("虚拟节点为: "+vnode+" 的结果为:");
		Map<String,Integer> resultMap = new  HashMap<String,Integer>();
		double sum = 0;
		for(int i = 1; i <= 1000000; i++) {
			String str = generatedString(8);
			String server = getServer(str);
			if(resultMap.containsKey(server)) 
				resultMap.put(server, resultMap.get(server)+1);
			else
				resultMap.put(server, 1);
		}
		for(String name : resultMap.keySet()) {
			sum += Math.pow((resultMap.get(name)-100000), 2);
			System.out.println("服务器[" + name + "]存储数据量为:" + resultMap.get(name)+"占比为:"+(resultMap.get(name)/10000)+"%");
		}
		System.out.println("标准差为:"+Math.sqrt(sum/10));
	}
}