一致性哈希算法

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

/**
 * 一致性哈希算法实现
 */
public class ConsistentHashing {
    // 哈希环，存储虚拟节点的哈希值到物理节点的映射
    private final SortedMap<Long, String> hashRing = new TreeMap<>();
    // 每个物理节点对应的虚拟节点数量
    private final int numberOfReplicas;
    // 存储所有物理节点
    private final Set<String> physicalNodes = new HashSet<>();

    /**
     * 构造函数
     * @param numberOfReplicas 每个物理节点对应的虚拟节点数量
     * @param nodes 初始物理节点列表
     */
    public ConsistentHashing(int numberOfReplicas, Collection<String> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        // 添加初始节点
        for (String node : nodes) {
            addNode(node);
        }
    }

    /**
     * 添加物理节点
     * @param node 物理节点标识（如IP地址）
     */
    public void addNode(String node) {
        if (physicalNodes.contains(node)) {
            return; // 节点已存在
        }
        
        physicalNodes.add(node);
        
        // 为每个物理节点创建多个虚拟节点并添加到哈希环
        for (int i = 0; i < numberOfReplicas; i++) {
            // 虚拟节点的名称为 "物理节点#虚拟节点索引"
            String virtualNode = node + "#" + i;
            long hash = hash(virtualNode);
            hashRing.put(hash, node);
            System.out.printf("添加虚拟节点: %s, 哈希值: %d, 对应物理节点: %s%n", 
                             virtualNode, hash, node);
        }
    }

    /**
     * 移除物理节点
     * @param node 物理节点标识
     */
    public void removeNode(String node) {
        if (!physicalNodes.contains(node)) {
            return; // 节点不存在
        }
        
        physicalNodes.remove(node);
        
        // 移除该物理节点对应的所有虚拟节点
        for (int i = 0; i < numberOfReplicas; i++) {
            String virtualNode = node + "#" + i;
            long hash = hash(virtualNode);
            hashRing.remove(hash);
            System.out.printf("移除虚拟节点: %s, 哈希值: %d%n", virtualNode, hash);
        }
    }

    /**
     * 获取数据对应的物理节点
     * @param key 数据键
     * @return 负责存储该数据的物理节点
     */
    public String getNode(String key) {
        if (hashRing.isEmpty()) {
            return null; // 没有可用节点
        }
        
        long hash = hash(key);
        
        // 如果哈希值不在环上，则顺时针查找第一个虚拟节点
        if (!hashRing.containsKey(hash)) {
            SortedMap<Long, String> tailMap = hashRing.tailMap(hash);
            hash = tailMap.isEmpty() ? hashRing.firstKey() : tailMap.firstKey();
        }
        
        return hashRing.get(hash);
    }

    /**
     * 计算哈希值
     * 使用MD5算法获取128位哈希值，取前8位作为长整型哈希值
     * @param key 要计算哈希值的键
     * @return 哈希值
     */
    private long hash(String key) {
        try {
            MessageDigest md5 = MessageDigest.getInstance("MD5");
            md5.update(key.getBytes());
            byte[] digest = md5.digest();
            
            // 取前8位字节作为哈希值（转为长整型）
            long hash = 0;
            for (int i = 0; i < 8; i++) {
                hash = (hash << 8) | (digest[i] & 0xFF);
            }
            return hash;
        } catch (NoSuchAlgorithmException e) {
            // 如果MD5算法不可用，使用Java内置的哈希函数
            return key.hashCode() & 0x7FFFFFFF; // 确保返回正数
        }
    }

    /**
     * 测试一致性哈希算法
     */
    public static void main(String[] args) {
        // 初始化3个物理节点，每个节点对应3个虚拟节点
        List<String> nodes = Arrays.asList("192.168.1.1", "192.168.1.2", "192.168.1.3");
        ConsistentHashing ch = new ConsistentHashing(3, nodes);
        
        // 测试数据路由
        String[] keys = {"user1", "user2", "user3", "user4", "user5", "user6", "user7"};
        System.out.println("\n初始节点路由:");
        for (String key : keys) {
            System.out.printf("数据 %s 路由到节点: %s%n", key, ch.getNode(key));
        }
        
        // 移除一个节点
        System.out.println("\n移除节点 192.168.1.2 后:");
        ch.removeNode("192.168.1.2");
        for (String key : keys) {
            System.out.printf("数据 %s 路由到节点: %s%n", key, ch.getNode(key));
        }
        
        // 添加一个新节点
        System.out.println("\n添加节点 192.168.1.4 后:");
        ch.addNode("192.168.1.5");
        for (String key : keys) {
            System.out.printf("数据 %s 路由到节点: %s%n", key, ch.getNode(key));
        }
    }
}