一致性Hash算法介绍及简单实现——做个笔记
一致性 hash 算法( consistent hashing )介绍:
http://blog.csdn.net/sparkliang/archive/2010/02/02/5279393.aspx
一致性 hash 算法简单实现:
hashcode产生接口
package consistentHash;import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;/** * @author zhengtian * * @date 2012-4-20 下午02:50:26 */@SuppressWarnings("all")public class ConsistentHash<T> {// hashcode生成接口private final HashFunction hashFunction;// 需要复制的虚拟节点个数private final int numberOfReplicas;// hashcode循环圈private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();/** * 构造函数 * * @param hashFunction * @param numberOfReplicas * @param nodes * 真实节点数 */public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {this.hashFunction = hashFunction;this.numberOfReplicas = numberOfReplicas;for (T node : nodes) {add(node);}}/** * 增加节点 * * @param node */public void add(T node) {for (int i = 0; i < numberOfReplicas; i++) {circle.put(hashFunction.hash(node.toString() + i), node);}}/** * 移除节点 * * @param node */public void remove(T node) {for (int i = 0; i < numberOfReplicas; i++) {circle.remove(hashFunction.hash(node.toString() + i));}}/** * 根据对象的key得到顺时针方向的第一个node * * @param key * @return */public T get(Object key) {if (circle.isEmpty()) {return null;}int hash = hashFunction.hash(key);if (!circle.containsKey(hash)) {// 得到circle中hashcode值大于等于hash的部分映射SortedMap<Integer, T> tailMap = circle.tailMap(hash);hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}return circle.get(hash);}public static void main(String[] args) {SortedMap<Integer, String> tailMap = new TreeMap<Integer, String>();tailMap.put(1, "111");tailMap.put(3, "333");tailMap.put(4, "444");tailMap.put(2, "222");System.out.println(tailMap.firstKey());System.out.println(tailMap.get(tailMap.firstKey()));}}