Go语言视频零基础入门到精通

javalearner

代码实现了一致性Hash算法，并加入虚拟节点。

1. package com.baijob.commonTools;
   
2. import java.util.Collection;
   
3. import java.util.SortedMap;
   
4. import java.util.TreeMap;
   
5. /**
   
6. * 一致性Hash算法
   
7. * 算法详解：http://blog.csdn.net/sparkliang/article/details/5279393
   
8. * 算法实现：https://weblogs.java.net/blog/2007/11/27/consistent-hashing
   
9. * @author xiaoleilu
   
10. *
    
11. * @param
12.    
13.              节点类型
    
14. */
    
15. public class ConsistentHash
16.      
17.        {
    
18.         /** Hash计算对象，用于自定义hash算法 */
    
19.         HashFunc hashFunc;
    
20.         /** 复制的节点个数 */
    
21.         private final int numberOfReplicas;
    
22.         /** 一致性Hash环 */
    
23.         private final SortedMap< Integer, T> circle = new TreeMap< Integer, T>();
    
24.        
    
25.         /**
    
26.          * 构造，使用Java默认的Hash算法
    
27.          * @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡
    
28.          * @param nodes 节点对象
    
29.          */
    
30.         public ConsistentHash(int numberOfReplicas, Collection
31.       
32.         nodes) {
    
33.                 this.numberOfReplicas = numberOfReplicas;
    
34.                 this.hashFunc = new HashFunc() {
    
35.                        
    
36.                         @Override
    
37.                         public Integer hash(Object key) {
    
38.                                 String data = key.toString();
    
39.                                 //默认使用FNV1hash算法
    
40.                                 final int p = 16777619;
    
41.                                 int hash = (int) 2166136261L;
    
42.                                 for (int i = 0; i < data.length(); i++)
    
43.                                         hash = (hash ^ data.charAt(i)) * p;
    
44.                                 hash += hash << 13;
    
45.                                 hash ^= hash >> 7;
    
46.                                 hash += hash << 3;
    
47.                                 hash ^= hash >> 17;
    
48.                                 hash += hash << 5;
    
49.                                 return hash;
    
50.                         }
    
51.                 };
    
52.                 //初始化节点
    
53.                 for (T node : nodes) {
    
54.                         add(node);
    
55.                 }
    
56.         }
    
57.         /**
    
58.          * 构造
    
59.          * @param hashFunc hash算法对象
    
60.          * @param numberOfReplicas 复制的节点个数，增加每个节点的复制节点有利于负载均衡
    
61.          * @param nodes 节点对象
    
62.          */
    
63.         public ConsistentHash(HashFunc hashFunc, int numberOfReplicas, Collection< T> nodes) {
    
64.                 this.numberOfReplicas = numberOfReplicas;
    
65.                 this.hashFunc = hashFunc;
    
66.                 //初始化节点
    
67.                 for (T node : nodes) {
    
68.                         add(node);
    
69.                 }
    
70.         }
    
71.         /**
    
72.          * 增加节点
73.       
74. 
    
75.          * 每增加一个节点，就会在闭环上增加给定复制节点数
76.       
77. 
    
78.          * 例如复制节点数是2，则每调用此方法一次，增加两个虚拟节点，这两个节点指向同一Node
    
79.          * 由于hash算法会调用node的toString方法，故按照toString去重
    
80.          * @param node 节点对象
    
81.          */
    
82.         public void add(T node) {
    
83.                 for (int i = 0; i < numberOfReplicas; i++) {
    
84.                         circle.put(hashFunc.hash(node.toString() + i), node);
    
85.                 }
    
86.         }
    
87.         /**
    
88.          * 移除节点的同时移除相应的虚拟节点
    
89.          * @param node 节点对象
    
90.          */
    
91.         public void remove(T node) {
    
92.                 for (int i = 0; i < numberOfReplicas; i++) {
    
93.                         circle.remove(hashFunc.hash(node.toString() + i));
    
94.                 }
    
95.         }
    
96.         /**
    
97.          * 获得一个最近的顺时针节点
    
98.          * @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
    
99.          * @return 节点对象
    
100.          */
     
101.         public T get(Object key) {
     
102.                 if (circle.isEmpty()) {
     
103.                         return null;
     
104.                 }
     
105.                 int hash = hashFunc.hash(key);
     
106.                 if (!circle.containsKey(hash)) {
     
107.                         SortedMap< Integer, T> tailMap = circle.tailMap(hash);        //返回此映射的部分视图，其键大于等于 hash
     
108.                         hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
     
109.                 }
     
110.                 //正好命中
     
111.                 return circle.get(hash);
     
112.         }
     
113.         /**
     
114.          * Hash算法对象，用于自定义hash算法
     
115.          * @author xiaoleilu
     
116.          *
     
117.          */
     
118.         public interface HashFunc {
     
119.                 public Integer hash(Object key);
     
120.         }
     
121. }
     
123.       
124.      
125.    

复制代码