极客大学第五周课后作业

package hash;
 
import java.util.*;
 
/**
 * 一致性Hash算法
 */
public class ConsistentHashingVirtualNode {
 
	//待添加入Hash环的服务器列表
	private static String[] servers = { "192.168.1.111", "192.168.1.113",
			"192.168.1.112", "192.168.1.114", "192.168.1.115" };
 
	//key表示服务器的hash值，value表示服务器
	private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
 
	//程序初始化，将所有的服务器放入sortedMap中
	static {
		for (int i=0; i<servers.length; i++) {
			int hash = getHash(servers[i]);
			sortedMap.put(hash, servers[i]);
		}
	}
 
	//得到应当路由到的结点
	private static String getServer(String key) {
		//得到该key的hash值
		int hash = getHash(key);
		//得到大于该Hash值的所有Map
		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
		if(subMap.isEmpty()){
			//如果没有比该key的hash值大的，则从第一个node开始
			Integer i = sortedMap.firstKey();
			//返回对应的服务器
			return sortedMap.get(i);
		}else{
			//第一个Key就是顺时针过去离node最近的那个结点
			Integer i = subMap.firstKey();
			//返回对应的服务器
			return subMap.get(i);
		}
	}
	
	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;
		}
}