最近項(xiàng)目碰到了問題，突然就想起了這個(gè)算法，特意找了一下java實(shí)現(xiàn)。
參考文章：
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95.md
https://weblogs.java.net/blog/2007/11/27/consistent-hashing
最后發(fā)現(xiàn)這篇，已經(jīng)有實(shí)現(xiàn)了。感謝作者。

HashFunction.java

package consistenhash;

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.zip.CRC32;

import net.rubyeye.xmemcached.utils.ByteUtils;

public class HashFunction {
    private MessageDigest md5 = null;

    public long hash(String key) {
        if (md5 == null) {
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                throw new IllegalStateException("no md5 algorythm found");
            }
        }

        md5.reset();
        md5.update(key.getBytes());
        byte[] bKey = md5.digest();
        long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)
                | (long) (bKey[0] & 0xFF);
        return res & 0xffffffffL;
    }
  
}

ConsistentHash.java

package consistenhash;

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

    private final HashFunction hashFunction;
    private final int numberOfReplicas;  // 虛擬節(jié)點(diǎn)
    private final SortedMap<Long, T> circle = new TreeMap<Long, T>();   // 用來存儲(chǔ)虛擬節(jié)點(diǎn)hash值 到真實(shí)node的映射

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

    /**
     * 獲得一個(gè)最近的順時(shí)針節(jié)點(diǎn)
     * @param key 為給定鍵取Hash，取得順時(shí)針方向上最近的一個(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)的實(shí)際節(jié)點(diǎn)
     * @return
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        long hash = hashFunction.hash((String) key);
        if (!circle.containsKey(hash)) {
            SortedMap<Long, T> tailMap = circle.tailMap(hash); ////返回此映射的部分視圖，其鍵大于等于 hash
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
    
    public long getSize() {
        return circle.size();
    }
    
}

Test.java

package consistenhash;

import java.util.HashSet;
import java.util.Set;

public class Test {

    public static void main(String[] args) {

        Set<String> nodes = new HashSet<String>();
        nodes.add("0");
        nodes.add("1");
        //nodes.add("C");
        ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 160, nodes);

        //consistentHash.add("D");
        System.out.println(consistentHash.getSize());  //640

        System.out.println(consistentHash.get("0"));
        System.out.println(consistentHash.get("1"));
        System.out.println(consistentHash.get("2"));
        System.out.println(consistentHash.get("3"));
        System.out.println(consistentHash.get("4"));
        System.out.println(consistentHash.get("5"));
        System.out.println(consistentHash.get("6"));
        System.out.println(consistentHash.get("7"));
        System.out.println(consistentHash.get("8"));
        System.out.println(consistentHash.get("9"));
    }

}