一致性hash

在缓存场景中，一致性hash算法避免了余数法在因为节点失效导致大面积缓存失效的问题。
直接上代码,使用了Java自带的TreeMap, 参考了dubbo代码中的一致性hash负载
 1 package org.example;
 2 
 3 import java.nio.charset.StandardCharsets;
 4 import java.security.MessageDigest;
 5 import java.security.NoSuchAlgorithmException;
 6 import java.util.*;
 7 
 8 public class ConsistentHash<T> {
 9 
10     private int VIRTUAL_NODE_NUM = 40;
11     private final TreeMap<Long, T> circle = new TreeMap<>();
12 
13     public ConsistentHash(List<T> nodes, int VIRTUAL_NODE_NUM) {
14         this.VIRTUAL_NODE_NUM = VIRTUAL_NODE_NUM;
15         for (T node : nodes) {
16             for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
17                 byte[] digest = md5(node.toString() + i);
18                 for (int h = 0; h < 4; h++) {
19                     long m = hash(digest, h);
20                     circle.put(m, node);
21                 }
22             }
23         }
24     }
25 
26     public T get(Object key) {
27         if (circle.isEmpty()) {
28             return null;
29         }
30         byte[] digest = md5(key.toString());
31         long hash = hash(digest, 0);
32         Map.Entry<Long, T> entry = circle.ceilingEntry(hash);
33         if (entry == null) {
34             entry = circle.firstEntry();
35         }
36         return entry.getValue();
37     }
38 
39 
40     private long hash(byte[] digest, int number) {
41         return (((long) (digest[3 + number * 4] & 0xFF) << 24)
42                 | ((long) (digest[2 + number * 4] & 0xFF) << 16)
43                 | ((long) (digest[1 + number * 4] & 0xFF) << 8)
44                 | (digest[number * 4] & 0xFF))
45                 & 0xFFFFFFFFL;
46     }
47 
48     private byte[] md5(String value) {
49         MessageDigest md5;
50         try {
51             md5 = MessageDigest.getInstance("MD5");
52         } catch (NoSuchAlgorithmException e) {
53             throw new IllegalStateException(e.getMessage(), e);
54         }
55         md5.reset();
56         byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
57         md5.update(bytes);
58         return md5.digest();
59     }
60 }