算法之一致性哈希算法：动态负载均衡的数学之美

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

public class ConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int virtualNodes;
    private final HashFunction hashFunc;

    public ConsistentHash(Collection<T> nodes, int virtualNodes) {
        this.virtualNodes = virtualNodes;
        this.hashFunc = new MD5Hash();
        for (T node : nodes) addNode(node);
    }

    // 添加节点（生成虚拟节点）
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hashFunc.hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    // 删除节点
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hashFunc.hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    // 获取数据归属节点
    public T getNode(String key) {
        if (ring.isEmpty()) return null;
        long hash = hashFunc.hash(key);
        SortedMap<Long, T> tailMap = ring.tailMap(hash);
        Long nodeHash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
        return ring.get(nodeHash);
    }

    // 哈希函数（MD5示例）
    private static class MD5Hash implements HashFunction {
        public long hash(String key) {
            try {
                MessageDigest md = MessageDigest.getInstance("MD5");
                byte[] digest = md.digest(key.getBytes());
                return ((digest[3] & 0xFFL) << 24) | ((digest[2] & 0xFFL) << 16)
                     | ((digest[1] & 0xFFL) << 8) | (digest[0] & 0xFFL);
            } catch (Exception e) { throw new RuntimeException(e); }
        }
    }

    interface HashFunction { long hash(String key); }
}