一致性 hash 算法的实现

package com.test.hash;

import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;

import org.apache.commons.lang.StringUtils;

/**

* 带虚拟节点的一致性 Hash 算法

*/

public class ConsistentHashWithVirtualNode {

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

private static String[] servers = {"192.168.2.0:111", "192.168.2.1:111", "192.168.2.2:111",

"192.168.2.3:111", "192.168.2.4:111"};

private static List<String> realNodes = new LinkedList<String>();

//虚拟节点，key 表示虚拟节点的 hash 值，value 表示虚拟节点的名称

private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

//虚拟节点的数目，这里写死，一个真实结点对应 10 个虚拟节点

private static final int VIRTUAL_NODES = 10;

static{

//先把原始的服务器添加到真实结点列表中

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

realNodes.add(servers[i]);

for (String str : realNodes){

for(int i=0; i<VIRTUAL_NODES; i++){

String virtualNodeName = str + "&&VN" + String.valueOf(i);

int hash = getHash(virtualNodeName);

virtualNodes.put(hash, virtualNodeName);

}

}

}

//使用 FNV132HASH 算法计算服务器的 Hash 值

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 String getServer(String key){

//得到该 key 的 hash 值

int hash = getHash(key);

// 得到大于该 Hash 值的所有 Map

SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);

String virtualNode;

if(subMap.isEmpty()){

//如果没有比该 key 的 hash 值大的，则从第一个 node 开始

Integer i = virtualNodes.firstKey();

//返回对应的服务器

virtualNode = virtualNodes.get(i);

}else{

//第一个 Key 就是顺时针过去离 node 最近的那个结点

Integer i = subMap.firstKey();

//返回对应的服务器

virtualNode = subMap.get(i);

}

//virtualNode 虚拟节点名称要截取一下

if(StringUtils.isNotBlank(virtualNode)){

return virtualNode.substring(0, virtualNode.indexOf("&&"));

}

return null;

}

public static void main(String[] args){

String[] keys = {"key1", "key2", "key3", "key4", "key5"};

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

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

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

}

}