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

/**
 * Created by 01369537 on 2019/8/16.
 */
public class ConsistentHash<T> {

    private final HashFunction hashFunction;
    private final int numberOfReplicas;// 節(jié)點(diǎn)的復(fù)制因子,實(shí)際節(jié)點(diǎn)個(gè)數(shù) * numberOfReplicas = 虛擬節(jié)點(diǎn)個(gè)數(shù)
    private final SortedMap<Long, T> circle = new TreeMap<>();// 存儲(chǔ)虛擬節(jié)點(diǎn)的hash值到真實(shí)節(jié)點(diǎn)的映射

    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++)
            // 對于一個(gè)實(shí)際機(jī)器節(jié)點(diǎn) node, 對應(yīng) numberOfReplicas 個(gè)虛擬節(jié)點(diǎn)
            /*
             * 不同的虛擬節(jié)點(diǎn)(i不同)有不同的hash值,但都對應(yīng)同一個(gè)實(shí)際機(jī)器node
             * 虛擬node一般是均衡分布在環(huán)上的,數(shù)據(jù)存儲(chǔ)在順時(shí)針方向的虛擬node上
             */ {
            String key = node.toString() + i;
            Long hash = hashFunction.hash(key);
            System.out.println("key=" + key + " hash=" + hash);
            circle.put(hash, 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),根據(jù)給定的key 取Hash
     * 然后再取得順時(shí)針方向上最近的一個(gè)虛擬節(jié)點(diǎn)對應(yīng)的實(shí)際節(jié)點(diǎn)
     */
    public T get(Object key) {
        if (circle.isEmpty())
            return null;
        long hash = hashFunction.hash((String) key);// node 用String來表示,獲得node在哈希環(huán)中的hashCode
        if (!circle.containsKey(hash)) {//數(shù)據(jù)映射在兩臺(tái)虛擬機(jī)器所在環(huán)之間,就需要按順時(shí)針方向?qū)ふ覚C(jī)器
            //SortedMap的tailMap函數(shù)返回Map中所有大于該key的元素組成的子map
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        //返回存儲(chǔ)key的真實(shí)的節(jié)點(diǎn)
        return circle.get(hash);
    }

    public long getSize() {
        return circle.size();
    }

    public static void main(String[] args) {

        ConsistentHash<String> consistentHash = new ConsistentHash<>(new HashFunction() {
            @Override
            public Long hash(Object key) {
                return (long) key.hashCode();
            }
        }, 2, Arrays.asList("1", "2", "3"));

        String key = "13";
        System.out.println("keyHashCode=" + key.hashCode());
        String node = consistentHash.get(key);
        System.out.println("node=" + node);

    }

}