【一】一致性hash算法，基本实现分布平衡。
1 package org.ehking.quartz.curator;
2
3 import java.util.SortedMap;
4 import java.util.TreeMap;
5
6 public class ConsistentHashingWithoutVirtualNode {
7 /**
8 * 待添加入Hash环的服务器列表
9 */
10 private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
11 "192.168.0.3:111", "192.168.0.4:111"};
12
13 /**
14 * key表示服务器的hash值，value表示服务器的名称
15 */
16 private static SortedMap<Integer, String> sortedMap =
17 new TreeMap<Integer, String>();
18
19 /**
20 * 程序初始化，将所有的服务器放入sortedMap中
21 */
22 static
23 {
24 for (int i = 0; i < servers.length; i++)
25 {
26 int hash = getHash(servers[i]);
27 System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
28 sortedMap.put(hash, servers[i]);
29 }
30 System.out.println();
31 }
32
33 /**
34 * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
35 */
36 private static int getHash(String str)
37 {
38 final int p = 16777619;
39 int hash = (int)2166136261L;
40 for (int i = 0; i < str.length(); i++)
41 hash = (hash ^ str.charAt(i)) * p;
42 hash += hash << 13;
43 hash ^= hash >> 7;
44 hash += hash << 3;
45 hash ^= hash >> 17;
46 hash += hash << 5;
47
48 // 如果算出来的值为负数则取其绝对值
49 if (hash < 0)
50 hash = Math.abs(hash);
51 return hash;
52 }
53
54 /**
55 * 得到应当路由到的结点
56 */
57 private static String getServer(String node)
58 {
59 // 得到带路由的结点的Hash值
60 int hash = getHash(node);
61 // 得到大于该Hash值的所有Map
62 SortedMap<Integer, String> subMap =
63 sortedMap.tailMap(hash);
64 // 第一个Key就是顺时针过去离node最近的那个结点
65 Integer i = subMap.firstKey();
66 // 返回对应的服务器名称
67 return subMap.get(i);
68 }
69
70 public static void main(String[] args)
71 {
72 String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
73 for (int i = 0; i < nodes.length; i++)
74 System.out.println("[" + nodes[i] + "]的hash值为" +
75 getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
76 }
77 }
View Code
【二】借助虚拟节点，实现分布平衡的hash算法
1 package org.ehking.quartz.curator;
2
3 import java.util.ArrayList;
4 import java.util.HashMap;
5 import java.util.LinkedList;
6 import java.util.List;
7 import java.util.Set;
8 import java.util.SortedMap;
9 import java.util.TreeMap;
10 import java.util.UUID;
11
12 public class ConsistentHashingWithVirtualNode {
13 /**
14 * 待添加入Hash环的服务器列表
15 */
16 private static String[] servers = { "192.168.0.0:111","192.168.0.1:111", "192.168.0.2:111"};
17
18 /**
19 * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
20 */
21 private static List<String> realNodes = new LinkedList<String>();
22 /**
23 * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
24 */
25 private static SortedMap<Integer, String> virtualNodes =
26 new TreeMap<Integer, String>();
27
28 /**
29 * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
30 */
31 private static final int VIRTUAL_NODES = 1000;
32
33 static
34 {
35 // 先把原始的服务器添加到真实结点列表中
36 for (int i = 0; i < servers.length; i++)
37 realNodes.add(servers[i]);
38
39 // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
40 for (String str : realNodes)
41 {
42 for (int i = 0; i < VIRTUAL_NODES; i++)
43 {
44 String virtualNodeName = str + "&&VN" + String.valueOf(i);
45 int hash = getHash(virtualNodeName);
46 System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
47 virtualNodes.put(hash, virtualNodeName);
48 }
49 }
50 System.out.println();
51 }
52
53 /**
54 * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
55 */
56 private static int getHash(String str)
57 {
58 final int p = 16777619;
59 int hash = (int)2166136261L;
60 for (int i = 0; i < str.length(); i++)
61 hash = (hash ^ str.charAt(i)) * p;
62 hash += hash << 13;
63 hash ^= hash >> 7;
64 hash += hash << 3;
65 hash ^= hash >> 17;
66 hash += hash << 5;
67
68 // 如果算出来的值为负数则取其绝对值
69 if (hash < 0)
70 hash = Math.abs(hash);
71 return hash;
72 }
73
74 /**
75 * 得到应当路由到的结点
76 */
77 private static String getServer(String node)
78 {
79 // 得到带路由的结点的Hash值
80 int hash = getHash(node);
81 // 得到大于该Hash值的所有Map
82 SortedMap<Integer, String> subMap =
83 virtualNodes.tailMap(hash);
84 Integer i=null;
85 String virtualNode = null;
86 if(subMap==null||subMap.size()==0){
87 i=virtualNodes.firstKey();
88 virtualNode=virtualNodes.get(i);
89 }else{
90 i = subMap.firstKey();
91 virtualNode= subMap.get(i);
92 }
93 // 第一个Key就是顺时针过去离node最近的那个结点
94
95 // 返回对应的虚拟节点名称，这里字符串稍微截取一下
96 return virtualNode.substring(0, virtualNode.indexOf("&&"));
97 }
98
99 public static void main(String[] args)
100 {
101
102 HashMap<String,Integer> map=new HashMap<String, Integer>();
103 List<String> id=new ArrayList<String>();
104 for(int i=0;i<1000;i++){
105 id.add(UUID.randomUUID().toString().replace("-", ""));
106 //id.add("adasfdsafdsgfdsagdsafdsafdsaf"+i);
107 }
108 for (int i = 0; i < id.size(); i++){
109 String aString=getServer(id.get(i));
110 Integer aInteger=map.get(aString);
111 if(aInteger==null){
112 map.put(aString,1);
113 }else{
114 map.put(aString, aInteger+1);
115 }
116 }
117 Set<String> set= map.keySet();
118 for(String a:set){
119 System.out.println("节点【"+a+"】分配到元素个数为==>"+map.get(a));
120 }
121 }
122 }
View Code
时间： 2024-10-21 15:23:07