-
Notifications
You must be signed in to change notification settings - Fork 0
/
ConsistentHash.java
74 lines (56 loc) · 1.77 KB
/
ConsistentHash.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package io.sodabox.common.server.map;
import java.util.HashMap;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
public class ConsistentHash<T> implements NodeMap<T>{
public static final int NUMBER_OF_REPLICAS = 100;
private final HashMap<String, Long[]> keyMap = new HashMap<String, Long[]>();
private final HashFunction hashFunction;
private final int numberOfReplicas;
private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
public ConsistentHash() {
this(Hashing.md5(), NUMBER_OF_REPLICAS);
}
public ConsistentHash(int numberOfReplicas) {
this(Hashing.md5(), numberOfReplicas);
}
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
}
public void add(String key, T node) {
Long keyArray[] = new Long[numberOfReplicas];
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hashString(key + i).asLong(),
node);
keyArray[i] = hashFunction.hashString(key + i).asLong();
}
keyMap.put(key, keyArray);
}
public void remove(String key) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunction.hashString(key + i).asLong());
}
keyMap.remove(key);
}
public boolean isExist(String key){
return keyMap.containsKey(key);
}
public Set<String> getKeys(){
return keyMap.keySet();
}
public T get(String key) {
if (circle.isEmpty()) {
return null;
}
long hash = hashFunction.hashString(key).asLong();
if (!circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}