java 实现一致性 hash 算法

/**
 * 抽象hash实现接口
 */
public interface HashFunction {
    Integer hash(String key);
}

public class HashFunctionImpl implements HashFunction {
    @Override
    public Integer hash(String key) {
        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
}

/**
 * 物理机节点模拟类，保存节点的IP、名称、端口等信息
 */
@Data
public class Node {
    private String ip;
    private String name;
    public Node(String ip, String name) {
        this.ip = ip;
        this.name = name;
    }
}

package com.li.hash.sevice;
import com.li.hash.entity.Node;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
    private final HashFunction hashFunction;
    /**
     * 每个机器节点关联的虚拟节点个数
     */
    private final int numberOfReplicas;
    /**
     * 环形虚拟节点
     */
    private final SortedMap<Integer, Node> circle = new TreeMap<>();
    /**
     * @param hashFunction     hash 函数接口
     * @param numberOfReplicas 每个机器节点关联的虚拟节点个数
     * @param nodes            真实机器节点
     */
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<Node> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        for (Node node : nodes) {
            add(node);
        }
    }
    /**
     * 增加真实机器节点
     *
     * @param node
     */
    public void add(Node node) {
        for (int i = 0; i < this.numberOfReplicas; i++) {
            circle.put(this.hashFunction.hash(node.getIp() + i), node);
        }
    }
    /**
     * 取得真实机器节点
     *
     * @param key
     * @return
     */
    public Node get(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        Integer hash = hashFunction.hash(key);
        if (!circle.containsKey(hash)) {
            //沿环的顺时针找到一个虚拟节点
            SortedMap<Integer, Node> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        // 返回该虚拟节点对应的真实机器节点的信息
        return circle.get(hash);
    }
}

package com.li.hash;
import com.li.hash.entity.Node;
import com.li.hash.sevice.ConsistentHash;
import com.li.hash.sevice.HashFunction;
import com.li.hash.sevice.impl.HashFunctionImpl;
import org.junit.Test;
import java.util.*;
public class test {
    @Test
    public void hashTest() {
        // 机器节点IP前缀
        final String IP_PREFIX = "192.168.1.";
        // 每台真实机器节点上保存的记录条数
        Map<String, Integer> map = new HashMap<String, Integer>();
        HashFunction hashFunction = new HashFunctionImpl();
        //真实物理节点
        List<Node> realNodes = new ArrayList<>();
        // 每台真实机器节点上保存的记录条数初始为0
        for (int i = 1; i <= 10; i++) {
            map.put(IP_PREFIX + i, 0);
            Node node = new Node(IP_PREFIX + i, "node" + i);
            realNodes.add(node);
        }
        ConsistentHash consistentHash = new ConsistentHash(hashFunction, 100, realNodes);
        // 将10000条记录尽可能均匀的存储到10台机器节点
        for (int i = 0; i < 1000000; i++) {
            // 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
            String data = UUID.randomUUID().toString() + i;
            // 通过记录找到真实机器节点
            Node node = consistentHash.get(data);
            // 这里可以通过其它工具将记录存储真实机器节点上，比如MemoryCache等
            // ...
            // 每台真实机器节点上保存的记录条数加1
            map.put(node.getIp(), map.get(node.getIp()) + 1);
        }
        // 打印每台真实机器节点保存的记录条数
        for (int i = 1; i <= 10; i++) {
            System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get("192.168.1." + i));
        }
    }
}

192.168.1.1节点记录条数：86617
192.168.1.2节点记录条数：103035
192.168.1.3节点记录条数：118516
192.168.1.4节点记录条数：107492
192.168.1.5节点记录条数：99635
192.168.1.6节点记录条数：110879
192.168.1.7节点记录条数：99929
192.168.1.8节点记录条数：94695
192.168.1.9节点记录条数：85379
192.168.1.10节点记录条数：93823