Consistent Hashing

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, //hash算法  
      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);  
 }  
  
}