一致性哈希（Consistent Hashing）

// 传统方式：hash(key) % N
int serverIndex = hash(key) % serverCount;
String server = servers.get(serverIndex);

public class ConsistentHash {
    
    // 哈希环：TreeMap 自动排序
    private TreeMap<Integer, String> circle = new TreeMap<>();
    
    // 虚拟节点数（解决数据倾斜）
    private int virtualNodes = 150;
    
    // 添加服务器
    public void addServer(String server) {
        for (int i = 0; i < virtualNodes; i++) {
            // 每个服务器对应多个虚拟节点
            String virtualNode = server + "#" + i;
            int hash = hash(virtualNode);
            circle.put(hash, server);
        }
    }
    
    // 移除服务器
    public void removeServer(String server) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNode = server + "#" + i;
            int hash = hash(virtualNode);
            circle.remove(hash);
        }
    }
    
    // 获取数据所在服务器
    public String getServer(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        
        int hash = hash(key);
        
        // 顺时针找到第一个大于等于 hash 的节点
        Map.Entry<Integer, String> entry = circle.ceilingEntry(hash);
        
        // 如果没有，回到环的开头（第一个节点）
        if (entry == null) {
            entry = circle.firstEntry();
        }
        
        return entry.getValue();
    }
    
    // FNV1_32_HASH 算法
    private int 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;
    }
}

public class ConsistentHashDemo {
    public static void main(String[] args) {
        ConsistentHash ch = new ConsistentHash();
        
        // 添加服务器
        ch.addServer("192.168.1.1");
        ch.addServer("192.168.1.2");
        ch.addServer("192.168.1.3");
        
        // 查看数据分布
        String[] keys = {"user:1", "user:2", "user:3", "user:4", "user:5"};
        for (String key : keys) {
            System.out.println(key + " → " + ch.getServer(key));
        }
        
        // 输出：
        // user:1 → 192.168.1.2
        // user:2 → 192.168.1.1
        // user:3 → 192.168.1.3
        // user:4 → 192.168.1.2
        // user:5 → 192.168.1.1
        
        // 移除一台服务器
        System.out.println("\n移除 192.168.1.2 后：");
        ch.removeServer("192.168.1.2");
        
        for (String key : keys) {
            System.out.println(key + " → " + ch.getServer(key));
        }
        
        // 输出：
        // user:1 → 192.168.1.3  (变了)
        // user:2 → 192.168.1.1  (没变)
        // user:3 → 192.168.1.3  (没变)
        // user:4 → 192.168.1.3  (变了)
        // user:5 → 192.168.1.1  (没变)
        // 只有 2/5 的数据需要迁移！
    }
}

// Dubbo 一致性哈希负载均衡
@Reference(loadbalance = "consistenthash")
private UserService userService;

// 相同参数的请求总是路由到同一提供者
// 适合有状态服务或缓存场景

public class WeightedConsistentHash {
    
    // 根据服务器权重分配虚拟节点数
    public void addServer(String server, int weight) {
        int virtualNodes = weight * 100;  // 权重 1 = 100 个虚拟节点
        
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNode = server + "#" + i;
            int hash = hash(virtualNode);
            circle.put(hash, server);
        }
    }
}

// 使用：高性能服务器权重高，低性能服务器权重低
ch.addServer("Server-A", 5);  // 高性能
ch.addServer("Server-B", 3);  // 中性能
ch.addServer("Server-C", 1);  // 低性能

// Google 提出的算法，无虚拟节点，内存占用极低
public class JumpConsistentHash {
    
    public static int jumpHash(long key, int numBuckets) {
        long b = -1;
        long j = 0;
        
        while (j < numBuckets) {
            b = j;
            key = key * 2862933555777941757L + 1;
            j = (long) ((b + 1) * (2147483648.0 / ((key >>> 33) + 1)));
        }
        
        return (int) b;
    }
}

优势：
- 无需内存存储哈希环
- 计算复杂度 O(log n)
- 适合超大规模集群

缺点：
- 不支持权重
- 不支持删除节点（只能添加）