第五周课后练习

一致性 hash 算法的 java 实现

public class ConsistentHashingWithoutVirtualNode {

//待添加入 Hash 环的服务器列表

private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111",

"192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111" };

//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]);

System.out.println("[" + servers[i] + "]加入集合中, 其 Hash 值为" + hash);

sortedMap.put(hash, servers[i]);

}

System.out.println();

}

//得到应当路由到的结点

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);

}

}

//使用 FNV132HASH 算法计算服务器的 Hash 值,这里不使用重写 hashCode 的方法，最终效果没区别

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;

}

public static void main(String[] args) {

String[] keys = {"太阳", "月亮", "星星"};

for(int i=0; i<keys.length; i++)

System.out.println("[" + keys[i] + "]的 hash 值为" + getHash(keys[i])

+ ", 被路由到结点[" + getServer(keys[i]) + "]");

}

}