一致性哈希

1. 简介
一致性哈希（consistent hashing） 是一种 hash 算法，在移除/添加一个节点时，它能够尽可能小的改变已存在 key 的映射关系。
最简单的哈希算法是模运算（%），slot = hashCode() % N (N为节点数)
但是当N增加或减少时，slot的值会和之前完全不一样，导致完全不命中。

2. java实现

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);
 }

}

可以看到用java实现一个一致性哈希算法如此简单，核心就是调用SortedMap.tailMap和firstKey这两个方法。

3. 参考资料
Memcached分布式算法详解
Consistent Hashing