一致性 hash 算法

import java.util.ArrayList;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Random;

import java.util.SortedMap;

import java.util.TreeMap;

/**

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

*/

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", "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"};

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

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

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

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[] chars = new String[]{"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",

"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z",

"1","2","3","4","5","6","7","8","9","0"};

Random r = new Random();

Map<String,Integer> map = new HashMap<String,Integer>();

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

int num = r.nextInt(62);

String key = i+chars[num];

String sever = getServer(key);

if(map.get(sever) != null){

map.put(sever, map.get(sever)+1);

}else{

map.put(sever, 1);

}

}

map.forEach((k,v)->{

System.out.println("服务器上"+k+"有"+v+"个 key");

});

List<Integer> array = new ArrayList<Integer>();

map.forEach((k,v)->{

array.add(v);

});

int sum = 0;

for(int i=0;i<array.size();i++){

sum += array.get(i);

}

System.out.println("总和："+sum);

double average = sum/array.size();

System.out.println("平均值："+average);

int total=0;

for(int i=0;i<array.size();i++){

total += (array.get(i)-average)*(array.get(i)-average);

}

double standardDeviation = Math.sqrt(total/array.size());

System.out.println(standardDeviation);

}

}