Skip to content

Instantly share code, notes, and snippets.

@bcambel
Created July 28, 2016 07:59
Show Gist options
  • Star 7 You must be signed in to star a gist
  • Fork 11 You must be signed in to fork a gist
  • Save bcambel/cd45ab30bd19cb7e69bcb3fb64e71922 to your computer and use it in GitHub Desktop.
Save bcambel/cd45ab30bd19cb7e69bcb3fb64e71922 to your computer and use it in GitHub Desktop.
Consistent Hash Java implementation
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
private final HashFunction hashFunction;
private final int numberOfReplicas;
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
public void add(T node) {
for (int i = 0; i <numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i), node);
}
}
public void remove(T node) {
for (int i = 0; i <numberOfReplicas; i++) {
circle.remove(hashFunction.hash(node.toString() + i));
}
}
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}
@cyberaka
Copy link

The code for HashFunction is not listed. Did I miss something obvious?

@maobaolong
Copy link

hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();

If the hash of the node is larger than the biggest key, this method will return the first element of this tree map, which can make first element become a hot element.

@jeev567
Copy link

jeev567 commented Jan 9, 2023

this code looks like ChatGPT generated. I see similar signatures.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment