一致性哈希算法的原理及实现

import java.util.*;
import java.security.*;

public class ConsistentHash {
    // 哈希环: 虚拟节点哈希值 -> 物理节点名称
    private final TreeMap<Long, String> ring = new TreeMap<>();
    // 每个物理节点对应的虚拟节点数量
    private final int virtualNodes;

    public ConsistentHash(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void addNode(String node) {
        // 一个物理节点映射成 virtualNodes 个虚拟节点，分散到环上
        for (int i = 0; i < virtualNodes; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

    public void removeNode(String node) {
        // 从环上摘除所有虚拟节点
        for (int i = 0; i < virtualNodes; i++) {
            ring.remove(hash(node + "#" + i));
        }
    }

    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        long h = hash(key);
        // 顺时针找到第一个虚拟节点
        Long nodeHash = ring.ceilingKey(h);
        // 没找到说明 key 的哈希值超过了环上最大的节点，绕回到第一个节点
        if (nodeHash == null) {
            nodeHash = ring.firstKey();
        }
        return ring.get(nodeHash);
    }

    // 计算哈希值，用 MD5 取前 8 字节
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes());
            long h = 0;
            for (int i = 0; i < 8; i++) {
                h = (h << 8) | (digest[i] & 0xFF);
            }
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }



    // 统计每个节点分到的 key 数量
    private static Map<String, Integer> getDistribution(ConsistentHash ch, String[] keys) {
        Map<String, Integer> dist = new TreeMap<>();
        for (String key : keys) {
            String node = ch.getNode(key);
            dist.put(node, dist.getOrDefault(node, 0) + 1);
        }
        return dist;
    }

    // 获取每个 key 的映射关系，用于计算迁移量
    private static Map<String, String> getMapping(ConsistentHash ch, String[] keys) {
        Map<String, String> mapping = new HashMap<>();
        for (String key : keys) {
            mapping.put(key, ch.getNode(key));
        }
        return mapping;
    }

    // 统计迁移的 key 数量
    private static int countMigrations(Map<String, String> before, Map<String, String> after) {
        int count = 0;
        for (String key : before.keySet()) {
            if (!before.get(key).equals(after.get(key))) {
                count++;
            }
        }
        return count;
    }


    // 展示一致性哈希的分布和迁移量
    public static void main(String[] args) {
        String[] keys = new String[10000];
        for (int i = 0; i < keys.length; i++) {
            keys[i] = "key-" + i;
        }

        ConsistentHash ch = new ConsistentHash(200);

        // 初始状态：3 个节点
        ch.addNode("node-1");
        ch.addNode("node-2");
        ch.addNode("node-3");
        Map<String, String> mapping3 = getMapping(ch, keys);
        System.out.println("initial 3 nodes: " + getDistribution(ch, keys));

        // 扩容：添加第 4 个节点
        ch.addNode("node-4");
        Map<String, String> mapping4 = getMapping(ch, keys);
        int migrationsAfterAdd = countMigrations(mapping3, mapping4);
        System.out.println("after adding node-4: " + getDistribution(ch, keys));
        System.out.println("  migrated keys: " + migrationsAfterAdd + " (" + (migrationsAfterAdd * 100 / keys.length) + "%)");

        // 缩容：移除 node-2
        ch.removeNode("node-2");
        Map<String, String> mappingAfterRemove = getMapping(ch, keys);
        int migrationsAfterRemove = countMigrations(mapping4, mappingAfterRemove);
        System.out.println("after removing node-2: " + getDistribution(ch, keys));
        System.out.println("  migrated keys: " + migrationsAfterRemove + " (" + (migrationsAfterRemove * 100 / keys.length) + "%)");
    }
}