import java.util.*;

class ConsistentHashing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int HASH_SPACE = 100; // 0–100 like our example

    // Hash function (simple mod for demo, use MD5 in production)
    private int hash(String key) {
        return Math.abs(key.hashCode()) % HASH_SPACE;
    }

    // Add a server to the ring
    public void addServer(String server) {
        int position = hash(server);
        ring.put(position, server);
        System.out.println("Server " + server + " added at position " + position);
    }

    // Remove a server
    public void removeServer(String server) {
        int position = hash(server);
        ring.remove(position);
        System.out.println("Server " + server + " removed from position " + position);
    }

    // Find the server for a given key
    public String getServer(String key) {
        int keyHash = hash(key);
        Map.Entry<Integer, String> entry = ring.ceilingEntry(keyHash);

        if (entry == null) {
            entry = ring.firstEntry(); // wrap around
        }

        return entry.getValue();
    }

    // Show key mappings
    public void printKeyMappings(List<String> keys) {
        for (String key : keys) {
            System.out.println(key + " → " + getServer(key));
        }
    }
}

public class ConsistentHashingDemo {
    public static void main(String[] args) {
        ConsistentHashing ch = new ConsistentHashing();

        // Step 1: Add servers
        ch.addServer("S1");
        ch.addServer("S2");
        ch.addServer("S3");
        ch.addServer("S4");

        List<String> keys = Arrays.asList("K1", "K2", "K3", "K4", "K5", "K6");
        System.out.println("\nInitial key mappings:");
        ch.printKeyMappings(keys);

        // Step 2: Remove a server
        ch.removeServer("S3");
        System.out.println("\nAfter removing S3:");
        ch.printKeyMappings(keys);

        // Step 3: Add a new server
        ch.addServer("S5");
        System.out.println("\nAfter adding S5:");
        ch.printKeyMappings(keys);
    }
}

Server S1 added at position 9
Server S2 added at position 32
Server S3 added at position 60
Server S4 added at position 85

Initial key mappings:
K1 → S2
K2 → S2
K3 → S3
K4 → S4
K5 → S4
K6 → S1

Server S3 removed from position 60

After removing S3:
K1 → S2
K2 → S2
K3 → S4
K4 → S4
K5 → S4
K6 → S1

Server S5 added at position 49

After adding S5:
K1 → S2
K2 → S2
K3 → S5
K4 → S4
K5 → S4
K6 → S1