一致性HASH算法的JAVA实现

        一致性哈希算法是分布式系统中常用的算法。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
        一致性Hash算法将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环。
如下图所示：

Java代码  

1. package hash;  
2.   
3. import java.io.UnsupportedEncodingException;  
4. import java.nio.ByteBuffer;  
5. import java.nio.ByteOrder;  
6. import java.security.MessageDigest;  
7. import java.security.NoSuchAlgorithmException;  
8. import java.util.*;  
9.   
10. /** 
11.  * Created by IntelliJ IDEA. 
12.  * User: test 
13.  * Date: 12-5-24 
14.  * Time: 下午5:37 
15.  * To change this template use File | Settings | File Templates. 
16.  */  
17. public class ConsistencyHash {  
18.     private TreeMap<Long,Object> nodes = null;  
19.     //真实服务器节点信息  
20.     private List<Object> shards = new ArrayList();  
21.     //设置虚拟节点数目  
22.     private int VIRTUAL_NUM = 4;  
23.   
24.     /** 
25.      * 初始化一致环 
26.      */  
27.     public void init() {  
28.          shards.add("192.168.0.0-服务器0");  
29.          shards.add("192.168.0.1-服务器1");  
30.          shards.add("192.168.0.2-服务器2");  
31.          shards.add("192.168.0.3-服务器3");  
32.          shards.add("192.168.0.4-服务器4");  
33.   
34.         nodes = new TreeMap<Long,Object>();  
35.         for(int i=0; i<shards.size(); i++) {  
36.             Object shardInfo = shards.get(i);  
37.             for(int j=0; j<VIRTUAL_NUM; j++) {  
38.                 nodes.put(hash(computeMd5("SHARD-" + i + "-NODE-" + j),j), shardInfo);  
39.             }  
40.         }  
41.     }  
42.   
43.     /** 
44.      * 根据key的hash值取得服务器节点信息 
45.      * @param hash 
46.      * @return 
47.      */  
48.     public Object getShardInfo(long hash) {  
49.         Long key = hash;  
50.         SortedMap<Long, Object> tailMap=nodes.tailMap(key);  
51.         if(tailMap.isEmpty()) {  
52.             key = nodes.firstKey();  
53.         } else {  
54.             key = tailMap.firstKey();  
55.         }  
56.         return nodes.get(key);  
57.     }  
58.   
59.     /** 
60.      * 打印圆环节点数据 
61.      */  
62.      public void printMap() {  
63.          System.out.println(nodes);  
64.      }  
65.   
66.     /** 
67.      * 根据2^32把节点分布到圆环上面。 
68.      * @param digest 
69.      * @param nTime 
70.      * @return 
71.      */  
72.       public long hash(byte[] digest, int nTime) {  
73.         long rv = ((long) (digest[3+nTime*4] & 0xFF) << 24)  
74.                 | ((long) (digest[2+nTime*4] & 0xFF) << 16)  
75.                 | ((long) (digest[1+nTime*4] & 0xFF) << 8)  
76.                 | (digest[0+nTime*4] & 0xFF);  
77.   
78.         return rv & 0xffffffffL; /* Truncate to 32-bits */  
79.       }  
80.   
81.     /** 
82.      * Get the md5 of the given key. 
83.      * 计算MD5值 
84.      */  
85.      public byte[] computeMd5(String k) {  
86.         MessageDigest md5;  
87.         try {  
88.             md5 = MessageDigest.getInstance("MD5");  
89.         } catch (NoSuchAlgorithmException e) {  
90.             throw new RuntimeException("MD5 not supported", e);  
91.         }  
92.         md5.reset();  
93.         byte[] keyBytes = null;  
94.         try {  
95.             keyBytes = k.getBytes("UTF-8");  
96.         } catch (UnsupportedEncodingException e) {  
97.             throw new RuntimeException("Unknown string :" + k, e);  
98.         }  
99.   
100.         md5.update(keyBytes);  
101.         return md5.digest();  
102.      }  
103.   
104.      public static void main(String[] args) {  
105.          Random ran = new Random();  
106.          ConsistencyHash hash = new ConsistencyHash();  
107.          hash.init();  
108.          hash.printMap();  
109.          //循环50次，是为了取50个数来测试效果，当然也可以用其他任何的数据来测试  
110.          for(int i=0; i<50; i++) {  
111.              System.out.println(hash.getShardInfo(hash.hash(hash.computeMd5(String.valueOf(i)),ran.nextInt(hash.VIRTUAL_NUM))));  
112.          }  
113.    }  
114.   
115. }