一致性哈希是一种常用的分布式哈希算法，用于将键（key）映射到节点（node），以实现负载均衡和分布式存储。一下是一个简单的一致性哈希算法，并通过示例代码验证其正确性。

一、一致性哈希算法简介

一致性哈希算法是一种将键映射到节点的分布式哈希算法，其基本思想是将所有可能的键和节点分布在一个哈希环上，通过哈希函数计算键的哈希值，并在哈希环上找到距离最近的节点作为键的所属节点。

二、Java 实现一致性哈希算法：在 Java 中，我们可以使用 TreeMap 来表示哈希环，通过 TreeMap 的 tailMap 方法来查找距离最近的节点。以下是一个简单的一致性哈希算法的实现：

public class ConsistentHashing {

    private SortedMap<Integer, String> circle = new TreeMap<>();
    private List<String> nodes = new ArrayList<>();
    private final int numberOfReplicas = 3; // 虚拟节点的副本数

    /**
     * 计算hash值
     */
    private int getHash1(String key) {
        final int prime = 31;
        int hash = 0;
        for (char c : key.toCharArray()) {
            hash = prime * hash + c;
        }
        return hash;
    }

    private int getHash2(String key) {
        return key.hashCode();
    }

    private int getHash(String key) {
        return ConsistentHashingHashFunction.hashCode(key);
    }

    public void addNode(String node) {
        nodes.add(node);
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = this.getHash(node + i);
            circle.put(hash, node);
        }
    }

    public void removeNode(String node) {
        nodes.remove(node);
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = this.getHash(node + i);
            circle.remove(hash);
        }
    }

    public String getNode(String key) {
        //没有可用节点直接返回
        if (circle.isEmpty()) {
            return null;
        }
        int hash = this.getHash(key);
        if (!circle.containsKey(hash)) {
            //hash环中不存在，说明没有映射到具体节点，于是去找大于等于该hash值的所有节点，即顺时针便利
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    public static void main(String[] args) {
        ConsistentHashing test = new ConsistentHashing();

        // 添加模拟的物理节点
        test.addNode("192.168.0.1");
        test.addNode("192.168.0.2");
        test.addNode("192.168.0.3");

        // 模拟查找多个键的所属节点
        String[] keys = {"A-1", "He-2", "Oey-3", "ReyA-4", "YeyDF-5"};
        for (String key : keys) {
            String node = test.getNode(key);
            System.out.println("Key: " + key + " => Node: " + node);
        }

        // 模拟删除一个物理节点并重新查找所属节点
        test.removeNode("192.168.0.2");

        System.out.println("After removing Node 192.168.0.2:");
        for (String key : keys) {
            String node = test.getNode(key);
            System.out.println("Key: " + key + " => Node: " + node);
        }
    }
}

四、Redis CRC16算法的java实现（大概抄了一下不保证正确）

public class ConsistentHashingHashFunction {

    // Redis CRC16算法
    private static final int CRC16_POLY = 0x1021;
    private static final int CRC16_INIT = 0xFFFF;

    public static int hashCode(String key) {
        byte[] bytes = key.getBytes();
        int crc = CRC16_INIT;
        for (byte b : bytes) {
            crc ^= (b & 0xff) << 8;
            for (int i = 0; i < 8; i++) {
                if ((crc & 0x8000) != 0) {
                    crc = (crc << 1) ^ CRC16_POLY;
                } else {
                    crc <<= 1;
                }
            }
        }
        return crc & 0xffff;
    }

    public static void main(String[] args) {
        // 测试不同键的CRC16哈希值
        String[] keys = {"Key-1", "Key-2", "Key-3", "Key-4", "Key-5"};
        for (String key : keys) {
            int hash = hashCode(key);
            System.out.println("Key: " + key + " => CRC16 Hash: " + hash);
        }
    }
}

三、参考资料：

一致性哈希算法 - 维基百科